predohra
Tento článok je o binárnych vyhľadávacích stromoch. Nedávno som napísal článok o Tam som sa binárnym stromom veľmi nevenoval, pretože metódy vyhľadávania, vkladania, mazania neboli relevantné. Teraz som sa rozhodol napísať článok o stromoch. Možno začneme.
Strom je dátová štruktúra pozostávajúca z uzlov spojených hranami. Môžeme povedať, že strom je špeciálny prípad grafu. Tu je príklad stromu:
Toto nie je binárny vyhľadávací strom! Všetko je pod rezom!
terminológie
koreň
Koreň stromu je najvyšší uzol. V príklade je to uzol A. V strome môže z koreňa do akéhokoľvek iného uzla viesť iba jedna cesta! V skutočnosti môže byť akýkoľvek uzol považovaný za koreň podstromu zodpovedajúceho tomuto uzlu.
Rodičia/potomkovia
Všetky uzly okrem koreňa majú presne jednu hranu vedúcu k inému uzlu. Zavolá sa uzol nad aktuálnym uzlom rodič tento uzol. Volá sa uzol, ktorý sa nachádza pod aktuálnym a je k nemu pripojený potomok tento uzol. Vezmime si príklad. Vezmite uzol B, jeho rodič bude uzol A a jeho potomkovia uzly D, E a F.
list
Uzol, ktorý nemá potomkov, sa nazýva list stromu. V príklade uzly D, E, F, G, I, J, K budú listy.
Toto je základná terminológia. O ďalších konceptoch sa bude diskutovať neskôr. Binárny strom je teda strom, v ktorom každý uzol nebude mať viac ako dve deti. Ako ste uhádli, strom z príkladu nebude binárny, pretože uzly B a H majú viac ako dve deti. Tu je príklad binárneho stromu:
Uzly stromu môžu obsahovať akékoľvek informácie. Binárny vyhľadávací strom je binárny strom, ktorý má nasledujúce vlastnosti:
- Ľavý aj pravý podstrom sú binárne vyhľadávacie stromy.
- Všetky uzly ľavého podstromu ľubovoľného uzla X majú hodnoty kľúča údajov menšie ako hodnota kľúča údajov samotného uzla X.
- Všetky uzly pravého podstromu ľubovoľného uzla X majú hodnoty dátového kľúča väčšie alebo rovné hodnote dátového kľúča samotného uzla X.
kľúč - nejaká charakteristika uzla (napríklad číslo). Kľúč je potrebný na to, aby bolo možné nájsť prvok stromu, ktorému tento kľúč zodpovedá. Príklad binárneho vyhľadávacieho stromu:
stromový pohľad
Postupom času zahrniem niektoré (možno neúplné) časti kódu, aby som vám zlepšil porozumenie. Celý kód bude na konci článku.
Strom sa skladá z uzlov. Štruktúra uzla:
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;
}
//...остальные методы узла
}
Každý uzol má dve deti (je celkom možné, že deti leftChild a/alebo rightChild budú nulové). Pravdepodobne ste pochopili, že v tomto prípade číselné údaje sú údaje uložené v uzle; kľúč - kľúč uzla.
Prišli sme na uzol, teraz sa porozprávajme o naliehavých problémoch so stromami. Ďalej bude slovo "strom" znamenať koncept binárneho vyhľadávacieho stromu. Binárna stromová štruktúra:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Ako pole triedy potrebujeme iba koreň stromu, pretože z koreňa sa pomocou metód getLeftChild() a getRightChild() dostanete do ľubovoľného uzla stromu.
Stromové algoritmy
vyhľadávanie
Povedzme, že máte postavený strom. Ako nájsť prvok pomocou kľúča? Musíte sa postupne pohybovať od koreňa nadol v strome a porovnať hodnotu kľúča s kľúčom nasledujúceho uzla: ak je kľúč menší ako kľúč ďalšieho uzla, prejdite na ľavého potomka uzla, ak je viac - vpravo, ak sú kľúče rovnaké - požadovaný uzol sa nájde! Príslušný kód:
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;
}
Ak sa prúd stane nulovým, potom iterácia dosiahla koniec stromu (na koncepčnej úrovni ste na neexistujúcom mieste v strome - dieťa listu).
Zvážte efektívnosť vyhľadávacieho algoritmu na vyváženom strome (strome, v ktorom sú uzly rozdelené viac-menej rovnomerne). Potom bude efektivita vyhľadávania O(log(n)) a logaritmus so základom 2. Pozri: ak je vo vyváženom strome n prvkov, znamená to, že v strome budú úrovne log(n) so základom 2. A pri hľadaní na jeden krok cyklu idete o úroveň nižšie.
vložiť
Ak ste pochopili podstatu hľadania, nebude pre vás ťažké pochopiť vkladanie. Stačí zísť dolu k listu stromu (podľa pravidiel zostupu opísaných vo vyhľadávaní) a stať sa jeho potomkom - vľavo alebo vpravo, v závislosti od kľúča. Implementácia:
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 tomto prípade je potrebné okrem aktuálneho uzla uložiť aj informácie o rodičovi aktuálneho uzla. Keď sa aktuálna stane nulovou, rodičovská premenná bude obsahovať hárok, ktorý potrebujeme.
Účinnosť vkladania bude samozrejme rovnaká ako účinnosť vyhľadávania - O(log(n)).
Odstránenie
Odstránenie je najzložitejšia operácia, ktorú bude potrebné vykonať so stromom. Je jasné, že najskôr bude potrebné nájsť prvok, ktorý ideme odstrániť. Ale čo potom? Ak jednoducho nastavíme jeho odkaz na hodnotu null, stratíme informácie o podstrome, ktorého koreňom je tento uzol. Metódy odstraňovania stromov sú rozdelené do troch prípadov.
Prvý prípad. Uzol, ktorý sa má odstrániť, nemá žiadne deti.
Ak uzol, ktorý sa má odstrániť, nemá potomkov, znamená to, že ide o list. Preto môžete jednoducho nastaviť pole leftChild alebo rightChild jeho rodiča na hodnotu null.
Druhý prípad. Uzol, ktorý sa má odstrániť, má jedného potomka
Tento prípad tiež nie je veľmi ťažký. Vráťme sa k nášmu príkladu. Predpokladajme, že potrebujeme vymazať prvok s kľúčom 14. Súhlaste s tým, že keďže ide o správneho potomka uzla s kľúčom 10, potom ktorýkoľvek z jeho potomkov (v tomto prípade ten pravý) bude mať kľúč väčší ako 10, takže ho môže jednoducho „vystrihnúť“ zo stromu a spojiť rodiča priamo s potomkom uzla, ktorý sa odstraňuje, t.j. prepojte uzol s kľúčom 10 s uzlom 13. Situácia by bola podobná, keby sme museli vymazať uzol, ktorý je ľavým potomkom svojho rodiča. Premýšľajte o tom sami - presná analógia.
Tretí prípad. Node má dve deti
Najťažší prípad. Pozrime sa na nový príklad.
Hľadať nástupcu
Povedzme, že potrebujeme odstrániť uzol kľúčom 25. Koho umiestnime na jeho miesto? Jeden z jeho nasledovníkov (potomkov alebo potomkov potomkov) sa musí stať nástupcu(ten, kto zaujme miesto odstráneného uzla).
Ako viete, kto by mal byť nástupcom? Intuitívne je to uzol v strome, ktorého kľúč je ďalší najväčší z uzla, ktorý sa odstraňuje. Algoritmus je nasledujúci. Musíte prejsť k jeho pravému potomkovi (vždy k pravému, pretože už bolo povedané, že kľúč nástupcu je väčší ako kľúč vymazaného uzla) a potom prejsť reťazcom ľavých potomkov tohto práva. dieťa. V príklade musíme prejsť do uzla s kľúčom 35 a potom prejsť reťazou jeho ľavých potomkov na list - v tomto prípade tento reťazec pozostáva iba z uzla s kľúčom 30. Presne povedané, hľadáme najmenší uzol v množine uzlov väčší ako požadovaný uzol.
Kód nasledujúcej metódy vyhľadávania:
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;
}
Úplný kód metódy odstránenia:
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;
}
Zložitosť možno priblížiť k O(log(n)).
Nájdenie maxima/minima v strome
Je zrejmé, že ako nájsť minimálnu / maximálnu hodnotu v strome - musíte postupne prejsť reťazcom ľavých / pravých prvkov stromu; keď sa dostanete k listu, bude to minimálny/maximálny prvok.
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;
}
Zložitosť - O(log(n))
Symetrický bypass
Traversal je návšteva každého uzla stromu s cieľom niečo s ním urobiť.
Rekurzívny symetrický traverzálny algoritmus:
- Vykonajte akciu na ľavom dieťati
- Urobte akciu sami so sebou
- Urobte akciu na správnom dieťati
Kód:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Záver
Konečne! Ak som niečo nevysvetlil alebo mám nejaké pripomienky, čakám v komentároch. Ako som sľúbil, tu je úplný kód.
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
Degenerácia na O(n)
Mnohí z vás si možno všimli: čo ak spôsobíte, že strom bude nevyvážený? Napríklad vložte uzly do stromu so zvyšujúcimi sa kľúčmi: 1,2,3,4,5,6... Potom bude strom trochu pripomínať prepojený zoznam. A áno, strom stratí svoju stromovú štruktúru a tým aj efektivitu prístupu k údajom. Zložitosť operácií vyhľadávania, vkladania a odstraňovania bude rovnaká ako pri prepojenom zozname: O(n). Toto je podľa mňa jedna z najdôležitejších nevýhod binárnych stromov.
Do prieskumu sa môžu zapojiť iba registrovaní užívatelia. Prosím.
Dlho som nebol na Habré a zaujímalo by ma, aké články na aké témy by ste chceli vidieť viac?
-
Dátové štruktúry
-
Algoritmy (DP, rekurzia, kompresia dát atď.)
-
Aplikácia dátových štruktúr a algoritmov v reálnom živote
-
Programovanie aplikácií pre Android v jazyku Java
-
Programovanie webových aplikácií Java
Hlasovali 2 používatelia. 1 používateľ sa zdržal hlasovania.
Zdroj: www.habr.com