Předehra
Tento článek je o binárních vyhledávacích stromech. Nedávno jsem psal článek o Tam jsem se binárním stromům opravdu nevěnoval, protože metody vyhledávání, vkládání, mazání nebyly relevantní. Nyní jsem se rozhodl napsat článek o stromech. Možná začneme.
Strom je datová struktura sestávající z uzlů spojených hranami. Můžeme říci, že strom je speciální případ grafu. Zde je příklad stromu:
Toto není binární vyhledávací strom! Všechno je pod řezem!
Terminologie
kořen
Kořen stromu je nejvyšší uzel. V příkladu se jedná o uzel A. Ve stromu může z kořene do libovolného jiného uzlu vést pouze jedna cesta! Ve skutečnosti lze jakýkoli uzel považovat za kořen podstromu odpovídajícího tomuto uzlu.
Rodiče/potomci
Všechny uzly kromě kořene mají právě jednu hranu vedoucí k dalšímu uzlu. Zavolá se uzel nad aktuálním uzlem rodič tento uzel. Zavolá se uzel umístěný pod aktuálním a k němu připojený potomek tento uzel. Vezměme si příklad. Vezměte uzel B, jeho rodič bude uzel A a jeho potomci budou uzly D, E a F.
List
Uzel, který nemá žádné potomky, se nazývá list stromu. V příkladu budou uzly D, E, F, G, I, J, K listy.
Toto je základní terminologie. Další koncepty budou diskutovány později. Binární strom je tedy strom, ve kterém každý uzel nebude mít více než dva potomky. Jak jste uhodli, strom z příkladu nebude binární, protože uzly B a H mají více než dvě děti. Zde je příklad binárního stromu:
Uzly stromu mohou obsahovat libovolné informace. Binární vyhledávací strom je binární strom, který má následující vlastnosti:
- Levý i pravý podstrom jsou binární vyhledávací stromy.
- Všechny uzly levého podstromu libovolného uzlu X mají hodnoty datového klíče menší než hodnota datového klíče samotného uzlu X.
- Všechny uzly pravého podstromu libovolného uzlu X mají hodnoty datového klíče větší nebo rovné hodnotě datového klíče samotného uzlu X.
Klíč - nějaká charakteristika uzlu (například číslo). Klíč je potřeba k tomu, aby bylo možné najít prvek stromu, kterému tento klíč odpovídá. Příklad binárního vyhledávacího stromu:
stromový pohled
Jak budu pokračovat, zahrnu některé (možná neúplné) části kódu, abych vám lépe porozuměl. Celý kód bude na konci článku.
Strom se skládá z uzlů. Struktura uzlu:
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ý uzel má dva potomky (je docela možné, že děti leftChild a/nebo rightChild budou mít hodnotu null). Pravděpodobně jste pochopili, že v tomto případě číselná data jsou data uložená v uzlu; klíč - klíč uzlu.
Přišli jsme na uzel, teď si promluvme o naléhavých problémech stromů. Zde a níže bude slovo „strom“ znamenat koncept binárního vyhledávacího stromu. Binární stromová struktura:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Jako pole třídy potřebujeme pouze kořen stromu, protože z kořene se pomocí metod getLeftChild() a getRightChild() dostanete do libovolného uzlu stromu.
Stromové algoritmy
Vyhledávání
Řekněme, že máte postavený strom. Jak najít prvek pomocí klíčového klíče? Musíte se postupně přesunout od kořene dolů ve stromu a porovnat hodnotu klíče s klíčem dalšího uzlu: pokud je klíč menší než klíč dalšího uzlu, přejděte k levému potomkovi uzlu, pokud je více - vpravo, pokud jsou klíče stejné - požadovaný uzel je nalezen! Pří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;
}
Pokud se proud stane nulovým, pak iterace dosáhla konce stromu (na koncepční úrovni jste na neexistujícím místě ve stromu - dítě listu).
Zvažte efektivitu vyhledávacího algoritmu na vyváženém stromě (stromu, ve kterém jsou uzly rozmístěny víceméně rovnoměrně). Účinnost vyhledávání pak bude O(log(n)) a logaritmus se základem 2. Viz: pokud je ve vyváženém stromu n prvků, znamená to, že bude existovat log(n) úrovně stromu se základem 2. A při hledání na jeden krok cyklu sestoupíte o jednu úroveň dolů.
vložit
Pokud jste pochopili podstatu hledání, pak pro vás nebude těžké vložení pochopit. Stačí sestoupit k listu stromu (podle pravidel sestupu popsaných ve vyhledávání) a stát se jeho potomkem - vlevo nebo vpravo, v závislosti na klíči. Implementace:
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 případě je nutné kromě aktuálního uzlu uložit i informace o rodiči aktuálního uzlu. Když se aktuální stane null, rodičovská proměnná bude obsahovat list, který potřebujeme.
Účinnost vkládání bude samozřejmě stejná jako účinnost vyhledávání - O(log(n)).
Odstranění
Odstranění je nejsložitější operace, kterou bude třeba provést pomocí stromu. Je jasné, že nejprve bude nutné najít prvek, který se chystáme odstranit. Ale co potom? Pokud jednoduše nastavíme jeho odkaz na null, pak ztratíme informace o podstromu, jehož kořenem je tento uzel. Metody odstraňování stromů jsou rozděleny do tří případů.
První případ. Uzel, který má být odstraněn, nemá žádné potomky.
Pokud uzel, který má být odstraněn, nemá žádné potomky, znamená to, že se jedná o list. Proto můžete jednoduše nastavit pole leftChild nebo rightChild jeho rodiče na hodnotu null.
Druhý případ. Uzel, který má být odebrán, má jednoho potomka
Tento případ také není příliš obtížný. Vraťme se k našemu příkladu. Předpokládejme, že potřebujeme odstranit prvek s klíčem 14. Souhlaste s tím, že jelikož je to správný potomek uzlu s klíčem 10, pak kterýkoli z jeho potomků (v tomto případě ten pravý) bude mít klíč větší než 10, takže lze jej snadno „vystřihnout“ ze stromu a spojit rodiče přímo s potomkem mazaného uzlu, tzn. připojte uzel s klíčem 10 k uzlu 13. Situace by byla podobná, kdybychom museli odstranit uzel, který je levým potomkem svého rodiče. Přemýšlejte o tom sami - přesné přirovnání.
Třetí případ. Node má dvě děti
Nejtěžší případ. Podívejme se na nový příklad.
Hledat nástupce
Řekněme, že potřebujeme odstranit uzel s klíčem 25. Koho umísťujeme na jeho místo? Jeden z jeho následovníků (potomků nebo potomků potomků) se musí stát nástupce(ten, kdo nastoupí na místo odstraněného uzlu).
Jak víte, kdo by měl být nástupcem? Intuitivně se jedná o uzel ve stromu, jehož klíč je další největší z uzlu, který je odstraňován. Algoritmus je následující. Musíte jít k jeho pravému potomkovi (vždy k tomu pravému, protože již bylo řečeno, že klíč nástupce je větší než klíč mazaného uzlu), a pak projít řetězcem levých potomků tohoto práva. dítě. V příkladu musíme přejít k uzlu s klíčem 35 a pak sejít po řetězci jeho levých potomků na list - v tomto případě se tento řetězec skládá pouze z uzlu s klíčem 30. Přesně řečeno, hledáme nejmenší uzel v množině uzlů větší než požadovaný uzel.
Kód následující metody vyhledávání:
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 metody odstranění:
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;
}
Složitost lze přiblížit k O(log(n)).
Nalezení maxima/minima ve stromu
Je zřejmé, jak najít minimální / maximální hodnotu ve stromu - musíte postupně procházet řetězcem levých / pravých prvků stromu; když se dostanete k listu, bude to minimální/maximální prvek.
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;
}
Složitost - O(log(n))
Symetrický bypass
Traversal je návštěva každého uzlu stromu s cílem něco s ním udělat.
Rekurzivní symetrický traverzální algoritmus:
- Proveďte akci na levém dítěti
- Udělejte se sebou akci
- Udělejte akci na správném dítěti
Kód:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Závěr
Konečně! Pokud jsem něco nevysvětlil nebo mám nějaké připomínky, tak čekám v komentářích. Jak jsme slíbili, zde je kompletní 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
Degenerace na O(n)
Mnozí z vás si možná všimli: co když způsobíte, že strom bude nevyvážený? Například do stromu vložte uzly s rostoucími klíči: 1,2,3,4,5,6... Pak bude strom trochu připomínat propojený seznam. A ano, strom ztratí svou stromovou strukturu a tím i efektivitu přístupu k datům. Složitost operací vyhledávání, vkládání a mazání bude stejná jako u propojeného seznamu: O(n). To je podle mého názoru jedna z nejdůležitějších nevýhod binárních stromů.
Průzkumu se mohou zúčastnit pouze registrovaní uživatelé. , prosím.
Dlouho jsem na Habré nebyl a zajímalo by mě, jaké články na jaká témata byste rádi viděli víc?
-
Datové struktury
-
Algoritmy (DP, rekurze, komprese dat atd.)
-
Aplikace datových struktur a algoritmů v reálném životě
-
Programování aplikací pro Android v Javě
-
Programování webových aplikací Java
2 uživatelé hlasovali. 1 uživatel se zdržel hlasování.
Zdroj: www.habr.com