Eelmäng
See artikkel käsitleb binaarseid otsingupuid. Kirjutasin hiljuti artikli sellest Seal ma kahendpuudele eriti tähelepanu ei pööranud, sest otsimise, sisestamise, kustutamise meetodid ei olnud asjakohased. Nüüd otsustasin kirjutada artikli puudest. Võib-olla alustame.
Puu on andmestruktuur, mis koosneb servadega ühendatud sõlmedest. Võime öelda, et puu on graafi erijuht. Siin on näide puust:
See ei ole binaarne otsingupuu! Kõik on kärbete all!
Terminoloogia
juur
Puu juur on ülemine sõlm. Näites on selleks sõlm A. Puus võib juurest mis tahes teise sõlmeni viia ainult üks tee! Tegelikult võib iga sõlme pidada sellele sõlmele vastava alampuu juureks.
Vanemad/järglased
Kõigil sõlmedel, välja arvatud juur, on täpselt üks serv, mis viib teise sõlmeni. Nimetatakse praeguse sõlme kohal olev sõlm lapsevanem see sõlm. Nimetatakse sõlme, mis asub praegusest allpool ja on sellega ühendatud järeltulija see sõlm. Võtame näite. Võtke sõlm B, siis on selle ülem sõlm A ja selle alampunktid sõlmed D, E ja F.
Leht
Sõlme, millel pole lapsi, nimetatakse puuleheks. Näites on sõlmed D, E, F, G, I, J, K lehed.
See on põhiterminoloogia. Teisi kontseptsioone arutatakse hiljem. Seega on kahendpuu puu, mille igal sõlmel ei ole rohkem kui kaks last. Nagu arvasite, ei ole näite puu binaarne, kuna sõlmedel B ja H on rohkem kui kaks last. Siin on näide kahendpuust:
Puu sõlmed võivad sisaldada mis tahes teavet. Binaarne otsingupuu on kahendpuu, millel on järgmised omadused:
- Nii vasak kui ka parem alampuud on binaarsed otsingupuud.
- Kõigil suvalise sõlme X vasakpoolse alampuu sõlmedel on andmevõtme väärtused väiksemad kui sõlme X enda andmevõtme väärtus.
- Kõigil suvalise sõlme X parempoolse alampuu sõlmedel on andmevõtme väärtused, mis on suuremad või võrdsed sõlme X enda andmevõtme väärtusega.
võti - mõni sõlme tunnus (näiteks arv). Võti on vajalik selleks, et oleks võimalik leida puu element, millele see võti vastab. Binaarse otsingupuu näide:
puu vaade
Kui ma lähen, lisan teie arusaamise parandamiseks mõned (võib-olla mittetäielikud) koodijupid. Täielik kood on artikli lõpus.
Puu koosneb sõlmedest. Sõlme struktuur:
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;
}
//...остальные методы узла
}
Igal sõlmel on kaks last (on täiesti võimalik, et vasaku lapse ja/või parema lapse lapsed on nullid). Tõenäoliselt saite aru, et antud juhul on numbriandmeteks sõlme salvestatud andmed; võti - sõlme võti.
Me mõtlesime sõlme välja, nüüd räägime puude pakitavatest probleemidest. Siin ja allpool tähendab sõna "puu" binaarse otsingupuu mõistet. Binaarne puu struktuur:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Klassiväljana vajame ainult puu juurt, sest juurest, kasutades meetodeid getLeftChild() ja getRightChild(), pääseb puu igasse sõlme.
Puu algoritmid
Otsing
Oletame, et teil on ehitatud puu. Kuidas leida võtme võtmega elementi? Peate liikuma järjestikku juurest puu alla ja võrdlema võtme väärtust järgmise sõlme võtmega: kui võti on väiksem kui järgmise sõlme võti, siis minge sõlme vasakpoolsesse järeltulijasse, kui rohkem - paremale, kui võtmed on võrdsed - soovitud sõlm leitakse! Vastav kood:
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;
}
Kui vool muutub nulliks, siis on iteratsioon jõudnud puu lõppu (kontseptsioonitasandil olete puus olematus kohas - lehe laps).
Mõelge otsingualgoritmi efektiivsusele tasakaalustatud puul (puul, milles sõlmed on jaotatud enam-vähem ühtlaselt). Siis on otsingu efektiivsus O(log(n)) ja logaritm 2. Vaata: kui tasakaalustatud puus on n elementi, siis see tähendab, et puul on log(n) baasi 2 tasandit. Ja otsides lähete tsükli ühe sammu jaoks ühe taseme võrra allapoole.
sisestada
Kui olete otsingu olemusest aru saanud, pole teil sisestusest raske aru saada. Peate lihtsalt laskuma puu lehe juurde (vastavalt otsingus kirjeldatud põlvnemisreeglitele) ja saama selle järeltulijaks - sõltuvalt võtmest vasakule või paremale. Rakendamine:
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;
}
}
}
}
}
Sel juhul on lisaks praegusele sõlmele vaja salvestada teavet praeguse sõlme vanema kohta. Kui praegune muutub nulliks, sisaldab ülemmuutuja meile vajalikku lehte.
Sisestamise efektiivsus on ilmselt sama, mis otsingul - O(log(n)).
Kustutamine
Kustutamine on kõige keerulisem toiming, mida tuleb puuga teha. On selge, et kõigepealt on vaja leida element, mille me eemaldame. Aga mis siis? Kui seame selle viite lihtsalt nulliks, siis kaotame teabe selle alampuu kohta, mille juur on see sõlm. Puude eemaldamise meetodid jagunevad kolmeks juhtumiks.
Esimene juhtum. Eemaldataval sõlmel ei ole lapsi.
Kui kustutataval sõlmel pole lapsi, tähendab see, et see on leht. Seetõttu saate selle vanema väljale leftChild või rightChild lihtsalt määrata null.
Teine juhtum. Eemaldataval sõlmel on üks laps
See juhtum pole ka väga raske. Läheme tagasi meie näite juurde. Oletame, et peame kustutama elemendi võtmega 14. Leppige kokku, et kuna see on võtmega 10 sõlme õige alam, siis on mis tahes selle järglastel (antud juhul õigel) võti suurem kui 10, nii et saab selle hõlpsalt puust "lõigata" ja ühendada vanema otse kustutatava sõlme lapsega, st. ühendage sõlm võtmega 10 sõlmega 13. Olukord oleks sarnane, kui peaksime kustutama sõlme, mis on selle vanema vasakpoolne alam. Mõelge sellele ise - täpne analoogia.
Kolmas juhtum. Nodel on kaks last
Kõige keerulisem juhtum. Vaatame uut näidet.
Otsige järglast
Oletame, et peame eemaldama sõlme võtmega 25. Kelle me selle asemele paneme? Üks tema järgijatest (järglastest või järeltulijate järeltulijatest) peab saama järglane(see, kes võtab eemaldatud sõlme asemele).
Kuidas sa tead, kes peaks olema järglane? Intuitiivselt on see puu sõlm, mille võti on eemaldatavast sõlmest suuruselt järgmine. Algoritm on järgmine. Peate minema selle parema alamosa juurde (alati õigesse, sest juba öeldi, et järglase võti on suurem kui kustutatava sõlme võti) ja seejärel läbima selle parema vasakpoolsete laste ahela. laps. Näites peame minema võtmega 35 sõlme ja seejärel minema selle vasakpoolsete laste ahelast alla lehele – antud juhul koosneb see kett ainult võtmega 30 sõlmest. Rangelt võttes otsime sõlmede komplekti väikseim sõlm, mis on suurem kui soovitud sõlm.
Järgmiste otsingumeetodite kood:
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;
}
Kustutusmeetodi täielik kood:
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;
}
Keerukust saab lähendada O(log(n)).
Puust maksimumi/miinimumi leidmine
Ilmselgelt, kuidas leida puust minimaalne / maksimaalne väärtus - peate järjestikku läbima vastavalt puu vasak-/parempoolsete elementide ahela; kui jõuate lehe juurde, on see minimaalne/maksimaalne 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;
}
Keerukus – O(log(n))
Sümmeetriline ümbersõit
Läbisõit on puu iga sõlme külastamine, et sellega midagi ette võtta.
Rekursiivne sümmeetriline läbimise algoritm:
- Tehke vasakpoolse lapsega toiming
- Tehke endaga tegevus
- Tehke õige lapsega toiming
Kood:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Järeldus
Lõpuks ometi! Kui ma midagi ei selgitanud või kommentaare ei avalda, siis ootan kommentaaridesse. Nagu lubatud, on siin täielik kood.
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
Degeneratsioon O(n)-ks
Paljud teist on ehk märganud: mis siis, kui paned puu tasakaalust välja? Näiteks pane puusse sõlmed kasvavate klahvidega: 1,2,3,4,5,6... Siis meenutab puu mõneti lingitud loendit. Ja jah, puu kaotab oma puustruktuuri ja seega ka andmetele juurdepääsu tõhususe. Otsingu-, sisestamis- ja kustutamistoimingute keerukus muutub samaks kui lingitud loendi puhul: O(n). See on minu arvates kahendpuude üks olulisemaid puudusi.
Küsitluses saavad osaleda ainult registreerunud kasutajad. palun.
Ma pole pikka aega Habres käinud ja tahaksin teada, milliseid artikleid millistel teemadel tahaksite rohkem näha?
-
Andmestruktuurid
-
Algoritmid (DP, rekursioon, andmete tihendamine jne)
-
Andmestruktuuride ja algoritmide rakendamine reaalses elus
-
Androidi rakenduste programmeerimine Javas
-
Java veebirakenduste programmeerimine
2 kasutajat hääletas. 1 kasutaja jäi erapooletuks.
Allikas: www.habr.com