Drzewa binarne, drzewa BST i kopce w Javie

W drzewie binarnym każdy węzeł ma co najwyżej dwoje dzieci, lewe i prawe. W Javie węzeł to mała klasa, na przykład taka:

1class TreeNode {2    int value;3    TreeNode left;4    TreeNode right;5}

• Korzeń to najwyższy węzeł, jedyny bez rodzica. Przez niego dochodzisz do całego drzewa.
• Liść nie ma dzieci: left i right są null. Wszystkie inne węzły nazywa się węzłami wewnętrznymi.
• Poddrzewo to węzeł razem ze wszystkim, co wisi pod nim. Lewe poddrzewo korzenia samo jest więc drzewem.
• Wysokość liczy tutaj poziomy: pojedynczy węzeł ma wysokość 1, puste drzewo wysokość 0. Niektóre książki liczą zamiast tego krawędzie, wtedy wszystko jest o 1 mniejsze.

Metoda na drzewie prawie zawsze ma ten sam schemat: warunkiem stopu jest puste drzewo (node == null), w przeciwnym razie przetwarzasz węzeł i wywołujesz siebie dla node.left i node.right. Każdy węzeł jest odwiedzany dokładnie raz, co kosztuje O(n).

Odwiedzanie wszystkich węzłów to przechodzenie drzewa. Trzy typowe kolejności różnią się tylko tym, kiedy przychodzi kolej na sam węzeł:

• Preorder: węzeł, lewo, prawo. Korzeń jest na początku.
• Inorder: lewo, węzeł, prawo. Korzeń jest w środku.
• Postorder: lewo, prawo, węzeł. Korzeń jest na końcu.

1public class Main {2    static int countNodes(TreeNode node) {3        if (node == null) {4            return 0;5        }6        return 1 + countNodes(node.left) + countNodes(node.right);7    }8
9    static int height(TreeNode node) {10        if (node == null) {11            return 0;12        }13        return 1 + Math.max(height(node.left), height(node.right));14    }15
16    static void preorder(TreeNode node) {17        if (node == null) {18            return;19        }20        System.out.print(node.value + " ");21        preorder(node.left);22        preorder(node.right);23    }24
25    static void inorder(TreeNode node) {26        if (node == null) {27            return;28        }29        inorder(node.left);30        System.out.print(node.value + " ");31        inorder(node.right);32    }33
34    static void postorder(TreeNode node) {35        if (node == null) {36            return;37        }38        postorder(node.left);39        postorder(node.right);40        System.out.print(node.value + " ");41    }42
43    public static void main(String[] args) {44        //        145        //       / \46        //      2   347        //     / \48        //    4   549        TreeNode root = new TreeNode(1,50                new TreeNode(2, new TreeNode(4), new TreeNode(5)),51                new TreeNode(3));52        System.out.println("Nodes: " + countNodes(root));53        System.out.println("Height: " + height(root));54        System.out.print("Preorder:  ");55        preorder(root);56        System.out.println();57        System.out.print("Inorder:   ");58        inorder(root);59        System.out.println();60        System.out.print("Postorder: ");61        postorder(root);62        System.out.println();63    }64}65
66class TreeNode {67    int value;68    TreeNode left;69    TreeNode right;70
71    TreeNode(int value) {72        this.value = value;73    }74
75    TreeNode(int value, TreeNode left, TreeNode right) {76        this.value = value;77        this.left = left;78        this.right = right;79    }80}

Dla drzewa z przykładu daje to 1 2 4 5 3, 4 2 5 1 3 i 4 5 2 3 1. Na kolokwium pomaga narysować drzewo i odhaczać każdy węzeł przy odwiedzeniu.

Drzewo poszukiwań binarnych porządkuje wartości: dla każdego węzła wszystkie wartości w lewym poddrzewie są mniejsze, a wszystkie w prawym większe. Przy wyszukiwaniu porównujesz z węzłem i idziesz w lewo albo w prawo, zupełnie jak przy wyszukiwaniu binarnym w tablicy. Nową wartość wstawia się w miejscu, w którym wyszukiwanie trafi na null.

• Najmniejsza wartość jest na samym dole po lewej, największa na samym dole po prawej.
• Inorder daje wartości posortowane.
• Wyszukiwanie i wstawianie potrzebują tylu kroków, ile wynosi wysokość drzewa. Jeśli drzewo jest zrównoważone, to około log₂ n, czyli O(log n): 1 000 000 wartości w około 20 poziomach.
• Jeśli wstawiasz wartości już posortowane (1, 2, 3, …), każdy nowy węzeł wisi po prawej stronie poprzedniego. Drzewo degeneruje się do listy, a wyszukiwanie kosztuje wtedy O(n). Drzewa samorównoważące się (AVL, czerwono-czarne, w Javie TreeMap) temu zapobiegają.

1public class Main {2    static TreeNode insert(TreeNode root, int value) {3        if (root == null) {4            return new TreeNode(value);5        }6        if (value < root.value) {7            root.left = insert(root.left, value);8        } else if (value > root.value) {9            root.right = insert(root.right, value);10        }11        return root;12    }13
14    static boolean contains(TreeNode root, int value) {15        TreeNode node = root;16        while (node != null) {17            if (value == node.value) {18                return true;19            }20            node = value < node.value ? node.left : node.right;21        }22        return false;23    }24
25    static int min(TreeNode root) {26        TreeNode node = root;27        while (node.left != null) {28            node = node.left;29        }30        return node.value;31    }32
33    static void inorder(TreeNode node) {34        if (node == null) {35            return;36        }37        inorder(node.left);38        System.out.print(node.value + " ");39        inorder(node.right);40    }41
42    public static void main(String[] args) {43        TreeNode root = null;44        for (int v : new int[] {50, 30, 70, 20, 40, 60, 80}) {45            root = insert(root, v);46        }47        System.out.println("contains 40? " + contains(root, 40));48        System.out.println("contains 45? " + contains(root, 45));49        System.out.println("min: " + min(root));50        System.out.print("sorted: ");51        inorder(root);52        System.out.println();53    }54}55
56class TreeNode {57    int value;58    TreeNode left;59    TreeNode right;60
61    TreeNode(int value) {62        this.value = value;63    }64}

Kopiec minimalny (min-heap) to drzewo binarne z własnością kopca: każdy węzeł jest mniejszy lub równy swoim dzieciom. Minimum jest więc zawsze w korzeniu. Inaczej niż w drzewie BST rodzeństwo nie jest między sobą uporządkowane.

Kopiec jest zawsze zupełny, wypełniany poziom po poziomie od lewej. Dlatego mieści się bez luk w tablicy:

• korzeń pod indeksem 0
• dzieci i: 2 * i + 1 i 2 * i + 2
• rodzic i: (i - 1) / 2 (dzielenie całkowite)

Wstawianie: dopisz na końcu i przesuwaj w górę, dopóki wartość jest mniejsza od rodzica. Usuwanie minimum: wstaw ostatni element pod indeks 0 i przesuwaj go w dół, zawsze zamieniając z mniejszym dzieckiem. Obie operacje przechodzą przez drzewo co najwyżej raz z góry na dół: O(log n). Java oferuje to gotowe jako PriorityQueue.

1import java.util.Arrays;2
3public class Main {4    static int[] data = new int[10];5    static int size = 0;6
7    static void insert(int value) {8        data[size] = value;9        int i = size;10        size++;11        // sift up: swap with the parent while smaller12        while (i > 0 && data[i] < data[(i - 1) / 2]) {13            swap(i, (i - 1) / 2);14            i = (i - 1) / 2;15        }16    }17
18    static int poll() {19        int min = data[0];20        size--;21        data[0] = data[size];22        int i = 0;23        // sift down: swap with the smaller child while larger24        while (2 * i + 1 < size) {25            int child = 2 * i + 1;26            if (child + 1 < size && data[child + 1] < data[child]) {27                child++;28            }29            if (data[i] <= data[child]) {30                break;31            }32            swap(i, child);33            i = child;34        }35        return min;36    }37
38    static void swap(int i, int j) {39        int tmp = data[i];40        data[i] = data[j];41        data[j] = tmp;42    }43
44    public static void main(String[] args) {45        for (int v : new int[] {5, 3, 8, 1, 4}) {46            insert(v);47            System.out.println("insert " + v + ": " + Arrays.toString(Arrays.copyOf(data, size)));48        }49        System.out.println("poll: " + poll());50        System.out.println("heap: " + Arrays.toString(Arrays.copyOf(data, size)));51    }52}

Heapsort sortuje za pomocą kopca maksymalnego bezpośrednio w tablicy:

1. Zbuduj kopiec: od a.length / 2 - 1 do 0 przesuwaj w dół każdy węzeł wewnętrzny. Potem maksimum jest pod indeksem 0.
2. Zamień maksimum z ostatnim elementem kopca. Stoi ono teraz na swoim ostatecznym miejscu, a kopiec jest o jeden element krótszy. Przesuń nowy korzeń w dół i powtarzaj.

Każde przesunięcie w dół kosztuje O(log n) i dzieje się n razy: O(n log n), także w najgorszym przypadku. W przeciwieństwie do quicksorta heapsort nie potrzebuje dodatkowej pamięci i nie ma złego przypadku z O(n²). Za to nie jest stabilny: równe wartości mogą zamienić się kolejnością.

1import java.util.Arrays;2
3public class Main {4    static void heapSort(int[] a) {5        // 1. build a max-heap: let every inner node sink, from back to front6        for (int i = a.length / 2 - 1; i >= 0; i--) {7            siftDown(a, i, a.length);8        }9        // 2. move the maximum to the end, shrink the heap, repair it10        for (int end = a.length - 1; end > 0; end--) {11            swap(a, 0, end);12            siftDown(a, 0, end);13        }14    }15
16    static void siftDown(int[] a, int i, int size) {17        while (2 * i + 1 < size) {18            int child = 2 * i + 1;19            if (child + 1 < size && a[child + 1] > a[child]) {20                child++;21            }22            if (a[i] >= a[child]) {23                return;24            }25            swap(a, i, child);26            i = child;27        }28    }29
30    static void swap(int[] a, int i, int j) {31        int tmp = a[i];32        a[i] = a[j];33        a[j] = tmp;34    }35
36    public static void main(String[] args) {37        int[] a = {4, 10, 3, 5, 1};38        heapSort(a);39        System.out.println(Arrays.toString(a));40    }41}