Прелюдія
Ця стаття присвячена бінарним деревам пошуку. Нещодавно робив статтю про Там я не дуже звертав увагу на бінарні дерева, бо методи пошуку, вставки, видалення не були актуальними. Тепер вирішив написати статтю саме про дерева. Мабуть, почнемо.
Дерево - структура даних, що складається з вузлів, з'єднаних ребрами. Можна сміливо сказати, що дерево — окремий випадок графа. Ось приклад дерева:
Це не бінарне дерево пошуку! Все під кат!
Термінологія
корінь
Корінь дерева — це найвищий його вузол. У прикладі це вузол 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<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 стане рівним null, у змінній parent лежатиме потрібний нам лист.
Ефективність вставки, очевидно, буде такою самою, як і у пошуку — O(log(n)).
Видалення
Видалення – найскладніша операція, яку треба буде провести з деревом. Зрозуміло, що спочатку потрібно буде знайти елемент, який ми збираємося видаляти. Але що ж потім? Якщо просто привласнити його посилання значення null, ми втратимо інформацію про поддереве, корінням якого є цей вузол. Методи видалення дерева поділяють на три випадки.
Перший випадок. Вузол, що видаляється, не має нащадків
Якщо видалений вузол немає нащадків, це означає, що він є листом. Отже, можна просто полям leftChild або rightChild його батька присвоїти значення null.
Другий випадок. Вузол, що видаляється, має одного нащадка
Цей випадок також не дуже складний. Повернемося до нашого прикладу. Припустимо, треба видалити елемент із ключем 14. Погодьтеся, що оскільки він — правий нащадок вузла з ключем 10, то будь-який його нащадок (в даному випадку правий) матиме ключ, більший за 10, тому можна легко його «вирізати» з дерева, а батька з'єднати безпосередньо з нащадком вузла, що видаляється, тобто. вузол з ключем 10 з'єднати з вузлом 13. Аналогічною була б ситуація, якби треба було видалити вузол, який є лівим нащадком свого батька. Подумайте про це самі – точна аналогія.
Третій випадок. Вузол має двох нащадків
Найбільш складний випадок. Розберемо на прикладі.
Пошук наступника
Припустимо, треба видалити вузол із ключем 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;
}
Повний код методу 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;
}
Складність може бути апроксимована до 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). У цьому й проявляється одне із найважливіших, мій погляд, недоліків бінарних дерев.
Тільки зареєстровані користувачі можуть брати участь в опитуванні. , будь ласка.
Я нещодавно на хабрі, і мені хотілося б знати, статті на які теми хотіли б ви бачити більше?
-
Структури даних
-
Алгоритми (ДП, рекурсія, стиск даних і т. д.)
-
Застосування структур даних та алгоритмів у реальному житті
-
Програмування android-додатків на Java
-
Програмування web-додатків на Java
Проголосували 2 користувача. Утримався 1 користувач.
Джерело: habr.com