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).