Прелюдия
Тази статия е посветена на двоичните дървета за търсене. Наскоро написах статия за Там не обърнах много внимание на двоичните дървета, тъй като методите за търсене, добавяне, изтриване не бяха актуални. Сега реших да напиша статия именно за дърветата. Нека започнем.
Дърво — структура от данни, състояща се от възли, свързани с ръбове. Може да се каже, че дървото е специален случай на граф. Ето пример за дърво:
Това не е двоично дърво за търсене! Всичко под кат!
Терминология
Корен
Коренът на дървото е най-горният му възел. В примера — това е възел 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). Вероятно сте разбрали, че в този случай data — това са данните, съхранявани в възела; key — ключът на възела.
След като разгледахме възела, да поговорим за актуалните проблеми с дърветата. Под термина 'дърво' тук и по-нататък ще имам предвид концепцията за двоично дърво за търсене. Структурата на двоичното дърво:
public class BinaryTree<T> {
private Node<T> root;
//методи на дървото
}
Като поле на класа ще ни е нужен само корена на дървото, тъй като от корена, с помощта на методите getLeftChild() и getRightChild(), можем да достигнем до всеки възел на дървото.
Алгоритми в дървото
Търсене
Представете си, че имате построено дърво. Как да намерите елемент с ключ key? Трябва да се движите последователно от корена надолу по дървото и да сравнявате стойността на key с ключа на текущия възел: ако key е по-малко от ключа на текущия възел, преминете към левия наследник на възела, ако е по-голям — към десния, ако ключовете са равни — търсеният възел е намерен! Съответният код:
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;
}
Ако current стане равно на null, значи переборът е достигнал края на дървото (на концептуално ниво вие се намирате на несъществуващо място в дървото — наследник на листа).
Нека разгледаме ефективността на алгоритъма за търсене в балансирано дърво (дърво, в което възлите са разпределени по-горе равномерно). Тогава ефективността на търсенето ще бъде O(log(n)), като логаритъмът е по основание 2. Вижте: ако в балансирано дърво има n елемента, това означава, че ще има log(n) по основание 2 нива на дървото. А в процеса на търсене, с една стъпка на цикъла, слизате на едно ниво.
Вмъкване
Ако сте уловили същността на търсенето, ще ви бъде лесно да разберете вмъкването. Просто трябва да се спуснете до листа на дървото (по правилата на спускането, описани в търсенето) и да станете негов потомък — ляв или десен, в зависимост от ключа. Реализация:
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;
}
}
}
}
}
В този случай трябва, освен текущия възел, да се съхранява информация за родителя на текущия възел. Когато current стане равен на null, в променливата parent ще се съдържа нужният ни лист.
Ефективността на вмъкването очевидно ще бъде същата като при търсенето — O(log(n)).
Удаление
Изтриването е най-сложната операция, която ще трябва да извършим с дървото. Ясно е, че първо трябва да намерим елемента, който ще изтриваме. Но какво следва? Ако просто присвоим на съответната променлива стойност null, ще загубим информация за поддървото, чийто корен е този възел. Методи за изтриване на дърво се разделят на три случая.
Първият случай. Изтриваният възел няма потомци
Ако изтриваният възел няма потомци, това означава, че е лист. Следователно, можем просто да присвоим стойност null на полетата leftChild или rightChild на родителя му.
Вторият случай. Изтриваният възел има един потомък
Този случай също не е много сложен. Нека се върнем към нашия пример. Да кажем, че трябва да изтрием елемент с ключ 14. Съгласете се, че тъй като той е десен потомък на възел с ключ 10, всеки негов потомък (в този случай десен) ще има ключ, по-голям от 10, затова можем лесно да го 'изрежем' от дървото, а родителя да свържем директно с потомка на изтривания възел, т.е. възел с ключ 10 да бъде свързан с възел 13. Аналогично би била ситуацията, ако трябваше да изтрием възел, който е химичен ляв потомък на родителя си. Помислете за това сами — точна аналогия.
Третият случай. Възелът има двама потомци
Най-сложният случай. Да разгледаме нов пример.
Търсене на наследник
Представете си, трябва да премахнем възел с ключ 25. Кой да поставим на негово място? Някой от неговите последователи (потомци или потомците на потомците) трябва да стане наследник(онзи, който заема мястото на премахнатия възел).
Как да разберем кой трябва да стане наследник? Интуитивно е ясно, че това е възел в дървото, ключът на който е следващият по големина от премахнатия възел. Алгоритъмът е следният. Трябва да преминем към неговия десен потомък (винаги към десния, тъй като вече беше споменато, че ключът на наследника е по-голям от ключа на премахнатия възел), а след това да преминем по веригата на левите потомци на този десен потомък. В примера, трябва да преминем към възел с ключ 35, а след това да преминем надолу по веригата на левите му потомци — в този случай, тази верига се състои само от възел с ключ 30. Строго погледнато, търсим най-малкия възел в набора от възли, по-големи от търсения възел.
Код на метода за намиране на наследника:
public Node getSuccessor(Node deleteNode) {
Node parentSuccessor = deleteNode; // родител на наследника
Node successor = deleteNode; // наследник
Node 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;
}
Пълният код на метода delete:
public boolean delete(int deleteKey) {
Node current = root;
Node 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 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 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;
}
Сложността — O(log(n))
Симетричен обход
Обход — посещение на всеки връх на дървото с цел да се направи нещо с него.
Алгоритъм на рекурсивния симетричен обход:
- Направете действие с лявото потомство
- Направете действие със себе си
- Направете действие с дясното потомство
Код:
public void inOrder(Node current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Тук може да е всичко, което искате
inOrder(current.getRightChild());
}
}
Заключение
Накрая! Ако нещо не съм обяснил или имате коментари, очаквам ги. Както обещах, предлагам целия код.
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.
Увеличаване до O(n)
Мнозина от вас вероятно забелязаха: какво ще стане, ако направим така, че дървото да стане несбалансирано? Например, да поставяме в дървото възли с нарастващи ключове: 1,2,3,4,5,6… Тогава дървото ще заприлича на свързан списък. И да, дървото ще загуби своята дървовидна структура и следователно, ефективността на достъпа до данни. Сложността на операциите за търсене, вмъкване и изтриване ще стане такава, каквато е при свързан списък: O(n). Именно в това се проявява един от най-важните, според мен, недостатъци на бинарните дървета.
Само регистрирани потребители могат да участват в анкетата. , моля.
Не съм много отдавна на Хабра и бих искал да знам, на какви теми бихте искали да видите повече статии?
Структури от данни
Алгоритми (ДП, рекурсия, компресия на данни и т.н.)
Приложение на структурите от данни и алгоритмите в реалния живот
Програмиране на Android приложения на Java
Програмиране на уеб приложения на Java
Гласували 2 потребители. Въздържали се 1 потребител.
Източник: habr.com
