bevezetés
Ez a cikk a bináris keresőfákról szól. Nemrég írtam egy cikket erről Ott nem igazán figyeltem a bináris fákra, mert a keresés, beillesztés, törlés módszerei nem voltak relevánsak. Most úgy döntöttem, hogy írok egy cikket a fákról. Talán kezdjük.
A fa olyan adatstruktúra, amely élekkel összekapcsolt csomópontokból áll. Azt mondhatjuk, hogy a fa a gráf speciális esete. Íme egy példa fa:
Ez nem egy bináris keresőfa! Minden a vágás alatt van!
terminológia
gyökér
Fa gyökér a legfelső csomópont. A példában ez az A csomópont. A fában csak egy út vezethet a gyökértől bármely másik csomóponthoz! Valójában bármely csomópont tekinthető az ehhez a csomóponthoz tartozó részfa gyökerének.
Szülők/utód
A gyökér kivételével minden csomópontnak pontosan egy éle van, amely egy másik csomóponthoz vezet. Az aktuális csomópont feletti csomópontot hívják szülő ezt a csomópontot. Az aktuális alatti és hozzá kapcsolódó csomópontot hívják leszármazott ezt a csomópontot. Vegyünk egy példát. Vegyük a B csomópontot, akkor a szülője az A csomópont, a gyermekei pedig a D, E és F csomópontok.
lap
Azt a csomópontot, amelynek nincs gyermeke, a fa levelének nevezik. A példában a D, E, F, G, I, J, K csomópontok levelek lesznek.
Ez az alapvető terminológia. A többi koncepcióról később lesz szó. Tehát a bináris fa olyan fa, amelyben minden csomópontnak legfeljebb két gyermeke lesz. Ahogy sejtette, a példából származó fa nem lesz bináris, mivel a B és H csomópontoknak kettőnél több gyermekük van. Íme egy példa egy bináris fára:
A fa csomópontjai bármilyen információt tartalmazhatnak. A bináris keresési fa olyan bináris fa, amely a következő tulajdonságokkal rendelkezik:
- A bal és a jobb oldali részfa egyaránt bináris keresési fa.
- Egy tetszőleges X csomópont bal oldali részfájának minden csomópontjának adatkulcsértéke kisebb, mint magának az X csomópontnak az adatkulcsértéke.
- Egy tetszőleges X csomópont jobb oldali részfájának minden csomópontjának adatkulcsértéke nagyobb vagy egyenlő, mint magának az X csomópont adatkulcsának az értéke.
kulcs - a csomópont néhány jellemzője (például egy szám). A kulcsra azért van szükség, hogy meg tudjuk találni a fa azon elemét, amelyhez ez a kulcs tartozik. Bináris keresési fa példa:
fanézet
Ahogy haladok, beleteszek néhány (talán hiányos) kódrészletet, hogy jobban megértsd. A teljes kód a cikk végén lesz.
A fa csomópontokból áll. Csomópont szerkezete:
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;
}
//...остальные методы узла
}
Minden csomópontnak két gyermeke van (nagyon lehetséges, hogy a leftChild és/vagy a rightChild gyermek nulla lesz). Valószínűleg megértette, hogy ebben az esetben a számadatok a csomópontban tárolt adatok; kulcs - csomópont kulcs.
Kitaláltuk a csomót, most beszéljünk a fákkal kapcsolatos sürgető problémákról. A továbbiakban a "fa" szó a bináris keresőfa fogalmát jelenti. Bináris fa szerkezet:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Osztálymezőként csak a fa gyökerére van szükségünk, mert a gyökérből a getLeftChild() és getRightChild() metódusok segítségével a fa bármely csomópontjához el lehet jutni.
Fa algoritmusok
Keresés
Tegyük fel, hogy van egy épített fája. Hogyan lehet elemet találni kulcskulccsal? Sorrendben kell mozognia a gyökértől lefelé a fán, és össze kell hasonlítania a kulcs értékét a következő csomópont kulcsával: ha a kulcs kisebb, mint a következő csomópont kulcsa, akkor menjen a csomópont bal leszármazottjához, ha több - jobbra, ha a kulcsok egyenlőek - a kívánt csomópont megtalálható! Vonatkozó 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;
}
Ha az áram nullává válik, akkor az iteráció elérte a fa végét (fogalmi szinten egy nem létező helyen vagy a fában - egy levél gyermekében).
Tekintsük a keresési algoritmus hatékonyságát kiegyensúlyozott fán (olyan fán, amelyben a csomópontok többé-kevésbé egyenletesen vannak elosztva). Ekkor a keresés hatékonysága O(log(n)), és a 2-es bázis logaritmus. Lásd: ha egy kiegyensúlyozott fában n elem van, akkor ez azt jelenti, hogy a fának lesz log(n) 2. bázisszintje. A keresésben pedig a ciklus egy lépéséért egy szinttel lejjebb megy.
helyezze
Ha felfogta a keresés lényegét, akkor nem lesz nehéz megértenie a beillesztést. Csak le kell mennie a fa levelére (a keresésben leírt származási szabályok szerint), és a leszármazottává kell válnia - balra vagy jobbra, a kulcstól függően. Végrehajtás:
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;
}
}
}
}
}
Ebben az esetben az aktuális csomóponton kívül az aktuális csomópont szülőjére vonatkozó információkat is tárolni kell. Amikor az aktuális nullává válik, a szülőváltozó tartalmazza a szükséges lapot.
A beillesztés hatékonysága nyilvánvalóan megegyezik a keresésével - O(log(n)).
Eltávolítás
A törlés a legösszetettebb művelet, amelyet egy fával kell végrehajtani. Nyilvánvaló, hogy először meg kell találni azt az elemet, amelyet eltávolítani fogunk. De akkor mi van? Ha egyszerűen nullára állítjuk a hivatkozását, akkor elveszítjük az információt arról a részfáról, amelynek gyökere ez a csomópont. A faeltávolítási módszerek három esetre oszthatók.
Első eset. Az eltávolítandó csomópontnak nincs gyermeke.
Ha a törölni kívánt csomópontnak nincs gyermeke, az azt jelenti, hogy levél. Ezért egyszerűen nullára állíthatja a szülőjének leftChild vagy rightChild mezőjét.
Második eset. Az eltávolítandó csomópontnak egy gyermeke van
Ez az eset sem túl nehéz. Térjünk vissza példánkhoz. Tegyük fel, hogy törölnünk kell egy 14-es kulcsú elemet. Fogadjunk el, hogy mivel ez egy 10-es kulcsú csomópont megfelelő gyermeke, akkor bármelyik leszármazottja (jelen esetben a jobb oldali) kulcsa 10-nél nagyobb, így Ön könnyen „levághatja” a fáról, és a szülőt közvetlenül a törlendő csomópont gyermekéhez kötheti, pl. csatlakoztassa a 10-es kulcsú csomópontot a 13-as csomóponthoz. Hasonló lenne a helyzet, ha törölnünk kellene egy olyan csomópontot, amely a szülő bal gyermeke. Gondolj bele magad – egy pontos hasonlat.
Harmadik eset. Node-nak két gyermeke van
A legnehezebb eset. Nézzünk egy új példát.
Utód keresése
Tegyük fel, hogy el kell távolítanunk a csomópontot a 25-ös kulccsal. Kit tegyünk a helyére? Az egyik követőjének (leszármazottaknak vagy leszármazottak leszármazottainak) kell válnia utód(aki átveszi az eltávolított csomópont helyét).
Honnan tudod, hogy ki legyen az utód? Intuitív módon ez az a csomópont a fában, amelynek kulcsa a következő legnagyobb az eltávolítandó csomóponthoz képest. Az algoritmus a következő. Menni kell a jobb oldali gyermekhez (mindig a jobbhoz, mert már volt róla szó, hogy az utód kulcsa nagyobb, mint a törlendő csomópont kulcsa), majd végig kell menni e jobb oldal bal gyermekeinek láncán. gyermek. A példában a 35-ös kulcsú csomóponthoz kell mennünk, majd annak bal gyermekeinek láncán le kell menni a levélhez - ebben az esetben ez a lánc csak a 30-as kulcsú csomópontból áll. Szigorúan véve azt keressük, a csomópontok halmazának legkisebb csomópontja, amely nagyobb, mint a kívánt csomópont.
Utód keresési módszer kódja:
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;
}
A törlési módszer teljes kódja:
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;
}
A komplexitás O(log(n)-hoz közelíthető).
A maximum/minimum megkeresése egy fában
Nyilvánvaló, hogy hogyan lehet megtalálni a minimális / maximális értéket a fában - egymás után végig kell mennie a fa bal / jobb elemeinek láncán; amikor a levélhez ér, az lesz a minimum/maximum elem.
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;
}
Bonyolultság – O(log(n))
Szimmetrikus bypass
A bejárás a fa minden csomópontjának meglátogatása, hogy valamit kezdjünk vele.
Rekurzív szimmetrikus bejárási algoritmus:
- Végezzen műveletet a bal oldali gyermeken
- Cselekedj magaddal
- Végezzen műveletet a megfelelő gyermeken
Kód:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Következtetés
Végül! Ha valamit nem magyaráztam el, vagy észrevételem van, akkor várom kommentben. Ahogy ígértem, itt a teljes 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áció O(n)
Lehet, hogy sokan észrevették: mi van, ha a fa egyensúlytalanná válik? Például tegyen csomópontokat a fába növekvő kulcsokkal: 1,2,3,4,5,6... Ekkor a fa valamelyest egy linkelt listára fog emlékeztetni. És igen, a fa elveszíti fastruktúráját, és ezáltal az adatelérés hatékonyságát is. A keresési, beszúrási és törlési műveletek bonyolultsága megegyezik a hivatkozott listákéval: O(n). Véleményem szerint ez a bináris fák egyik legfontosabb hátránya.
A felmérésben csak regisztrált felhasználók vehetnek részt. , kérem.
Elég régóta nem vagyok a Habrén, és szeretném tudni, hogy milyen témában milyen cikkeket látnál még szívesen?
-
Adatstruktúrák
-
Algoritmusok (DP, rekurzió, adattömörítés stb.)
-
Adatstruktúrák és algoritmusok alkalmazása a való életben
-
Android alkalmazások programozása Java nyelven
-
Java webalkalmazás programozás
2 felhasználó szavazott. 1 felhasználó tartózkodott.
Forrás: www.habr.com