Wstęp
Ten artykuł poświęcony jest binarnym drzewom wyszukiwania. Niedawno pisałem artykuł na temat Tam nie zwracałem dużo uwagi na drzewa binarne, ponieważ metody wyszukiwania, wstawiania i usuwania nie były istotne. Teraz postanowiłem napisać artykuł dokładnie o drzewach. Zacznijmy.
Drzewo to struktura danych składająca się z węzłów połączonych krawędziami. Można powiedzieć, że drzewo jest szczególnym przypadkiem grafu. Oto przykład drzewa:
To nie jest binarne drzewo wyszukiwania! Wszystko poniżej!
Terminologia
Korzeń
Korzeń drzewa to najwyższy jego węzeł. W naszym przykładzie jest to węzeł A. W drzewie od korzenia do dowolnego innego węzła może prowadzić tylko jedna ścieżka! W rzeczywistości każdy węzeł można rozważać jako korzeń odpowiadającego mu poddrzewa.
Rodzice / potomkowie
Wszystkie węzły, poza korzeniem, mają dokładnie jedną krawędź prowadzącą w górę do innego węzła. Węzeł znajdujący się wyżej od aktualnego nazywa się rodzicem tego węzła. Węzeł znajdujący się niżej i połączony z nim nazywa się potomkiem tego węzła. Spójrzmy na przykład. Weźmy węzeł B, wtedy jego rodzicem będzie węzeł A, a potomkami węzły D, E i F.
Kartka
Węzeł, który nie ma potomków, nazywa się liściem drzewa. W naszym przykładzie liśćmi będą węzły D, E, F, G, I, J, K.
To podstawowa terminologia. Inne pojęcia będą omawiane dalej. Tak więc, drzewo binarne to drzewo, w którym każdy węzeł ma nie więcej niż dwóch potomków. Jak się domyśliliście, drzewo z przykładu nie jest binarne, ponieważ węzły B i H mają więcej niż dwóch potomków. Oto przykład binarnego drzewa:
W węzłach drzewa może znajdować się dowolna informacja. Binarne drzewo wyszukiwania to binarne drzewo, które charakteryzuje się następującymi właściwościami:
- Oba poddrzewa — lewe i prawe — są binarnymi drzewami wyszukiwania.
- Wszystkie węzły lewego poddrzewa dowolnego węzła X mają wartości kluczy danych mniejsze niż wartość klucza danych samego węzła X.
- Wszystkie węzły prawego poddrzewa dowolnego węzła X mają wartości kluczy danych większe lub równe wartości klucza danych tego węzła X.
Klucz to jakaś cecha węzła (np. liczba). Klucz jest potrzebny, aby można było znaleźć element drzewa, do którego przypisany jest ten klucz. Oto przykład binarnego drzewa wyszukiwania:
Reprezentacja drzewa
W miarę postępu będę przedstawiać niektóre (być może niekompletne) fragmenty kodu, aby poprawić twoje zrozumienie. Pełny kod będzie na końcu artykułu.
Drzewo składa się z węzłów. Struktura węzła:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
//...pozostałe metody węzła
}
Każdy węzeł ma dwóch potomków (prawdopodobnie potomkowie leftChild i/lub rightChild będą zawierać wartość null). Można zauważyć, że w tym przypadku liczba data – to dane przechowywane w węźle; key – to klucz węzła.
Z węzłem już się zapoznaliśmy, teraz porozmawiajmy o bieżących problemach związanych z drzewami. Tutaj i dalej przez słowo „drzewo” rozumiem pojęcie binarnego drzewa wyszukiwania. Struktura binarnego drzewa:
public class BinaryTree<T> {
private Node<T> root;
//metody drzewa
}
Jako pole klasy potrzebujemy tylko korzenia drzewa, ponieważ z korzenia za pomocą metod getLeftChild() i getRightChild() można dotrzeć do dowolnego węzła drzewa.
Algorytmy w drzewie
Wyszukiwanie
Załóżmy, że masz zbudowane drzewo. Jak znaleźć element z kluczem key? Należy kolejno poruszać się od korzenia w dół po drzewie i porównywać wartość key z kluczem kolejnego węzła: jeśli key jest mniejszy niż klucz kolejnego węzła, to przeszukaj lewego potomka węzła, jeśli większy – prawego, a jeśli klucze są równe – poszukiwany węzeł został znaleziony! Odpowiedni kod:
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
Jeśli current staje się równy null, to oznacza, że przeszukiwanie osiągnęło koniec drzewa (na poziomie koncepcyjnym znajdujesz się w nieistniejącym miejscu drzewa – potomku liścia).
Rozważmy efektywność algorytmu wyszukiwania w zbalansowanym drzewie (drzewie, w którym węzły są rozłożone w miarę równomiernie). W takim razie efektywność wyszukiwania będzie O(log(n)), przy czym logarytm o podstawie 2. Zobacz: jeśli w zbalansowanym drzewie jest n elementów, to oznacza, że będzie log(n) o podstawie 2 poziomów drzewa. A w wyszukiwaniu, w jednym kroku pętli, schodzisz na jeden poziom.
Wstawka
Jeśli zrozumiałeś istotę wyszukiwania, to zrozumienie wstawki nie sprawi ci trudności. Wystarczy po prostu zejść do liścia drzewa (zgodnie z zasadami schodzenia, opisanymi w wyszukiwaniu) i stać się jego potomkiem — lewym lub prawym, w zależności od klucza. Implementacja:
public void insert(T insertData, int key) {
Node current = root;
Node parent;
Node newNode = new Node(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
W tej sytuacji należy, oprócz bieżącego węzła, przechowywać informacje o rodzicu bieżącego węzła. Kiedy current stanie się równy null, w zmiennej parent będzie leżał potrzebny nam liść.
Efektywność wstawki oczywiście będzie taka sama jak dla wyszukiwania — O(log(n)).
Usunięcie
Usunięcie jest najtrudniejszą operacją, jaką trzeba będzie przeprowadzić z drzewem. Oczywiste jest, że najpierw musimy znaleźć element, który planujemy usunąć. Ale co potem? Jeśli po prostu przypiszemy jego referencji wartość null, stracimy informacje o poddrzewie, którego korzeniem jest ten węzeł. Metody usuwania drzewa dzielą się na trzy przypadki.
Pierwszy przypadek. Usuwany węzeł nie ma potomków.
Jeśli usuwany węzeł nie ma potomków, to oznacza, że jest liściem. W związku z tym można po prostu przypisać wartość null polom leftChild lub rightChild jego rodzica.
Drugi przypadek. Usuwany węzeł ma jednego potomka.
Ten przypadek również nie jest zbyt trudny. Wróćmy do naszego przykładu. Załóżmy, że musimy usunąć element z kluczem 14. Zgódź się, że ponieważ jest on prawym potomkiem węzła z kluczem 10, każdy jego potomek (w tym przypadku prawy) będzie miał klucz większy od 10, więc można go łatwo „wyciąć” z drzewa, a rodzica bezpośrednio połączyć z potomkiem usuwanego węzła, tzn. węzeł z kluczem 10 połączyć z węzłem 13. Podobna sytuacja miałaby miejsce, gdyby trzeba było usunąć węzeł, który jest lewym potomkiem swojego rodzica. Pomyśl o tym sam.
Trzeci przypadek. Węzeł ma dwóch potomków.
Najtrudniejszy przypadek. Rozważmy na nowym przykładzie.
Wyszukiwanie następcy.
Załóżmy, że trzeba usunąć węzeł o kluczu 25. Kogo ustawimy na jego miejsce? Ktoś z jego potomków (dziedziców lub potomków potomków) powinien zostać następcą(tym, kto zajmie miejsce usuwanego węzła).
Jak zrozumieć, kto powinien zostać następcą? Intuicyjnie wiadomo, że jest to węzeł w drzewie, którego klucz jest największy spośród kluczy mniejszych od usuwanego węzła. Algorytm polega na tym, aby przejść do jego prawego potomka (zawsze do prawego, ponieważ już wspomniano, że klucz następcy jest większy od klucza usuwanego węzła), a następnie prześledzić łańcuch lewych potomków tego prawego potomka. W przykładzie musimy przejść do węzła o kluczu 35, a następnie przejść w dół do liścia wzdłuż łańcucha jego lewych potomków — w tym przypadku łańcuch ten składa się tylko z węzła o kluczu 30. Ścisłe mówiąc, szukamy najmniejszego węzła w zbiorze węzłów większych niż szukany węzeł.
Kod metody wyszukiwania następcy:
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode; // rodzic następcy
Node<T> successor = deleteNode; // następca
Node<T> current = successor.getRightChild(); // po prostu "przebiegający" węzeł
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
// na wyjściu z pętli mamy następcy i rodzica następcy
if (successor != deleteNode.getRightChild()) { // jeśli następca nie zgadza się z prawym potomkiem usuwanego węzła
parentSuccessor.setLeftChild(successor.getRightChild()); // to jego rodzic zabiera sobie potomka następcy, aby go nie stracić
successor.setRightChild(deleteNode.getRightChild()); // łączymy następcy z prawym potomkiem usuwanego węzła
}
return successor;
}
Pełny kod metody delete:
public boolean delete(int deleteKey) {
Node current = root;
Node parent = current;
boolean isLeftChild = false; // W zależności od tego, czy usuwany węzeł jest lewym, czy prawym dzieckiem swojego rodzica, zmienna boolean isLeftChild przyjmie wartość true lub false odpowiednio.
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) { // pierwszy przypadek
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) { // drugi przypadek
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else { // trzeci przypadek
Node successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
Złożoność można przybliżyć do O(log(n)).
Szukaj maksimum/minimum w drzewie
Oczywiście, aby znaleźć minimalną/maksymalną wartość w drzewie, należy kolejno przechodzić po łańcuchu lewych/prawych elementów drzewa; kiedy dotrzesz do liścia, będzie on minimalnym/maksymalnym elementem.
public Node getMinimum(Node startPoint) {
Node current = startPoint;
Node parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node getMaximum(Node startPoint) {
Node current = startPoint;
Node parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
Złożoność — O(log(n))
Symetryczne przejście
Przejście — odwiedzanie każdego węzła drzewa w celu wykonania jakiejś akcji.
Algorytm rekurencyjnego symetrycznego przejścia:
- Zrób akcję z lewym dzieckiem
- Zrób akcję ze sobą
- Zrób akcję z prawym dzieckiem
Kod:
public void inOrder(Node current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " "); //Tutaj może być wszystko, co chcesz
inOrder(current.getRightChild());
}
}
Podsumowanie
W końcu! Jeśli coś niedokładnie wyjaśniłem lub masz jakiekolwiek uwagi, czekam na komentarze. Jak obiecałem, podaję pełny kod.
Node.java:
public class Node {
private T data;
private int key;
private Node leftChild;
private Node rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node newNode) {
leftChild = newNode;
}
public void setRightChild(Node newNode) {
rightChild = newNode;
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.java:
public class BinaryTree<T> {
private Node<T> root;
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;
Node<T> successor = deleteNode;
Node<T> current = successor.getRightChild();
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
if (successor != deleteNode.getRightChild()) {
parentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(deleteNode.getRightChild());
}
return successor;
}
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
P.S.
Degeneracja do O(n)
Wielu z was mogło zauważyć: a co, jeśli zrobimy drzewo niezrównoważonym? Na przykład, umieszczając w drzewie węzły z rosnącymi kluczami: 1,2,3,4,5,6… Wtedy drzewo będzie przypominać listę połączoną. I tak, drzewo straci swoją strukturę drzewiastą, a co za tym idzie, efektywność dostępu do danych. Złożoność operacji wyszukiwania, wstawiania, usuwania stanie się taka jak w listach połączonych: O(n). W tym objawia się jedno z najważniejszych, moim zdaniem, niedociągnięć drzew binarnych.
Tylko zarejestrowani użytkownicy mogą brać udział w ankiecie. , proszę.
Niedawno znalazłem się na Hubie i chciałbym wiedzieć, o jakich tematach chcielibyście widzieć więcej artykułów?
Struktury danych
Algorytmy (DP, rekurencja, kompresja danych itd.)
Zastosowanie struktur danych i algorytmów w realnym życiu
Programowanie aplikacji android w Javie
Programowanie aplikacji webowych w Javie
Zagłosowało 2 użytkowników. Wstrzymał się 1 użytkownik.
Źródło: habr.com
