Kahendpuu

Allikas: Vikipeedia
Jump to navigation Jump to search
Kahendpuu, mille igas tipus on kirje. Puus on 9 tippu ning juurtippu kirjeks on 2. Juurtipu vasaku alluva kirje on 7 ja parema alluva kirje on 5.

Kahendpuu ehk binaarpuu on arvutiteaduses kasutusel olev andmestruktuur, mis koosneb tippudest, kusjuures igal tipul on maksimaalselt kaks alluvat. Tipu ühte alluvat nimetatakse vasakuks alluvaks ja teist paremaks alluvaks. Hulgateoorias saab (mittetühja) kahendpuud defineerida rekursiivselt kui ennikut (L, S, R), kus L ja R on kahendpuud või tühjad hulgad ja S on üheelemendiline hulk.[1]

Graafiteoorias vaadeldakse kahendpuid (üldisemalt kõiki k-aarseid puid) kui suunatud graafe, kus üks tipp u on juurtipp ning igasse teise tippu v leidub temast täpselt üks suunatud lihtahel.[2] Kahendpuud võib vaadelda ka kui suunamata graafi. Täpsemalt on tegemist järjestatud juurega puuga[3]. Mõned autorid kasutavad terminit juurega kahendpuu, et rõhutada asjaolu, et tegemist on juurega puuga.[4] Samas on ülaltoodud definitsioonidest näha, et iga kahendpuu on juurega puu.

Matemaatikas ei ole kahendpuudel ühtset definitsiooni. Mõned matemaatikud kasutavad arvutiteaduses levinud definitsioone[5], kuid mõnedes definitsioonides peab igal tipul, mis pole leht, olema täpselt kaks alluvat ning tingimata ei nõuta alluvate (vasaku/parema) järjestamist.[6]

Kahendpuude kasutusviisid[muuda | muuda lähteteksti]

Kahendpuudel on palju erinevaid otstarbeid. Üldiselt võib need jagada kaheks.

  • Esiteks saab kahendpuid kasutada, et saada ligi tippudele, lähtudes tipuga seotud infost.[7] Sellist ideed kasutatakse, et implementeerida kahendotsimispuid ja kahendkuhjasid, ning need on väga kasulikud andmete otsimiseks ja sorteerimiseks. Sellisel juhul on oluline, kas tipp on oma ülemuse parem või vasak alluv, isegi siis, kui ülemusel on ainult üks alluv.[8] Samas ei ole tippude üldine paigutus tingimata infot kandev. Näiteks kahendotsimispuus sõltub tippude paigutus suuresti sellest, mis järjekorras nad lisati. Samas võib neid ümber tõsta (näiteks tasakaalustades) ilma infot kaotamata.
  • Kahendpuid võib kasutada ka andmete salvestamiseks arvutis, kui andmetel on kaheks jagunev struktuur. Sel juhul on tippude paigutus puus osa informatsioonist. Näide sellisest kasutusest on Huffmani kodeering.

Kahendpuude tüübid[muuda | muuda lähteteksti]

Kompaktne kahendpuu
Täis-kahendpuu

Kahendpuude terminoloogia pole standardiseeritud, seega kirjeldatakse kahendpuid kirjanduses paljude erinevate mõistetega.

Kahendpuus nimetatakse tasemeks kõikide tippude hulka, mis asuvad samal kaugusel juurtipust.[9]

  • Täis-kahendpuu on kahendpuu, mille igal tipul on täpselt 0 või 2 alluvat. Teisisõnu, kõikidel tippudel peale lehtede on täpselt 2 alluvat.[9]
  • Täielik kahendpuu on kahendpuu, mille kõik lehttipud asuvad samal tasemel ning iga sisetipu aste on 2.[10]
  • Kompaktne kahendpuu on puu, mis on saadud täielikust kahendpuu viimasest tasemest mingi arvu lehttippude eemaldamisel.[10]
  • Tasakaalus kahendpuu on selline kahendpuu, mille iga tipu vasaku ja parema alampuu kõrgused ei erine rohkem kui ühe võrra.[11]

Kahendpuude omadused[muuda | muuda lähteteksti]

Kahendpuude teoorias ei ole kokkulepet, mis on ühetipulise puu kõrgus. Mõnes allikas kirjutatakse, et see on 0[10] , aga teises, et see on 1.[9] Järgnevates näidetes eeldatakse, et ühetipulise puu kõrgus on 0.

  • Täis-kahendpuus on vähemalt ja maksimaalselt tippu, kus on puu kõrgus.
  • Täielikus kahendpuus on täpselt lehttippu, kus on puu tippude arv. See tuleneb sellest, et sisetippude arvu saame leida .
  • Seega on täielikus lehega kahendpuus tippu.
  • Täielikus kahendpuus on lehtede arv ja tippude arv .

Kahendpuude esitus arvutis[muuda | muuda lähteteksti]

Kahendpuid saab arvutis programmerimiskeelte abil esitada mitut moodi.

Haskell[muuda | muuda lähteteksti]

Näiteks Haskellis saab kahendpuud esitada uue andmetüübina, millel on kaks konstruktorit:[12]

  • konstruktor lehttipu jaoks;
  • konstruktor tipu jaoks koos väärtuse ning vasaku ja parema haruga.
data Tree a = Leaf | Node a (Tree a) (Tree a)

Python[muuda | muuda lähteteksti]

Pythonis (ja ka paljudes teiste keeltes) saab kahendpuud esitada tipuklassina, kus igal isendil on viide oma alluvatele, mis on samuti tipud.[13]

class Node: 
    def __init__(self,key): 
        self.left = None
        self.right = None
        self.val = key

Massiivina[muuda | muuda lähteteksti]

Mõnel juhul soovitakse kahendpuid kujutada massiividena. Näiteks kahendkuhi, mis põhineb kompaktsel kahendpuul, esitatakse tihti lihtsalt massiivina, kus elemendid paiknevad järjestikuselt tasemete kaupa.[10] See tähendab, et massiivi alguses on juurtipp, siis tema alluvad, siis nende alluvate alluvad jne.

Viited[muuda | muuda lähteteksti]

  1. Rowan Garnier; John Taylor (2009). Discrete Mathematics: Proofs, Structures and Applications, Third Edition. CRC Press. p. 620. ISBN 978-1-4398-1280-8. 
  2. Knuth (1997). The Art Of Computer Programming, Volume 1, 3/E. Pearson Education. p. 363. ISBN 0-201-89683-4. 
  3. Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. p. 749. ISBN 978-0-07-338309-5. 
  4. David R. Mazur (2010). Combinatorics: A Guided Tour. Mathematical Association of America. p. 246. ISBN 978-0-88385-762-5. 
  5. Hazewinkel, Michiel (2001). Encyclopedia of Mathematics. Springer Science+Business Media B.V. / Kluwer Academic Publishers. ISBN 978-1-55608-010-4
  6. L.R. Foulds (1992). Graph Theory Applications. Springer Science & Business Media. p. 32. ISBN 978-0-387-97599-3. 
  7. David Makinson (2009). Sets, Logic and Maths for Computing. Springer Science & Business Media. p. 199. ISBN 978-1-84628-845-6. 
  8. Jonathan L. Gross (2007). Combinatorial Methods with Computer Applications. CRC Press. p. 248. ISBN 978-1-58488-743-0. 
  9. 9,0 9,1 9,2 Ahti Peder, Jüri Kiho, Härmel Nestra (2017). Algoritmid ja andmestruktuurid, Ülesannete kogu. Tartu: Tartu Ülikooli Kirjastus. 
  10. 10,0 10,1 10,2 10,3 Jüri Kiho (2003). Algoritmid ja andmestruktuurid. Tartu: Tartu Ülikooli Kirjastus. 
  11. Aaron M. Tenenbaum, et al. Data Structures Using C, Prentice Hall, 1990
  12. "Hackage - Haskell package archive". Vaadatud 10.11.2018.
  13. "GeeksforGeeks - A computer science portal for geeks". Vaadatud 10.11.2018.