Predigra
Ta članek govori o binarnih iskalnih drevesih. Pred kratkim sem napisal članek o Tam nisem posvečal veliko pozornosti binarnim drevesom, ker metode iskanja, vstavljanja in brisanja niso bile pomembne. Zdaj sem se odločil napisati članek o drevesih. Začnimo.
Drevo je podatkovna struktura, sestavljena iz vozlišč, povezanih z robovi. Lahko rečemo, da je drevo poseben primer grafa. Tukaj je primer drevesa:
To ni binarno iskalno drevo! Vse je razrezano!
Terminologija
koren
Drevesna korenina - to je njegovo najvišje vozlišče. V primeru je to vozlišče A. V drevesu lahko samo ena pot vodi od korena do katerega koli drugega vozlišča! Pravzaprav lahko vsako vozlišče obravnavamo kot koren poddrevesa, ki ustreza temu vozlišču.
Starši/potomci
Vsa vozlišča razen korena imajo točno en rob, ki vodi do drugega vozlišča. Pokliče se vozlišče, ki se nahaja nad trenutnim starš to vozlišče. Pokliče se vozlišče, ki se nahaja pod trenutnim in je z njim povezano potomec to vozlišče. Uporabimo primer. Vzemimo vozlišče B, potem bo njegov nadrejeni vozlišče A, njegovi otroci pa bodo vozlišča D, E in F.
List
Vozlišče, ki nima otrok, se bo imenovalo list drevesa. V primeru bodo listi vozlišča D, E, F, G, I, J, K.
To je osnovna terminologija. O drugih konceptih bomo še razpravljali. Binarno drevo je torej drevo, v katerem vsako vozlišče ne bo imelo več kot dva otroka. Kot ste uganili, drevo iz primera ne bo binarno, ker imata vozlišči B in H več kot dva otroka. Tukaj je primer binarnega drevesa:
Vozlišča drevesa lahko vsebujejo poljubne informacije. Binarno iskalno drevo je binarno drevo, ki ima naslednje lastnosti:
- Tako levo kot desno poddrevo sta binarna iskalna drevesa.
- Vsa vozlišča levega poddrevesa poljubnega vozlišča X imajo vrednosti podatkovnega ključa manjše od vrednosti podatkovnega ključa samega vozlišča X.
- Vsa vozlišča v desnem poddrevesu poljubnega vozlišča X imajo vrednosti podatkovnega ključa, ki so večje ali enake vrednosti podatkovnega ključa samega vozlišča X.
Ključ — katera koli značilnost vozlišča (na primer številka). Ključ je potreben, da lahko najdete element drevesa, ki mu ta ključ ustreza. Primer binarnega iskalnega drevesa:
Drevesni pogled
Ko bomo napredovali, bom zagotovil nekaj (morda nepopolnih) delov kode za izboljšanje vašega razumevanja. Celotna koda bo na koncu članka.
Drevo je sestavljeno iz vozlišč. Struktura vozlišča:
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;
}
//...остальные методы узла
}
Vsako vozlišče ima dva otroka (povsem možno je, da bodo otroci leftChild in/ali rightChild vsebovali ničelno vrednost). Verjetno ste ugotovili, da so v tem primeru številski podatki podatki, shranjeni v vozlišču; ključ — ključ vozlišča.
Razvrstili smo vozel, zdaj pa se pogovorimo o perečih težavah z drevesi. V nadaljevanju bom z besedo »drevo« mislil na koncept binarnega iskalnega drevesa. Binarna drevesna struktura:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Potrebujemo samo koren drevesa kot polje razreda, ker lahko iz korena z uporabo metod getLeftChild() in getRightChild() pridete do katerega koli vozlišča v drevesu.
Algoritmi v drevesu
iskanje
Recimo, da imate izdelano drevo. Kako najti element s ključnim ključem? Zaporedoma se morate premakniti od korena navzdol po drevesu in primerjati vrednost ključa s ključem naslednjega vozlišča: če je ključ manjši od ključa naslednjega vozlišča, pojdite na levega potomca vozlišča, če je večji, na desno, če sta ključa enaka, je želeno vozlišče najdeno! Ustrezna koda:
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;
}
Če tok postane nič, je iskanje doseglo konec drevesa (na konceptualni ravni ste na neobstoječem mestu v drevesu - potomec lista).
Oglejmo si učinkovitost iskalnega algoritma na uravnoteženem drevesu (drevo, v katerem so vozlišča porazdeljena bolj ali manj enakomerno). Potem bo učinkovitost iskanja O(log(n)), logaritem pa osnova 2. Poglejte: če je v uravnoteženem drevesu n elementov, potem to pomeni, da bo log(n) na ravni osnove 2 drevo. In pri iskanju se v enem koraku cikla spustite eno raven nižje.
vstavite
Če dojamete bistvo iskanja, vam razumevanje vstavljanja ne bo težko. Samo spustiti se morate na list drevesa (v skladu s pravili spuščanja, opisanimi v iskanju) in postati njegov potomec - levo ali desno, odvisno od ključa. Izvedba:
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;
}
}
}
}
}
V tem primeru je poleg trenutnega vozlišča potrebno shraniti tudi podatke o staršu trenutnega vozlišča. Ko tok postane enak nič, bo nadrejena spremenljivka vsebovala list, ki ga potrebujemo.
Učinkovitost vstavljanja bo očitno enaka kot pri iskanju - O(log(n)).
Brisanje
Odstranjevanje je najtežji poseg, ki ga bo treba izvesti na drevesu. Jasno je, da bomo morali najprej poiskati element, ki ga bomo izbrisali. Toda kaj potem? Če njegovo referenco preprosto nastavimo na nič, bomo izgubili informacije o poddrevesu, katerega koren je to vozlišče. Metode odstranjevanja dreves so razdeljene na tri primere.
Prvi primer. Vozlišče, ki se briše, nima otrok
Če vozlišče, ki ga brišete, nima otrok, potem to pomeni, da je list. Zato lahko preprosto nastavite polja leftChild ali rightChild njegovega nadrejenega elementa na nič.
Drugi primer. Vozlišče, ki ga želite izbrisati, ima enega podrejenega
Tudi ta primer ni zelo zapleten. Vrnimo se k našemu primeru. Recimo, da moramo izbrisati element s ključem 14. Strinjamo se, da ker je to desni potomec vozlišča s ključem 10, bo imel kateri koli od njegovih potomcev (v tem primeru desni) ključ, večji od 10, tako da ga lahko preprosto "izreže" iz drevesa in nadrejenega poveže neposredno s podrejenim vozliščem, ki se briše, tj. povežite vozlišče s ključem 10 na vozlišče 13. Situacija bi bila podobna, če bi bilo treba izbrisati vozlišče, ki je levi otrok svojega nadrejenega. Pomislite sami - natančna analogija.
Tretji primer. Vozlišče ima dva otroka
Najtežji primer. Poglejmo nov primer.
Iskanje naslednika
Recimo, da moramo izbrisati vozlišče s ključem 25. Koga naj postavimo na njegovo mesto? Eden od njegovih sledilcev (potomcev ali potomcev potomcev) mora postati naslednik(tisti, ki bo prevzel mesto odstranjenega vozlišča).
Kako razumeti, kdo naj postane naslednik? Intuitivno je to vozlišče v drevesu, katerega ključ je naslednji največji od vozlišča, ki se briše. Algoritem je naslednji. Morate iti do njegovega desnega potomca (vedno do desnega, ker je bilo že rečeno, da je ključ naslednika večji od ključa vozlišča, ki se briše), nato pa iti skozi verigo levih potomcev tega desnega potomca . V primeru bi šli do vozlišča s ključem 35 in se nato spustili do lista skozi verigo njegovih levih otrok - v tem primeru je ta veriga sestavljena samo iz vozlišča s ključem 30. Strogo gledano iščemo za najmanjše vozlišče v nizu vozlišč, večje od tistega, ki ga iščemo vozlišče.
Koda metode iskanja naslednika:
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;
}
Celotna koda za metodo brisanja:
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;
}
Kompleksnost je mogoče približati na O(log(n)).
Iskanje maksimuma/minimuma v drevesu
Očitno je, kako najti najmanjšo/največjo vrednost v drevesu - morate se zaporedno premikati po verigi levih/desnih elementov drevesa; ko pridete do lista, bo to najmanjši/največji element.
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;
}
Kompleksnost - O(log(n))
Simetrična obvodnica
Traversal obišče vsako vozlišče drevesa, da z njim izvede nekaj dejanj.
Algoritem rekurzivnega simetričnega prehoda:
- Izvedite dejanje na levem otroku
- Naredite akcijo sami s seboj
- Izvedite dejanje na pravem otroku
Koda:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Zaključek
Končno! Če nisem ničesar pojasnil ali imate kakršne koli pripombe, jih pustite v komentarjih. Kot obljubljeno, nudim celotno kodo.
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
Degeneracija na O(n)
Mnogi od vas ste morda opazili: kaj pa, če naredite drevo neuravnoteženo? V drevo na primer postavite vozlišča z naraščajočimi ključi: 1,2,3,4,5,6 ... Potem bo drevo nekoliko podobno povezanemu seznamu. In ja, drevo bo izgubilo svojo drevesno strukturo in s tem učinkovitost dostopa do podatkov. Kompleksnost operacij iskanja, vstavljanja in brisanja bo postala enaka kot pri povezanem seznamu: O(n). To je po mojem mnenju ena najpomembnejših pomanjkljivosti binarnih dreves.
V anketi lahko sodelujejo samo registrirani uporabniki. , prosim.
Nisem bil dolgo na vozlišču in rad bi vedel, katere članke o katerih temah bi radi videli več?
-
Podatkovne strukture
-
Algoritmi (DP, rekurzija, stiskanje podatkov itd.)
-
Uporaba podatkovnih struktur in algoritmov v realnem življenju
-
Programiranje aplikacij za Android v Javi
-
Programiranje spletnih aplikacij v Javi
Glasovali so 2 uporabniki. 1 uporabnik se je vzdržal.
Vir: www.habr.com