[Powered by Google Translate] Как бихте представлява всички членове на семейството в компютъра? Бихме могли просто да използвате списък, но тук има ясна йерархия. 

Да кажем, че започваме с прабаба ви, Алис. Тя има два сина, Боб и дядо ти, Чарли. Чарли има три деца, чичо ти, Дейв, леля ти, Ева и баща си, Фред. Вие сте единствено дете на Фред. 

Защо организиране на вашите членове на семейството по този начин да бъде по-добре, отколкото просто представителство списък? Една от причините е, че тази йерархична структура, нарича "дърво" съдържа повече информация, отколкото на обикновен списък. Ние знаем, че семейните взаимоотношения между всички само чрез изследване на дървото. Също така, тя може да се ускори поглед нагоре време значително, ако дървесни данните се сортират. 

Ние не можем да се възползват, че тук, но ще видим скоро пример за това. Всеки човек се представлява от възел на дървото. Възлите могат да имат дете възли , както и като родител възел. Това са техническите термини, дори при използване на дървета за други неща освен семейства. Възел Алис има две деца и не родители, , докато възел на Чарли има 3 деца и 1 майки. 

Листо възел е този, който не разполага с никакви деца на външния ръб на дървото. Горната възел на дървото, коренът, има никой родител. 

Двоично дърво е специален вид на дървото, , в която всеки възел има най-много две деца. Ето структура на възел на двоично дърво в C. Всеки възел има някои данни, свързани с него и 2 указатели към други възли. 

В нашето семейство дърво, свързаните с тях данни е името на всеки човек. Ето това е едно цяло число, въпреки че тя може да бъде всичко. Както се оказва, дърво двоичен не би било добро представяне за семейство, тъй като хората често имат повече от 2 деца. 

Двоично търсене дърво е специален, подреден вид на двоично дърво , която ни позволява да гледаме при стойности бързо. Може би сте забелязали че всеки възел под корените на едно дърво е в основата на друго дърво, наречено "дървото". Тук, коренът на дървото е 6, и нейното дете, 2, е корен на поддърво. 

В двоично дърво за търсене всички стойности на възел е прав поддърво са по-големи от стойността на възела. Тук: 6. Е, стойностите в лявото поддърво възел са по-малко от стойността на възела. Ако ние трябва да се справят с повтарящи се стойности, ние можем да променим нито един от тези до хлабава неравенство, което означава, идентични стойности могат да паднат или на ляво или дясно, толкова дълго, колкото ние сме за това цялата. Това дърво е двоично дърво за търсене , тъй като следва тези правила. 

Това е как тя ще изглежда, ако ние се обърнахме всички възли в structs C. Забележете, че ако едно дете липсва, показалецът е нищожна. Как да проверите, за да видите, ако 7 е в дървото? Ние започваме в корена. Седем е по-голяма от 6, така че ако това е в дървото, то трябва да бъде в дясно. След това, той е по-малко от 8, така че трябва да се оставят. Ето, ние открихме 7. Сега, ние ще проверим за 5. Five е по-малко от 6, така че трябва да бъде отляво. Five е по-голямо от 2, така че трябва да се прави, а също така е по-голяма от 4, така че той трябва да бъде отново надясно. Въпреки това, няма дете тук. Показалецът е нула. Това означава, че 5 не е в нашето дърво. 

Можем да търсим двоично дърво със следния код: На всеки възел, ние проверяваме, за да видим дали ще са намерили стойността, която ние търсим. Ако ние не го намери, ще се определи дали тя трябва да бъде наляво или надясно и провери дали поддърво. Тази линия ще продължи надолу по дървото докато има нито едно дете възел на лявата или дясната. 

Не забравяйте, че 5 не е в дървото. Как да го вмъкнете? Процесът прилича да търсите. Ние обхождане на дървото, като се започне от 6, ляво до 2, право на четири, и отново на дясно, но 4 има нито едно дете от тази страна. Това ще бъде нова позиция за 5 и тя ще започне без деца. 

Колко бързо са операциите на двоично дърво за търсене? Не забравяйте, че Bigohnotation се стреми да предостави горната граница. В най-лошия случай, нашето дърво може просто да бъде свързан списък което означава, че вмъкване, изтриване и търсене може да отнеме време, пропорционално на броя на възлите в дървото. Това е O (N). 

Например, следния ред е валиден двоично търсене дърво. Въпреки това, ако се опитваме да намерим 9, ние трябва да преминават всеки възел. Това не е по-добре, отколкото свързан списък. В идеалния случай бихме искали всеки възел на нашето дърво за двоично търсене, за да имат две деца. По този начин, вмъкване, изтриване и търсене ще отнеме, в най-лошия случай, O (дневник н) време. Дърво от преди може да бъде по-балансиран, по този начин. Сега, каквато и да е стойност отнема най-много три стъпки. Това дърво е балансирано, което означава, че е с минимална дълбочина в сравнение с броя на възлите. 

Търся стойност в балансирано двоично търсене дърво е подобен на двоично търсене в сортиран масив. В действителност, ако ние не трябва да поставите или изтриване на елементи, те се държат точно по същия начин. Въпреки това, дървовидна структура е по-добре за обработка на вмъквания и изтривания 

Моето име е Bannus Ван дер Kloot. Това е CS50.