Gra wstępna
Ten artykuł dotyczy drzew wyszukiwania binarnego. Niedawno napisałem artykuł nt Tam tak naprawdę nie zwracałem uwagi na drzewa binarne, ponieważ metody wyszukiwania, wstawiania, usuwania nie były istotne. Teraz postanowiłem napisać artykuł o drzewach. Być może zaczniemy.
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ładowe drzewo:
To nie jest drzewo wyszukiwania binarnego! Wszystko jest pod kreską!
terminologia
korzeń
Korzeń drzewa jest najwyższym węzłem. W tym przykładzie jest to węzeł A. W drzewie tylko jedna ścieżka może prowadzić od korzenia do dowolnego innego węzła! W rzeczywistości każdy węzeł można uznać za korzeń poddrzewa odpowiadającego temu węzłowi.
Rodzice/potomstwo
Wszystkie węzły z wyjątkiem korzenia mają dokładnie jedną krawędź prowadzącą do innego węzła. Węzeł nad bieżącym węzłem jest wywoływany rodzic ten węzeł. Nazywa się węzeł znajdujący się poniżej bieżącego i połączony z nim potomek ten węzeł. Weźmy przykład. Weź węzeł B, wtedy jego rodzicem będzie węzeł A, a jego dziećmi będą węzły D, E i F.
Arkusz
Węzeł, który nie ma dzieci, nazywany jest liściem drzewa. W przykładzie węzły D, E, F, G, I, J, K będą liśćmi.
To jest podstawowa terminologia. Inne koncepcje zostaną omówione później. Tak więc drzewo binarne to drzewo, w którym każdy węzeł będzie miał nie więcej niż dwoje dzieci. Jak się domyślacie, drzewo z przykładu nie będzie binarne, ponieważ węzły B i H mają więcej niż dwoje dzieci. Oto przykład drzewa binarnego:
Węzły drzewa mogą zawierać dowolne informacje. Drzewo wyszukiwania binarnego to drzewo binarne, które ma następujące właściwości:
- Zarówno lewe, jak i prawe poddrzewo są binarnymi drzewami wyszukiwania.
- Wszystkie węzły lewego poddrzewa dowolnego węzła X mają wartości klucza 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 klucza danych większe lub równe wartości klucza danych samego węzła X.
klucz - jakaś cecha węzła (na przykład liczba). Klucz jest potrzebny, aby móc znaleźć element drzewa, któremu ten klucz odpowiada. Przykład drzewa wyszukiwania binarnego:
widok drzewa
W trakcie będę dołączał 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;
}
//...остальные методы узла
}
Każdy węzeł ma dwoje dzieci (jest całkiem możliwe, że dzieci leftChild i/lub rightChild będą puste). Prawdopodobnie zrozumiałeś, że w tym przypadku dane liczbowe to dane przechowywane w węźle; klucz - klucz węzła.
Rozwiązaliśmy węzeł, teraz porozmawiajmy o palących problemach z drzewami. W dalszej części słowo „drzewo” będzie oznaczało pojęcie drzewa wyszukiwania binarnego. Struktura drzewa binarnego:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Jako pole klasowe potrzebujemy tylko korzenia drzewa, ponieważ z korzenia metodami getLeftChild() i getRightChild() można dostać się do dowolnego węzła drzewa.
Algorytmy drzewa
Wyszukiwanie
Powiedzmy, że masz zbudowane drzewo. Jak znaleźć element za pomocą klucza klucza? Musisz kolejno przejść od korzenia w dół drzewa i porównać wartość klucza z kluczem następnego węzła: jeśli klucz jest mniejszy niż klucz następnego węzła, przejdź do lewego potomka węzła, jeśli więcej - w prawo, jeśli klucze są równe - żądany 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 prąd stanie się zerowy, oznacza to, że iteracja osiągnęła koniec drzewa (na poziomie koncepcyjnym znajdujesz się w nieistniejącym miejscu w drzewie - dziecko liścia).
Rozważ efektywność algorytmu wyszukiwania na zrównoważonym drzewie (drzewie, w którym węzły są rozmieszczone mniej więcej równomiernie). Wtedy wydajność wyszukiwania wyniesie O(log(n)), a logarytm o podstawie 2. Zobacz: jeśli w zrównoważonym drzewie jest n elementów, oznacza to, że będzie log(n) poziomów drzewa o podstawie 2. A w poszukiwaniu jednego kroku cyklu schodzisz o jeden poziom niżej.
wstawić
Jeśli uchwyciłeś istotę wyszukiwania, zrozumienie wstawienia nie będzie dla ciebie trudne. Wystarczy zejść do liścia drzewa (zgodnie z zasadami zejścia opisanymi w wyszukiwaniu) i stać się jego potomkiem - w lewo lub w prawo, w zależności od klucza. Realizacja:
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;
}
}
}
}
}
W takim przypadku oprócz bieżącego węzła konieczne jest przechowywanie informacji o rodzicu bieżącego węzła. Gdy prąd stanie się pusty, zmienna nadrzędna będzie zawierać potrzebny nam arkusz.
Efektywność wstawiania będzie oczywiście taka sama jak w przypadku wyszukiwania - O(log(n)).
Usuwanie
Usuwanie jest najbardziej złożoną operacją, jaką należy wykonać na drzewie. Oczywiste jest, że najpierw konieczne będzie znalezienie elementu, który zamierzamy usunąć. Ale co wtedy? Jeśli po prostu ustawimy jego odniesienie na wartość null, stracimy informacje o poddrzewie, którego korzeniem jest ten węzeł. Metody usuwania drzew dzielą się na trzy przypadki.
Pierwszy przypadek. Węzeł do usunięcia nie ma dzieci.
Jeśli usuwany węzeł nie ma dzieci, oznacza to, że jest liściem. Dlatego możesz po prostu ustawić pola leftChild lub rightChild jego rodzica na wartość null.
Drugi przypadek. Węzeł do usunięcia ma jedno dziecko
Ten przypadek również nie jest bardzo trudny. Wróćmy do naszego przykładu. Załóżmy, że musimy usunąć element z kluczem 14. Zgadzam się, że ponieważ jest to prawe dziecko węzła z kluczem 10, to każdy z jego potomków (w tym przypadku prawy) będzie miał klucz większy niż 10, więc może łatwo „wyciąć” go z drzewa i połączyć rodzica bezpośrednio z dzieckiem usuwanego węzła, tj. połącz węzeł z kluczem 10 z węzłem 13. Sytuacja byłaby podobna, gdybyśmy musieli usunąć węzeł będący lewym dzieckiem swojego rodzica. Pomyśl o tym sam - dokładna analogia.
Trzeci przypadek. Węzeł ma dwoje dzieci
Najtrudniejszy przypadek. Spójrzmy na nowy przykład.
Szukaj następcy
Powiedzmy, że musimy usunąć węzeł z kluczem 25. Kogo postawimy na jego miejsce? Jeden z jego wyznawców (potomków lub potomków potomków) musi zostać następca(ten, który zajmie miejsce usuniętego węzła).
Skąd wiadomo, kto powinien być następcą? Intuicyjnie jest to węzeł w drzewie, którego klucz jest następny co do wielkości z usuwanego węzła. Algorytm jest następujący. Trzeba przejść do jego prawego potomka (zawsze do prawego, bo już było powiedziane, że klucz następcy jest większy niż klucz usuwanego węzła), a następnie przejść przez łańcuch lewych potomków tego prawego dziecko. W przykładzie musimy przejść do węzła z kluczem 35, a następnie zejść łańcuchem jego lewych dzieci do liścia - w tym przypadku łańcuch ten składa się tylko z węzła z kluczem 30. Ściśle mówiąc, szukamy najmniejszy węzeł w zbiorze węzłów większy niż żądany węzeł.
Kod następnej metody wyszukiwania:
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;
}
Pełny kod metody delete:
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;//В зависимости от того, является ли удаляемый узел левым или правым потомком своего родителя, булевская переменная isLeftChild будет принимать значение true или 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;
}
Złożoność można przybliżyć do O (log (n)).
Znajdowanie maksimum/minimum w drzewie
Oczywiście, jak znaleźć minimalną / maksymalną wartość w drzewie - musisz kolejno przejść przez łańcuch odpowiednio lewych / prawych elementów drzewa; kiedy dojdziesz do liścia, będzie to element minimalny/maksymalny.
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;
}
Złożoność — O(log(n))
Obejście symetryczne
Traversal to wizyta w każdym węźle drzewa w celu zrobienia z nim czegoś.
Rekurencyjny algorytm przechodzenia symetrycznego:
- Wykonaj akcję na lewym dziecku
- Zrób akcję ze sobą
- Wykonaj działanie na właściwym dziecku
Kod:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
wniosek
Wreszcie! Jeśli czegoś nie wyjaśniłem lub mam jakieś uwagi, to czekam w komentarzach. Zgodnie z obietnicą, oto pełny kod.
Node.java:
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 void setLeftChild(Node<T> newNode) {
leftChild = newNode;
}
public void setRightChild(Node<T> newNode) {
rightChild = newNode;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> 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());
}
}
}
PS
Degeneracja do O(n)
Wielu z was mogło zauważyć: co jeśli sprawisz, że drzewo stanie się niezrównoważone? Na przykład umieść węzły w drzewie z kluczami rosnącymi: 1,2,3,4,5,6... Wtedy drzewo będzie trochę przypominało listę połączoną. I tak, drzewo straci swoją drzewiastą strukturę, a co za tym idzie efektywność dostępu do danych. Złożoność operacji wyszukiwania, wstawiania i usuwania będzie taka sama jak w przypadku listy połączonej: O(n). Jest to jedna z najważniejszych, moim zdaniem, wad drzew binarnych.
W ankiecie mogą brać udział tylko zarejestrowani użytkownicy. , Proszę.
Nie byłem na Habré od dość dawna, a chciałbym wiedzieć, jakie artykuły na jakie tematy chcielibyście zobaczyć więcej?
-
Struktury danych
-
Algorytmy (DP, rekurencja, kompresja danych itp.)
-
Zastosowanie struktur danych i algorytmów w życiu codziennym
-
Programowanie aplikacji na Androida w Javie
-
Programowanie aplikacji internetowych w Javie
Głosowało 2 użytkowników. 1 użytkownik wstrzymał się od głosu.
Źródło: www.habr.com