SHPORA.net :: PDA

Login:
регистрация

Main
FAQ

гуманитарные науки
естественные науки
математические науки
технические науки
Search:
Title: | Body:

Kahendpuu ja selle läbimine, kahendotsimise puu (binary search tree).




Kahendpuu on puu, mille igal tipul on null kuni kaks alluvat, seejuures tehakse vahet vasakpoolse ja parempoolse alluva vahel.



T on kahendpuu, kui kas:



1. T on tühi



või



2. T = (t0, Tv, Tp), kus t0on puu T juur, Tv on kahendpuu (vasak alampuu) ja Tp on kahendpuu (parem alampuu).





Täielik kahendpuu sisaldab kõiki võimalikke tippe etteantud sügavusel (kõikidel vahetippudel on täpselt kaks alluvat);

kui eemaldada järjest parempoolseimaid lehti, on igal sammul tulemuseks kompaktne kahendpuu.

Kahendpuu läbimine



Eesjärjestuses (pre-order):



Kui T ei ole tühi, siis:



1. töödelda juur

2. läbida vasak alampuu eesjärjestuses

3. läbida parem alampuu eesjärjestuses.



Taga- e. lõppjärjestuses (post-order, end-order):



Kui T ei ole tühi, siis:



1. läbida vasak alampuu lõppjärjestuses

2. läbida parem alampuu lõppjärjestuses

3. töödelda juur.



Keskjärjestuses (in-order):



Kui T ei ole tühi, siis:



1. läbida vasak alampuu keskjärjestuses

2. töödelda juur

3. läbida parem alampuu keskjärjestuses.













Kahendotsimise puu



Olgu kahendpuu iga tipuga t seotud võti t.x (võrreldavad väärtused).

T.x olgu mittetühja kahendpuu T juure võti.



Kahendotsimise puu on kahendpuu T, milles



1. Kas T on tühi või

2.

1. iga tipu tv korral vasakust alampuust Tv kehtib tv.x <= T.x

3. iga tipu tp korral paremast alampuust Tp kehtib tp.x >= T.x

4. Tv ja Tp on kahendotsimise puud





Kahendotsimise puu moodustamine = järjestamine



Tasakaalustatud kahendpuu korral on Tv ja Tp enam-vähem võrdse suurusega (näit. kõrguste erinevus kuni 1).