Прэлюдыя
Гэты артыкул прысвечаны бінарным дрэвам пошуку. Нядаўна рабіў артыкул пра Там я не вельмі зважаў на бінарныя дрэвы, бо метады пошуку, устаўкі, выдаленні не былі актуальныя. Цяпер вырашыў напісаць артыкул менавіта пра дрэвы. Мабыць, пачнем.
Дрэва - структура дадзеных, якая складаецца з вузлоў, злучаных рэбрамі. Можна сказаць, што дрэва - прыватны выпадак графа. Вось прыклад дрэва:
Гэта не бінарнае дрэва пошуку! Усё пад кат!
тэрміналогія
корань
Корань дрэва - гэта самы верхні яго вузел. У прыкладзе - гэта вузел 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