Binäärihakupuut tukevat kolmea pääoperaatiota: alkuaineiden lisääminen, elementtien poistaminen ja etsintäoperaatiot (avaimen löytymisen tarkistaminen).

SearchingEdit

Haku binäärihakupuu tietyn avain voidaan ohjelmoida rekursiivisesti tai iteratiivisesti.

aloitamme tutkimalla juurisolmua. Jos puu on mitätön, etsimäämme avainta ei ole puussa. Muuten, jos avain on sama kuin juuren, haku onnistuu ja palautamme solmun. Jos avain on pienempi kuin juuri, tutkimme vasemmanpuoleisen subtreen., Samoin, jos avain on suurempi kuin juuri, etsimme oikea subtree. Tämä prosessi toistetaan, kunnes avain löytyy tai loput subtree on nolla. Jos etsittyä avainta ei löydetä sen jälkeen, kun nollalukema on saavutettu, avainta ei ole puussa. Tämä on helposti ilmaistuna rekursiivinen algoritmi (toteutettu Python):

sama algoritmi voidaan toteuttaa iteratiivisesti:

Nämä kaksi esimerkkiä eivät tue kaksoiskappaleet, se on, he luottavat järjestyksen suhteen, on koko tilauksen.

voidaan todeta, että rekursiivinen algoritmi on hännän rekursiivinen., Kieli tukee tail call optimization, rekursiivinen ja iteratiivinen esimerkkejä laatii vastaavia ohjelmia.

Koska pahimmassa tapauksessa tämä algoritmi on etsiä juuresta puun lehtiä kauimpana root, haku operaatio vie aikaa verrannollinen puun korkeuteen (ks puu terminologia). Keskimäärin binäärihakupuilla, joissa on Solmunavaimet, on O (loki |solmut|) korkeus. Kuitenkin, pahimmassa tapauksessa, binäärihaku puita voi olla O(|Solmut|) korkeus, kun epätasapainoinen puu muistuttaa linkitetty lista (rappeutua puu).,

Haku kaksoiskappaleita allowedEdit

Jos tilauksen suhteen on vain yhteensä ennakkotilata, kohtuullinen laajentaminen toiminnallisuutta on seuraava: myös siinä tapauksessa, että tasa-arvon hakua alas lehtiä. Näin voidaan määrittää (tai hard-wire) suunta, minne lisätä kaksoiskappaleen, joko oikealle tai vasemmalle kaikista kaksoiskappaleet puuhun toistaiseksi. Jos suunta on kova-wired, sekä valintoja, oikealle ja vasemmalle, tukea pino lisää päällekkäisiä kuten push-toiminnon ja poistaa kuten pop-operaatio.,:155

tällaisella hakutoiminnolla varustettu binääripuun Lajitelma muuttuu vakaaksi.

InsertionEdit

Lisäys alkaa haku alkaa; jos avain ei ole sama, että root, me haku vasemmalle tai oikealle alipuut kuin ennen. Lopulta pääsemme ulkoinen solmu ja lisätä uusi avain-arvo-pari (tässä koodataan ennätys ’newNode), sillä sen oikea tai vasen lapsi, riippuen solmun avain., Toisin sanoen, me tutkia juuri ja rekursiivisesti lisää uuden solmun vasen alipuu, jos sen avain on pienempi kuin juuren, tai oikea alipuu, jos sen avain on suurempi tai yhtä suuri kuin root.

Tässä on, miten tyypillinen binary search tree lisäys voidaan suorittaa binary tree C++:

Vaihtoehtoisesti, ei-rekursiivinen versio saattaa olla toteutettu näin., Käyttämällä osoitin-to-osoitin seurata, missä meidän tuli antaa koodin välttää avointa tarkistaminen ja käsittely silloin, kun se tarvitsee lisää solmu puun juuri:

edellä tuhoisa menettelyyn variantti muuttaa puun paikallaan. Se käyttää vain jatkuvaa kasaustilaa (ja iteratiivinen versio käyttää myös jatkuvaa pinoavaruutta), mutta puun aiempi versio on kadonnut., Vaihtoehtoisesti, kuten seuraavat Python-esimerkki, voimme rekonstruoida kaikki esi liitetään solmu; mahdolliset viittaukset alkuperäisen puun juuren on edelleen voimassa, jolloin puu pysyviä tiedot rakenne:

osa, joka on rakennettu uudelleen käyttää O(log n) tilaa keskimääräisessä tapauksessa O(n) pahimmassa tapauksessa.

joko versio, tämä operaatio vaatii aikaa verrannollinen puun korkeus pahimmassa tapauksessa, joka on O(log n) kertaa keskimääräinen tapauksessa yli kaikki puut, mutta O(n) aika, pahimmassa tapauksessa.,

Toinen tapa selittää lisäys on, että voidakseen lisätä uuden solmun puu, sen avain on ensimmäinen verrattuna root. Jos sen avain on pienempi kuin juuren, sitä verrataan juuren vasemman lapsen avaimeen. Jos sen avain on suurempi, sitä verrataan juuren oikeaan lapseen. Tämä prosessi jatkuu, kunnes uusi solmu on verrattuna lehtisolmu, ja sitten se lisätään tämä solmu on oikealla tai vasemmalla lapsi, riippuen sen avain: jos avain on pienempi kuin lehtiä on avain, niin se on asetettu niin, että lehtiä on vasen lapsi, muuten kuin lehtien on oikea lapsi.,

On olemassa muita tapoja lisäämällä solmuja binary puu, mutta tämä on ainoa tapa, lisäämällä solmut lehdet ja samaan aikaan säilyttää BST rakenne.

DeletionEdit

Kun poistat solmun binary search tree on pakko säilyttää, jotta peräkkäiset solmut. Tähän on monia mahdollisuuksia. T. Hibbardin vuonna 1962 ehdottama menetelmä takaa kuitenkin sen, että subjektin korkeudet muuttuvat korkeintaan yhdellä., Mahdollisia tapauksia on kolme:

• poistaa solmun, jossa ei ole lapsia: poista solmu puusta.
• poistaa solmun yhdellä lapsella: poista solmu ja korvaa se lapsellaan.
• Poistaminen solmu D kaksi lasta: valitse joko D-jotta edeltäjä tai-jotta seuraaja E (katso kuva). Poistamisen sijaan D, korvaa sen avain ja arvo E on. Jos E ei ole lapsi, poista E aiemmat vanhemman G. Jos E on lapsi F, se on oikea lapsi, niin, että se on korvata E E n emo.,

kaikissa tapauksissa, kun D sattuu olemaan juuri, tee korvaava solmu juuri uudelleen.

kahden lapsen solmuja on vaikeampi poistaa., Solmu on-jotta seuraaja on sen oikea alipuu on vasemmalle-eniten lapsi, ja solmu on-jotta edeltäjä on vasen alipuu on oikeassa-eniten lapsi. Kummassakin tapauksessa tällä solmulla on vain yksi tai ei yhtään lasta. Poista se toisen edellä mainituista kahdesta yksinkertaisemmasta tapauksesta mukaan.

Johdonmukaisesti käyttämällä, jotta seuraaja tai in-order edeltäjä jokaisen esiintymän kahden lapsen tapauksessa voi johtaa epätasapainoinen puu, joten jotkut toteutukset valitse yksi tai muita eri aikoina.,

Runtime analyysi: Vaikka tämä toiminta ei aina kulkea puun alas lehtiä, tämä on aina mahdollista; näin ollen pahimmassa tapauksessa se vaatii aikaa verrannollinen puun korkeus. Se ei vaadi enempää edes silloin, kun solmulla on kaksi lasta, koska se seuraa edelleen yhtä polkua eikä käy yhdessäkään solmussa kahdesti.,

TraversalEdit

Kun binary search tree on luotu, sen osia voidaan noutaa tilauksen rekursiivisesti liikkumisesta vasemman alipuun juurisolmu, päästä solmu itse, sitten rekursiivisesti liikkumisesta oikea alipuu solmun, tämä jatkuva malli, jossa jokainen solmu puussa, koska se on rekursiivisesti käsiksi. Kuten kaikki binary puita, yksi voi tehdä pre-order-traversal tai post-jotta läpikäynti, mutta ei todennäköisesti ole hyötyä binäärihaku puita., In-jotta läpikäynti binary search tree johtaa aina lajiteltu luettelo solmu kohteet (numerot, merkkijonoja tai muita vastaavia tuotteita).

Pythonissa järjestyksenvalvojien koodi on alla. Se soittaa soittopyynnön (jokin funktio ohjelmoija haluaa soittaa solmun arvo, kuten tulostaa näytölle) jokainen solmu puussa.

Traversal vaatii O(n) – aikaa, koska sen on käytävä jokaisessa solmussa. Tämä algoritmi on myös O(n), joten se on asymptoottisesti optimaalinen.

läpiajo voidaan toteuttaa myös iteratiivisesti. Tietyissä sovelluksissa, esim., suurempi yhtäläinen haku, approksimatiivinen haku, operaatio yhden vaiheen (iteratiivinen) läpimeno voi olla erittäin hyödyllinen. Tämä on tietenkin toteutettu ilman callback construct ja vie O(1) keskimäärin ja O(log n) pahimmassa tapauksessa.

VerificationEdit

Joskus meillä on jo binääripuu, ja meidän täytyy selvittää, onko se on BST. Tämä ongelma on yksinkertainen rekursiivinen ratkaisu.,

BST omaisuus—jokaisen solmun oikea alipuu on oltava suurempi kuin nykyisen solmun ja jokaisen solmun vasen alipuu on pienempi kuin nykyinen solmu—on avain sen selvittämiseen, onko puu on BST tai ei. Ahne algoritmi—yksinkertaisesti kulkea puun jokaisen solmun tarkistaa, onko solmun arvo on suurempi kuin arvo vasemmalla lapsi ja pienempi kuin arvo, joka on oikea lapsi—ei toimi kaikissa tapauksissa., Harkitse seuraavia puu:

 20 / \ 10 30 / \ 5 40

puu edellä, jokainen solmu täyttää ehdolla, että solmu sisältää arvoa, joka on suurempi kuin sen vasen lapsi ja pienempi kuin sen oikea lapsi pitää, ja silti se ei ole BST: arvo 5 on oikea alipuun solmun sisältää 20, rikkoo BST: n omaisuutta.

sen sijaan, että tehtäisiin päätös pelkästään solmun ja sen lasten arvoihin perustuen, tarvitaan myös vanhemmalta virtaavaa tietoa., Jos puu edellä, jos voisimme muistaa solmu sisältää arvon 20, näkisimme, että solmu, jossa on arvo 5 rikkoo BST-omaisuuden sopimus.,

Joten kunto täytyy tarkistaa jokaisen solmun on:

• jos solmulla on vasen lapsi on sen vanhemman, niin se on pienempi (tai yhtä suuri) emoyhtiön ja sen on läpäistävä alas arvo sen emoyhtiön sen oikea alipuu varmista, että mikään solmut, että alipuu on suurempi kuin emoyrityksen
• jos solmulla on oikea lapsi sen emoyhtiö, sitten se on suurempi kuin emoyrityksen ja sen on läpäistävä alas arvo sen emoyhtiön sen vasen alipuu varmista, että mikään solmut, että alipuu on pienempi kuin vanhemman.,

rekursiivinen ratkaisu C++ voi selittää tämän tarkemmin:

node->key+1 ja node->key-1 tehdään sallia vain erillisiä elementtejä BST.

Jos haluamme, että samat elementit ovat myös läsnä, niin voimme käyttää molemmissa paikoissa vain node->key.

alustava kutsu tämä toiminto voi olla jotain, kuten tämä:

if (isBST(root, INT_MIN, INT_MAX)) { puts("This is a BST.");} else { puts("This is NOT a BST!");}

Pohjimmiltaan meidän pitää luoda kelvollinen valikoima (alkaen ) ja pitää kutistuu sen alas kunkin solmu, niin menemme alas rekursiivisesti.,

kuten kohdassa #Traversal todetaan, binäärihakupuun järjestyksenvalvoja palauttaa lajitellut solmut. Niinpä meidän tarvitsee vain pitää viimeisen vieraili solmu, kun liikkumisesta puu ja tarkista, onko sen avain on pienempi (tai pienempi/sama, jos kopiot ovat sallittuja puu) verrattuna nykyiseen avain.

Rinnakkain algorithmsEdit

On olemassa myös rinnakkaisia algoritmeja binäärihaku puita, kuten lisäämällä/poistamalla useita elementtejä, rakentaminen alkaen array, suodatin tiettyjä predicator, litistää array, yhdistäminen/vähentämällä/leikkaavien kaksi puuta, jne., Nämä algoritmit voidaan toteuttaa käyttämällä liittyä-pohjainen puu, algoritmeja, joita voidaan myös pitää puu tasapainossa käyttämällä useita tasapainotus järjestelmien (kuten AVL-puu, punamusta puu, paino-tasapainoinen puu ja treap) .