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

Kahendpuudel on palju 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

Kahendpuude terminoloogia pole standardiseeritud, seega kirjeldatakse kahendpuid kirjanduses paljude 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

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 $n=2h+1$ ja maksimaalselt $n=2^{h+1}-1$ tippu, kus $h$ on puu kõrgus.
Täielikus kahendpuus on täpselt $l=(n+1)/2$ lehttippu, kus $n$ on puu tippude arv. See tuleneb sellest, et sisetippude arvu saame leida $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ .
Seega on täielikus $l$ lehega kahendpuus $n=2l-1$ tippu.
Täielikus kahendpuus on lehtede arv ${\displaystyle l=2^{h))$ ja tippude arv $n=2^{h+1}-1$ .

Kahendpuude esitus arvutis

Kahendpuid saab arvutis programmeerimiskeelte abil esitada mitut moodi.

Haskell

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

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

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

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

Kategooria