прелюдия
Тази статия е за двоични дървета за търсене. Наскоро написах статия за Там наистина не обърнах внимание на двоичните дървета, защото методите за търсене, вмъкване, изтриване не бяха подходящи. Сега реших да напиша статия за дърветата. Може би ще започнем.
Дървото е структура от данни, състояща се от възли, свързани с ръбове. Можем да кажем, че дървото е частен случай на граф. Ето едно примерно дърво:
Това не е двоично дърво за търсене! Всичко е под разрез!
терминология
корен
Корен на дърво е най-горният възел. В примера това е възел A. В дървото само един път може да води от корена до всеки друг възел! Всъщност всеки възел може да се разглежда като корен на поддървото, съответстващо на този възел.
Родители/потомство
Всички възли с изключение на корена имат точно един ръб, водещ до друг възел. Извиква се възелът над текущия възел родител този възел. Извиква се възел, разположен под текущия и свързан с него потомък този възел. Да вземем пример. Вземете възел B, тогава неговият родител ще бъде възел A, а децата му ще бъдат възли D, E и F.
лист
Възел, който няма деца, се нарича лист на дървото. В примера възлите D, E, F, G, I, J, K ще бъдат листа.
Това е основната терминология. Други концепции ще бъдат обсъдени по-късно. И така, двоично дърво е дърво, в което всеки възел няма да има повече от две деца. Както се досещате, дървото от примера няма да е двоично, защото възлите B и H имат повече от две деца. Ето пример за двоично дърво:
Възлите на дървото могат да съдържат всякаква информация. Двоично дърво за търсене е двоично дърво, което има следните свойства:
- Лявото и дясното поддървета са двоични дървета за търсене.
- Всички възли на лявото поддърво на произволен възел X имат стойности на ключ за данни, по-малки от стойността на ключ за данни на самия възел X.
- Всички възли на дясното поддърво на произволен възел X имат стойности на ключ за данни, по-големи или равни на стойността на ключа за данни на самия възел X.
ключ - някаква характеристика на възела (например число). Ключът е необходим, за да може да се намери елементът от дървото, на който съответства този ключ. Пример за двоично дърво за търсене:
дървовиден изглед
Докато продължавам, ще включа някои (може би непълни) части от код, за да подобря вашето разбиране. Пълният код ще бъде в края на статията.
Дървото се състои от възли. Структура на възела:
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;
}
//...остальные методы узла
}
Всеки възел има две деца (напълно възможно е децата leftChild и/или rightChild да бъдат null). Вероятно сте разбрали, че в този случай числовите данни са данните, съхранявани във възела; ключ - ключ на възел.
Разбрахме възела, сега нека поговорим за належащите проблеми с дърветата. По-нататък думата "дърво" ще означава концепцията за двоично дърво за търсене. Двоична дървовидна структура:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Като поле на клас се нуждаем само от корена на дървото, защото от корена, използвайки методите getLeftChild() и getRightChild(), можете да стигнете до всеки възел на дървото.
Дървовидни алгоритми
Търсене
Да приемем, че имате изградено дърво. Как да намеря елемент с ключ ключ? Трябва последователно да се придвижите от корена надолу по дървото и да сравните стойността на ключа с ключа на следващия възел: ако ключът е по-малък от ключа на следващия възел, отидете до левия потомък на възела, ако е повече - надясно, ако ключовете са равни - желаният възел е намерен! Подходящ код:
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;
}
Ако токът стане нулев, тогава итерацията е достигнала края на дървото (на концептуално ниво вие сте на несъществуващо място в дървото - дете на лист).
Помислете за ефективността на алгоритъма за търсене на балансирано дърво (дърво, в което възлите са разпределени повече или по-малко равномерно). Тогава ефективността на търсенето ще бъде O(log(n)) и логаритъм по основа 2. Вижте: ако има n елемента в балансирано дърво, това означава, че ще има нива на log(n) по основа 2 на дървото. И в търсенето, за една стъпка от цикъла, слизате едно ниво надолу.
вмъкнете
Ако сте схванали същността на търсенето, тогава няма да ви е трудно да разберете вмъкването. Просто трябва да слезете до листа на дървото (според правилата за слизане, описани в търсенето) и да станете негов потомък - отляво или отдясно, в зависимост от ключа. Изпълнение:
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;
}
}
}
}
}
В този случай, в допълнение към текущия възел, е необходимо да се съхранява информация за родителя на текущия възел. Когато current стане нула, родителската променлива ще съдържа листа, от който се нуждаем.
Ефективността на вмъкване очевидно ще бъде същата като тази на търсенето - O(log(n)).
Отстраняване
Изтриването е най-сложната операция, която ще трябва да се извърши с дърво. Ясно е, че първо ще е необходимо да намерим елемента, който ще премахнем. Но тогава какво? Ако просто зададем препратката му към null, тогава ще загубим информация за поддървото, чийто корен е този възел. Методите за отстраняване на дървета са разделени на три случая.
Първи случай. Възелът, който трябва да бъде премахнат, няма деца.
Ако възелът, който трябва да бъде изтрит, няма деца, това означава, че е лист. Следователно можете просто да зададете полетата leftChild или rightChild на неговия родител на null.
Втори случай. Възелът, който трябва да бъде премахнат, има едно дете
Този случай също не е много труден. Да се върнем към нашия пример. Да предположим, че трябва да изтрием елемент с ключ 14. Съгласете се, че тъй като това е дясното дете на възел с ключ 10, тогава всеки от неговите наследници (в този случай десният) ще има ключ, по-голям от 10, така че вие може лесно да го „изреже“ от дървото и да свърже родителя директно към дъщерния на възела, който се изтрива, т.е. свържете възела с ключ 10 към възел 13. Ситуацията би била подобна, ако трябваше да изтрием възел, който е ляво дете на своя родител. Замислете се сами - точна аналогия.
Трети случай. Node има две деца
Най-трудният случай. Нека да разгледаме един нов пример.
Търсене на наследник
Да кажем, че трябва да премахнем възела с ключ 25. Кого да поставим на негово място? Един от неговите последователи (потомци или потомци на потомци) трябва да стане наследник(този, който ще заеме мястото на премахнатия възел).
Откъде знаеш кой трябва да бъде наследникът? Интуитивно, това е възелът в дървото, чийто ключ е следващият по големина от възела, който се премахва. Алгоритъмът е следният. Трябва да отидете до дясното му дете (винаги до дясното, защото вече беше казано, че ключът на наследника е по-голям от ключа на възела, който се изтрива), и след това да преминете през веригата от леви деца на този десен дете. В примера трябва да отидем до възела с ключ 35 и след това да слезем по веригата на левите му деца до листа - в този случай тази верига се състои само от възела с ключ 30. Строго погледнато, ние търсим най-малкият възел в набора от възли, по-голям от желания възел.
Код на метода за търсене на наследник:
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;//В зависимости от того, является ли удаляемый узел левым или правым потомком своего родителя, булевская переменная 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;
}
Сложността може да се приближи до O(log(n)).
Намиране на максимум/минимум в дърво
Очевидно, как да намерите минималната / максималната стойност в дървото - трябва последователно да преминете през веригата от леви / десни елементи на дървото, съответно; когато стигнете до листа, това ще бъде минималният/максималния елемент.
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;
}
Сложност - O(log(n))
Симетричен байпас
Преминаването е посещение на всеки възел на дървото, за да се направи нещо с него.
Алгоритъм за рекурсивен симетричен обход:
- Направете действие върху лявото дете
- Направете действие със себе си
- Направете действие върху правилното дете
Код:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Заключение
Най-накрая! Ако не съм обяснил нещо или имам коментари, тогава чакам в коментарите. Както беше обещано, тук е пълният код.
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
Дегенерация до O(n)
Много от вас може би са забелязали: какво ще стане, ако накарате дървото да стане неуравновесено? Например, поставете възли в дървото с нарастващи ключове: 1,2,3,4,5,6... Тогава дървото донякъде ще напомня на свързан списък. И да, дървото ще загуби своята дървовидна структура, а оттам и ефективността на достъпа до данни. Сложността на операциите за търсене, вмъкване и изтриване ще стане същата като тази на свързан списък: O(n). Това е един от най-важните, според мен, недостатъци на двоичните дървета.
В анкетата могат да участват само регистрирани потребители. , Моля те.
Не съм бил в Хабре от доста време и бих искал да знам какви статии по какви теми бихте искали да видите повече?
-
Структури на данни
-
Алгоритми (DP, рекурсия, компресиране на данни и др.)
-
Приложение на структури от данни и алгоритми в реалния живот
-
Програмиране на android приложения на Java
-
Програмиране на Java уеб приложения
2 потребители гласуваха. 1 потребител се въздържа.
Източник: www.habr.com