alkusoitto
Tämä artikkeli käsittelee binäärihakupuita. Kirjoitin äskettäin artikkelin aiheesta Siellä en oikeastaan kiinnittänyt huomiota binääripuihin, koska haku-, lisäys- ja poistomenetelmät eivät olleet merkityksellisiä. Nyt päätin kirjoittaa artikkelin puista. Ehkä aloitamme.
Puu on tietorakenne, joka koostuu reunoilla yhdistetyistä solmuista. Voimme sanoa, että puu on graafin erikoistapaus. Tässä on esimerkkipuu:
Tämä ei ole binäärihakupuu! Kaikki on alla!
terminologia
juuri
Puun juuri on ylin solmu. Esimerkissä tämä on solmu A. Puussa vain yksi polku voi johtaa juuresta mihin tahansa toiseen solmuun! Itse asiassa mitä tahansa solmua voidaan pitää tätä solmua vastaavan alipuun juurina.
Vanhemmat/jälkeläiset
Kaikilla solmuilla, paitsi juurilla, on täsmälleen yksi reuna, joka johtaa toiseen solmuun. Nykyisen solmun yläpuolella olevaa solmua kutsutaan vanhempi tämä solmu. Nykyisen solmun alapuolella olevaa ja siihen kytkettyä solmua kutsutaan jälkeläinen tämä solmu. Otetaan esimerkki. Otetaan solmu B, niin sen pää on solmu A ja sen lapset ovat solmut D, E ja F.
arkki
Solmua, jolla ei ole lapsia, kutsutaan puun lehdeksi. Esimerkissä solmut D, E, F, G, I, J, K ovat lehtiä.
Tämä on perusterminologia. Muita käsitteitä käsitellään myöhemmin. Joten binääripuu on puu, jossa jokaisella solmulla ei ole enempää kuin kaksi lasta. Kuten arvasit, esimerkin puu ei ole binäärinen, koska solmuilla B ja H on enemmän kuin kaksi lasta. Tässä on esimerkki binääripuusta:
Puun solmut voivat sisältää mitä tahansa tietoa. Binäärihakupuu on binääripuu, jolla on seuraavat ominaisuudet:
- Sekä vasen että oikea alipuu ovat binäärihakupuita.
- Kaikkien mielivaltaisen solmun X vasemman alipuun solmujen dataavainarvot ovat pienemmät kuin itse solmun X dataavainarvo.
- Kaikilla mielivaltaisen solmun X oikean alipuun solmuilla on dataavainarvot, jotka ovat suurempia tai yhtä suuria kuin itse solmun X dataavaimen arvo.
avain - jokin solmun ominaisuus (esimerkiksi numero). Avain tarvitaan, jotta voidaan löytää puun elementti, jota tämä avain vastaa. Esimerkki binaarihakupuusta:
puunäkymä
Kun jatkan, sisällytän mukaan joitain (ehkä epätäydellisiä) koodinpätkiä ymmärtääksesi paremmin. Koko koodi on artikkelin lopussa.
Puu koostuu solmuista. Solmun rakenne:
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;
}
//...остальные методы узла
}
Jokaisella solmulla on kaksi lasta (on täysin mahdollista, että leftChild- ja/tai rightChild-lapset ovat nolla). Ymmärsit varmaan, että tässä tapauksessa numerotieto on solmuun tallennettua dataa; avain - solmuavain.
Selvitimme solmun, nyt puhutaan puiden kiireellisistä ongelmista. Tässä ja alla sana "puu" tarkoittaa binäärihakupuun käsitettä. Binääripuurakenne:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Luokkakenttänä tarvitsemme vain puun juuren, koska juuresta päästään getLeftChild()- ja getRightChild()-menetelmillä mihin tahansa puun solmuun.
Puun algoritmit
haku
Oletetaan, että sinulla on rakennettu puu. Kuinka löytää elementti avainavaimella? Sinun on siirryttävä peräkkäin juuresta alas puuhun ja verrattava avaimen arvoa seuraavan solmun avaimeen: jos avain on pienempi kuin seuraavan solmun avain, siirry solmun vasempaan jälkeläiseen, jos enemmän - oikealle, jos avaimet ovat samat - haluttu solmu löytyy! Asiaankuuluva koodi:
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;
}
Jos virta muuttuu nollaksi, iteraatio on saavuttanut puun loppuun (käsitteellisellä tasolla olet ei-olemassa olevassa paikassa puussa - lehden lapsessa).
Harkitse hakualgoritmin tehokkuutta tasapainoisessa puussa (puussa, jossa solmut ovat jakautuneet enemmän tai vähemmän tasaisesti). Tällöin haun tehokkuus on O(log(n)) ja kanta 2 logaritmi Katso: jos balansoidussa puussa on n elementtiä, niin tämä tarkoittaa, että puussa on log(n) kanta 2 tasoa. Ja haussa, yhden syklin vaiheen aikana menet yhden tason alaspäin.
lisätä
Jos olet ymmärtänyt haun olemuksen, sinun ei ole vaikea ymmärtää lisäystä. Sinun tarvitsee vain mennä alas puun lehteen (haussa kuvattujen laskeutumissääntöjen mukaisesti) ja tulla sen jälkeläiseksi - vasemmalle tai oikealle avaimesta riippuen. Toteutus:
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;
}
}
}
}
}
Tässä tapauksessa nykyisen solmun lisäksi on tarpeen tallentaa tietoa nykyisen solmun isästä. Kun nykyisestä tulee nolla, päämuuttuja sisältää tarvitsemamme arkin.
Lisäysteho on ilmeisesti sama kuin haun - O(log(n)).
Poistaminen
Poistaminen on monimutkaisin toiminto, joka täytyy tehdä puulla. On selvää, että ensin on löydettävä elementti, jonka aiomme poistaa. Mutta mitä sitten? Jos asetamme sen viittauksen yksinkertaisesti nollaksi, menetämme tiedot alipuusta, jonka juuri on tämä solmu. Puiden poistomenetelmät on jaettu kolmeen tapaukseen.
Ensimmäinen tapaus. Poistettavalla solmulla ei ole lapsia.
Jos poistettavalla solmulla ei ole lapsia, se tarkoittaa, että se on lehti. Siksi voit yksinkertaisesti asettaa sen ylätason leftChild- tai rightChild-kenttään nollaksi.
Toinen tapaus. Poistettavalla solmulla on yksi lapsi
Tämä tapaus ei myöskään ole kovin vaikea. Palataanpa esimerkkiimme. Oletetaan, että meidän on poistettava elementti avaimella 14. Sovitaan, että koska se on avaimella 10 olevan solmun oikea lapsi, minkä tahansa sen jälkeläisen (tässä tapauksessa oikean) avain on suurempi kuin 10, joten voi helposti "leikata" sen puusta ja yhdistää vanhemman suoraan poistettavan solmun lapsiin, ts. yhdistä solmu avaimella 10 solmuun 13. Tilanne olisi samanlainen, jos meidän täytyisi poistaa solmu, joka on vanhemman vasen lapsi. Ajattele sitä itse - tarkka analogia.
Kolmas tapaus. Nodilla on kaksi lasta
Vaikein tapaus. Katsotaanpa uutta esimerkkiä.
Etsi seuraaja
Oletetaan, että meidän on poistettava solmu avaimella 25. Kenet laitamme sen tilalle? Yksi hänen seuraajistaan (jälkeläisistä tai jälkeläisten jälkeläisistä) on tultava seuraaja(se, joka ottaa poistetun solmun paikan).
Mistä tiedät, kenen tulisi olla seuraaja? Intuitiivisesti tämä on puun solmu, jonka avain on seuraavaksi suurin poistettavasta solmusta. Algoritmi on seuraava. Sinun on mentävä sen oikeaan lapseen (aina oikeaan, koska jo sanottiin, että seuraajan avain on suurempi kuin poistettavan solmun avain) ja sitten käydä läpi tämän oikean vasemman avain. lapsi. Esimerkissä meidän täytyy mennä solmuun avaimella 35 ja sitten mennä alas sen vasemman jälkeläisten ketjua lehteen - tässä tapauksessa tämä ketju koostuu vain solmusta avaimella 30. Tarkkaan ottaen etsimme solmujoukon pienin solmu, joka on suurempi kuin haluttu solmu.
Seuraajan hakumenetelmäkoodi:
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;
}
Poistomenetelmän täydellinen koodi:
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;
}
Monimutkaisuus voidaan approksimoida O(log(n)).
Maksimin/minimin löytäminen puusta
Ilmeisesti kuinka löytää puusta pienin / maksimiarvo - sinun on käytävä peräkkäin puun vasemman / oikean elementin ketju; kun pääset lehteen, se on minimi/maksimielementti.
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;
}
Monimutkaisuus – O(log(n))
Symmetrinen ohitus
Traversal on käynti puun jokaisessa solmussa, jotta sille voidaan tehdä jotain.
Rekursiivinen symmetrinen läpikulkualgoritmi:
- Tee toiminto vasemmalle lapselle
- Tee teko itsesi kanssa
- Tee toimenpide oikean lapsen suhteen
Koodi:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Johtopäätös
vihdoinkin! Jos en selittänyt jotain tai minulla on kommentteja, odotan kommentteja. Kuten luvattiin, tässä on täydellinen koodi.
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.
Degeneraatio O(n)
Monet teistä ovat ehkä huomanneet: entä jos saat puun epätasapainoiseksi? Laita esimerkiksi solmut puuhun kasvavilla avaimilla: 1,2,3,4,5,6... Silloin puu muistuttaa jossain määrin linkitettyä listaa. Ja kyllä, puu menettää puurakenteensa ja siten tietojen käytön tehokkuuden. Haku-, lisäys- ja poistotoimintojen monimutkaisuus tulee samaksi kuin linkitetyssä luettelossa: O(n). Tämä on mielestäni yksi tärkeimmistä binääripuiden haitoista.
Vain rekisteröityneet käyttäjät voivat osallistua kyselyyn. , ole kiltti.
En ole ollut Habressa pitkään aikaan, ja haluaisin tietää, mitä artikkeleita mistä aiheista haluaisit nähdä lisää?
-
Tietorakenteet
-
Algoritmit (DP, rekursio, tietojen pakkaus jne.)
-
Tietorakenteiden ja algoritmien soveltaminen tosielämässä
-
Android-sovellusten ohjelmointi Java-kielellä
-
Java-verkkosovellusohjelmointi
2 käyttäjää äänesti. 1 käyttäjä pidättyi äänestämästä.
Lähde: www.habr.com