[Powered by Google Translate] Како би ти представља све чланове своје породице у компјутеру? Ми једноставно да користите листу, али овде је јасна хијерархија. 

Рецимо да смо на почетку са својим пра-баке, Алице. Она има 2 сина, БОБ и твој деда, Чарли. Чарли има 3 деце, твој стриц, Дејв, твоја тетка, Еве, и твој отац, Фред. Ви сте Фредов једино дете. 

Зашто би организовање своје чланове породице на овај начин бити боља од простог листе репрезентације? Један од разлога је да је ова хијерархијска структура, зове "дрво", садржи више информација него једноставним листе. Знамо породичних односа између свих само испитивањем дрво. Такође, може да убрза страховито лоок-уп време, ако дрво подаци сортирају. 

Ми не можемо искористити да се овде, али ћемо ускоро видети пример за ово. Свака особа је представљена чвор на дрвету. Чворови могу имати чворове дете као и родитељ чвора. То су технички услови, чак и када се користи дрвеће за ствари поред породице. Алисин чвор има 2 деце и без родитеља, док је Чарлијев чвор има 3 деце и 1 родитељ. 

Лист чвор је онај који нема децу на спољној ивици дрвета. Највиши чвор стабла, корен чвор, нема родитеља. 

Бинарно стабло је специфична врста дрвета, у којој сваки чвор има, највише, 2 деце. Овде је струцт од чвор бинарног стабла у Ц. Сваки чвор има неке податке у вези са тим и 2 показивачи другим чворовима. 

У нашем породичном стаблу, повезане су подаци били сваке особе име. Овде је инт, мада то може да буде било шта. Како се испоставило, бинарно стабло не би добро представљање за породицу, јер људи често имају више од 2 деце. 

Бинарна претрага дрво је посебан, уређена врста бинарног стабла који нам омогућава да погледамо вредности брзо. Можда сте приметили да сваки чвор испод корена стабла је корен друго дрво, назвао "подстабло. ' Овде је корен стабла је 6, и његов дете, 2, корен подстабло. 

У бинарном стаблу претраге све вредности чвор је у праву подстабло већа од вредности чвора. Ево: 6. Па, вредности у оставио чвора подстабло су мање од вредности чвора. Ако треба да рукује дуплиране вредности, можемо променити било који од оних на лабаву неједнакости, значи идентичне вредности може да падне на лево или десно, док смо доследни о томе све време. Ово дрво је бинарна претрага дрво јер следи ова правила. 

Ово је како би то изгледало да смо се окренули све чворове у Ц Структуре. Приметимо да ако дете нема, показивач је нулл. Како да проверите да ли 7 је у дрвету? Почињемо у корену. Седам је већи од 6, па ако је то у дрвету, она мора да буде са десне стране. Затим, то је мање од 8, тако да мора да остане. Ево, нашли смо 7. Сада ћемо проверити 5. Пет је мање од 6 година, тако да мора да буде са леве стране. Пет је већи од 2, тако да мора да буде у праву, а такође је већи од 4, тако да мора да буде опет десно. Међутим, овде постоји дете. Показивач је нулл. То значи да 5 није у нашем дрвету. 

Можемо претраживати бинарно стабло са следећим кодом: У сваком чвору, проверавамо да ли смо нашли вредност тражимо. Ако га не нађемо, можемо утврдити да ли је то требало да буде лево или десно и проверите да подстабло. Ова петља ће наставити низ дрво док не постоји дете чвор или лево или десно. 

Запамтите да 5 није био у дрвету. Како да га убацити? Процес личи на претрагу. Ми смо прелазили низ стабло, почевши од 6, отишао до 2, Право на 4, и опет десно, већ 4 нема дете на овој страни. То ће бити нови положај за 5, и она ће почети без деце. 

Колико брзо су послови на бинарну претрагу дрвета? Запамтите да Бигохнотатион настоји да обезбеди горњи граница. У најгорем случају, наша стабло може једноставно да буде повезана листа што значи да убацивање, брисање и претраживање могла потрајати пропорционалан броју чворова у дрвету. Ово је О (н). 

На пример, следећи је важећи бинарни претрагу дрво. Међутим, ако покушамо да нађемо 9, морамо да пролазе сваки чвор. То није ништа боља него повезане листе. Идеално, желимо да сваки чвор нашег стабла бинарног претраживања да имају 2 деце. На овај начин, убацивање, брисање и претраживање би предузети, у најгорем случају, О (лог н) времена. Дрво од раније могао бити избалансирана, овако. Сада, гледајући неку вредност узима, највише, 3 корака. Ово дрво је уравнотежен, што значи да је има минималну дубину у односу на број чворова. 

Тражите вредности у уравнотеженом стабла бинарног претраживања је слична бинарне претраге на сортирани низ. У ствари, ако не морамо да убаците или брисање ставки, они се понашају на исти начин. Међутим, дрво је структура боље за руковање уметања и брисања 

Моје име је Баннус Ван дер Клоот. Ово је ЦС50.