шпаргалка

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









КАТЕГОРИИ:

Network | английский | архитектура эвм | астрономия | аудит | биология | вычислительная математика | география | Гражданское право | демография | дискретная математика | законодательство | история | квантовая физика | компиляторы | КСЕ - Концепция современного естествознания | культурология | линейная алгебра | литература | математическая статистика | математический анализ | Международный стандарт финансовой отчетности МСФО | менеджмент | метрология | механика | немецкий | неорганическая химия | ОБЖ | общая физика | операционные системы | оптимизация в сапр | органическая химия | педагогика | политология | правоведение | прочие дисциплины | психология (методы) | радиоэлектроника | религия | русский | сертификация | сопромат | социология | теория вероятностей | управление в технических системах | физкультура | философия | фотография | французский | школьная математика | экология | экономика | экономика (словарь) | язык Assembler | язык Basic, VB | язык Pascal | язык Си, Си++ |