Implementacja drzewa BST w Javie
Przykładowa implementacja drzewa poszukiwań binarnych (BST) w Javie
Nasza implementacja drzewa BST składa się z dwóch klas.
Wezel– jest klasą wewnętrzną. Reprezentuje pojedynczy węzeł w drzewie. Przechowywanym kluczem jest wartość int.Drzewo– zawiera algorytmy dodawania, usuwania, wyświetlania elementów, odnajdywania poprzednika i następnika węzła oraz przechowuje korzeń. Jest klasą zewnętrzną.
Drzewa BST są ważną strukturą danych. Pozwalają o wiele skrócić czas wyszukiwania elementów, co jest szczególnie zauważalne przy dużych zbiorach. Oczywiście zakładając, że drzewo jest zrównoważone – w przeciwnym wypadku liczba operacji może wzrosnąć do poziomu zwykłej listy. Dużo lepszą wydajność zapewnią drzewa AVL lub drzewa czerwono-czarne. Te struktury poprzez rotacje potrafią zapewnić zrównoważenie poziomu obu poddrzew korzenia. Aby jednak je poznać warto najpierw poznać dokładnie drzewa BST, gdyż ta wiedza jest niezbędna, aby potem stosować dodatkowe zasady umieszczania węzłów.
Teoretyczna część znajduje się w naszym artykule odnośnie drzew BST. Tutaj skupimy się na praktycznej implementacji podanych tam algorytmów.
Klasa Drzewo
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 |
package pl.programistajava.Drzewo; public class Drzewo { private Wezel root; class Wezel { private Wezel left; private Wezel right; private Wezel parent; private int key; public Wezel(int key) { this.key = key; this.right = null; this.left = null; this.parent = null; } public Wezel getParent() { return parent; } public void setParent(Wezel parent) { this.parent = parent; } public Wezel getLeft() { return left; } public void setLeft(Wezel left) { this.left = left; } public Wezel getRight() { return right; } public void setRight(Wezel right) { this.right = right; } public int getKey() { return key; } public void setKey(int key) { this.key = key; } } public static void main(String[] args) { Drzewo tree = new Drzewo(); tree.addWezel(10); tree.addWezel(5); tree.addWezel(20); tree.addWezel(2); tree.addWezel(8); tree.addWezel(15); System.out.println("Wezel o wartości 10: " + tree.getWezel(10).getKey()); System.out.println("Maksymalna wartość w drzewie: " + tree.getMax(tree.getRoot()).getKey()); System.out.println("Minimalna wartość w drzewie: " + tree.getMin(tree.getRoot()).getKey()); System.out.println("Następnik korzenia: " + tree.successor(tree.getRoot()).getKey()); System.out.println("Poprzednik korzenia: " + tree.predecessor(tree.getRoot()).getKey()); System.out.println("Wartość korzenia: " + tree.getRoot().getKey()); System.out.println("Usuwam aktualny korzeń - klucz " + tree.getRoot().getKey()); tree.removeWezel(10); System.out.println("Wartość korzenia: " +tree.getRoot().getKey()); System.out.println("Rekurencyjne wyszukiwaie: " + tree.getWezel(tree.getRoot(), 5).getKey()); } public Wezel getWezel(int key) { Wezel current = getRoot(); while(current != null && current.getKey() != key) { if(key > current.getKey()) { current = current.getRight(); }else { current = current.getLeft(); } } if(current == null) { throw new NullPointerException("Nie znaleziono węzła z kluczem " + key); } return current; } public Wezel getWezel(Wezel node, int key) { if (key > node.getKey()){ return getWezel(node.getRight(), key); }else if(key < node.getKey()) { return getWezel(node.getLeft(), key); }else { return node; } } public boolean addWezel(int key){ Wezel parent = null; Wezel current = getRoot(); while(current != null) { parent = current; if(current.getKey() == key) { return false; } if(key > current.getKey()) { current = current.getRight(); }else if(key < current.getKey()) { current = current.getLeft(); } } Wezel tmp = new Wezel(key); if(parent == null) { setRoot(tmp); }else if(key > parent.getKey()) { parent.setRight(tmp); tmp.setParent(parent); }else if(key < parent.getKey()) { parent.setLeft(tmp); tmp.setParent(parent); } return true; } public void removeWezel(int key) { Wezel toDelete = getWezel(key); Wezel tmp,pred = null; if(toDelete.getLeft() == null || toDelete.getRight() == null) { //usuwamy liść lub element z jednym poddrzewem tmp = toDelete; }else { //usuwamy węzeł, z dwoma potomkami - szukamy następnika //można też znalezc poprzednik tmp = successor(toDelete); } if(tmp.getLeft() != null) { pred = tmp.getLeft(); }else { pred = tmp.getRight(); } if(pred != null) { pred.setParent(tmp.getParent()); } if(tmp.getParent() == null) { setRoot(pred); }else { if(tmp == tmp.getParent().getLeft()) { tmp.getParent().setLeft(pred); }else { tmp.getParent().setRight(pred); } } if(tmp.getKey() != toDelete.getKey()) { toDelete.setKey(tmp.getKey()); } } public Wezel predecessor(Wezel w) { if(w.getLeft() != null) { return getMax(w.getLeft()); } Wezel tmp = w.getParent(); while(w != null && w.getRight().getKey() != tmp.getKey()) { tmp = w; w = w.getRight(); } return w; } public Wezel successor(Wezel w) { if(w.getRight() != null) { return getMin(w.getRight()); } Wezel tmp = w.getParent(); while(w != null && w.getLeft().getKey() != tmp.getKey()) { tmp = w; w = w.getLeft(); } return w; } public Wezel getMin(Wezel w) { Wezel current = w; while(current.getLeft() != null) { current = current.getLeft(); } return current; } public Wezel getMax(Wezel w) { Wezel current = w; while(current.getRight() != null) { current = current.getRight(); } return current; } public Wezel getRoot() { return root; } public void setRoot(Wezel root) { this.root = root; } } |
Wewnętrzna klasa Wezel
Klasa Wezel przechowuje informację o dwóch potomkach, o rodzicu oraz klucz. Ze względu na to, że ta struktura danych jest mało elastyczna umieściliśmy ją wewnątrz klasy Drzewo, gdyż i tak nie wykorzystamy jej nigdzie indziej.
Pola
Obiekt klasy Wezel zawiera trzy referencje:
- do lewego potomka,
- do prawego potomka,
- oraz do rodzica.
Dodatkowym polem jest przechowywana wartość czyli zmienna key.
Konstruktor
Inicjuje dane – referencje do innych węzłów na null, a pole z danymi uzupełnia wartością przekazaną w argumencie.
Zewnętrzna klasa Drzewo
Obiekt klasy Drzewo przechowuje referencję do korzenia (ang. root). Zawiera również niezbędne algorytmy, takie jak:
- dodawanie elementów do drzewa,
- usuwanie elementów z drzewa,
- szukanie elementu o konkretnej wartości,
- znalezienie największej wartości w drzewie,
- znalezienie najmniejszej wartości w drzewie,
- wskazanie następnika węzła,
- wskazanie poprzednika węzła.
Wykonanie metody main() spowoduje wyświetlenie następujących komunikatów w konsoli.
|
1 2 3 4 5 6 7 8 |
Wezel o wartości 10: 10 Maksymalna wartość w drzewie: 20 Minimalna wartość w drzewie: 2 Następnik korzenia: 15 Poprzednik korzenia: 8 Wartość korzenia: 10 Usuwam aktualny korzeń - klucz 10 Wartość korzenia: 15 |
System zbierania nieużytków (ang. Garbage collector)
W Javie nie ma potrzeby ręcznego czyszczenia pamięci. Wystarczy odłączyć usuwany obiekt od struktury drzewa.
