SHPORA.net :: PDA | |
Main FAQ гуманитарные науки естественные науки математические науки технические науки 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). |