Прелуде
Овај чланак је о стаблима бинарног претраживања. Недавно сам написао чланак о Тамо нисам баш обраћао пажњу на бинарна стабла, јер методе тражења, уметања, брисања нису биле релевантне. Сада сам одлучио да напишем чланак о дрвећу. Можда ћемо почети.
Стабло је структура података која се састоји од чворова повезаних ивицама. Можемо рећи да је дрво посебан случај графа. Ево примера стабла:
Ово није бинарно стабло претраге! Све је испод реза!
Терминологија
Роот
Корен дрвета је највиши чвор. У примеру, ово је чвор А. У стаблу, само једна путања може водити од корена до било ког другог чвора! У ствари, било који чвор се може сматрати кореном подстабла које одговара овом чвору.
Родитељи/потомци
Сви чворови осим корена имају тачно једну ивицу која води до другог чвора. Позива се чвор изнад тренутног чвора родитељ овај чвор. Чвор који се налази испод тренутног и повезан са њим се зове потомак овај чвор. Узмимо пример. Узмимо чвор Б, тада ће његов родитељ бити чвор А, а потомци ће бити чворови Д, Е и Ф.
Леаф
Чвор који нема деце назива се лист дрвета. У примеру, чворови Д, Е, Ф, Г, И, Ј, К ће бити листови.
Ово је основна терминологија. О другим концептима ће бити речи касније. Дакле, бинарно стабло је дрво у коме сваки чвор неће имати више од два детета. Као што сте претпоставили, дрво из примера неће бити бинарно, јер чворови Б и Х имају више од два детета. Ево примера бинарног стабла:
Чворови стабла могу садржати било коју информацију. Бинарно стабло претраге је бинарно стабло које има следећа својства:
- И лево и десно подстабло су бинарно стабло претраге.
- Сви чворови левог подстабла произвољног чвора Кс имају вредности кључа података мање од вредности кључа података самог чвора Кс.
- Сви чворови десног подстабла произвољног чвора Кс имају вредности кључа података веће или једнаке вредности кључа података самог чвора Кс.
Кључ - неке карактеристике чвора (на пример, број). Кључ је потребан да би се могао пронаћи елемент стабла коме овај кључ одговара. Пример стабла бинарне претраге:
поглед на дрво
Како будем напредовао, укључићу неке (можда непотпуне) делове кода како бих побољшао ваше разумевање. Комплетан код ће бити на крају чланка.
Дрво се састоји од чворова. Структура чвора:
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;
}
//...остальные методы узла
}
Сваки чвор има два детета (сасвим је могуће да ће деца лефтЦхилд и/или ригхтЦхилд бити нулл). Вероватно сте разумели да су у овом случају подаци о броју подаци ускладиштени у чвору; кључ - кључ чвора.
Схватили смо чвор, хајде сада да причамо о горућим проблемима у вези са дрвећем. Овде и испод, реч "дрво" ће значити концепт бинарног стабла претраге. Структура бинарног стабла:
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;
}
Ако струја постане нулта, онда је итерација стигла до краја стабла (на концептуалном нивоу, налазите се на непостојећем месту у стаблу - дете листа).
Размотрите ефикасност алгоритма претраживања на балансираном стаблу (стабло у којем су чворови распоређени мање-више равномерно). Тада ће ефикасност претраживања бити О(лог(н)), а логаритам основе 2. Видите: ако постоји н елемената у балансираном стаблу, то значи да ће постојати лог(н) база 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;
}
}
}
}
}
У овом случају, поред тренутног чвора, потребно је чувати и информације о родитељу тренутног чвора. Када цуррент постане нулл, родитељска варијабла ће садржати лист који нам је потребан.
Ефикасност уметања ће очигледно бити иста као и код претраге - О(лог(н)).
Брисање
Брисање је најсложенија операција која ће се морати обавити са стаблом. Јасно је да ће прво бити потребно пронаћи елемент који ћемо уклонити. Али шта онда? Ако једноставно поставимо његову референцу на нулл, онда ћемо изгубити информације о подстаблу чији је корен овај чвор. Методе уклањања дрвећа подељене су у три случаја.
Први случај. Чвор који треба уклонити нема деце.
Ако чвор који се брише нема деце, то значи да је то лист. Стога, можете једноставно поставити поља лефтЦхилд или ригхтЦхилд његовог родитеља на нулл.
Други случај. Чвор који треба уклонити има једно дете
Овај случај такође није много тежак. Вратимо се нашем примеру. Претпоставимо да треба да избришемо елемент са кључем 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;
}
Комплетан код методе брисања:
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;
}
Сложеност се може апроксимирати на О(лог(н)).
Проналажење максимума/минимума у стаблу
Очигледно, како пронаћи минималну / максималну вредност у стаблу - морате узастопно проћи кроз ланац левих / десних елемената стабла, респективно; када дођете до листа, то ће бити минимални/максимални елемент.
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 void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Закључак
Коначно! Ако нешто нисам објаснио или имам коментаре, онда чекам у коментарима. Као што је обећано, ево комплетног кода.
Ноде.јава:
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;
}
}
БинариТрее.јава:
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());
}
}
}
ПС
Дегенерација у О(н)
Многи од вас су можда приметили: шта ако учините да дрво постане неуравнотежено? На пример, ставите чворове у стабло помоћу тастера за повећање: 1,2,3,4,5,6... Тада ће дрво донекле подсећати на повезану листу. И да, дрво ће изгубити структуру стабла, а самим тим и ефикасност приступа подацима. Сложеност операција претраживања, уметања и брисања ће постати иста као код повезане листе: О(н). Ово је један од најважнијих, по мом мишљењу, недостатака бинарних стабала.
Само регистровани корисници могу учествовати у анкети. , Добродошао си.
Нисам био на Хабреу доста дуго, и волео бих да знам које чланке о којим темама бисте волели да видите више?
-
Структуре података
-
Алгоритми (ДП, рекурзија, компресија података, итд.)
-
Примена структура података и алгоритама у реалном животу
-
Програмирање андроид апликација у Јави
-
Јава програмирање веб апликација
2 корисника гласало. 1 корисник је био уздржан.
Извор: ввв.хабр.цом