Двоично дърво за търсене
Определяне на двоично търсене на дърво (двоично дърво за търсене, BST)
Червено-черно дървета (червено-черно дърво, RB-Tree)
Сравнителни характеристики на скоростта на различните структури от данни
Определяне на двоично търсене на дърво (двоично дърво за търсене, BST)
Binary търсене дърво (MDC) нарича дървото на всички, чиито върхове са разположени така, че всеки възел има най-много две деца (нека ги наречем вляво и вдясно) и всички възли, с изключение на корена имат родител. Top, които нямат наследници, наречени листове. Разбираемо е, че всеки възел съответства на елемент или няколко елемента, с някои основни ценности, наричан по-нататък ключ. Обикновено един връх съответства на един елемент, така че тези условия са възможни без загуба на смисъл считат синоними, въпреки че ние трябва да помним, че това не е така в някои изпълнения. В горните алгоритми, като се смята, че един връх има само един елемент. Ето защо, ние ще използваме понятието върха и на върха на основните данни, което означава, клавиша за данни и съответния елемент на върха. Ние също така ще се разбере чрез вмъкване на върха на добавянето на върха с определения стойността на елемента и да се определят признаците на компанията майка и потомци на валидни стойности. Тази ключ се използва при всички операции на елементите на сравнение. Елементът може да съдържа и данни, свързани с ключа. На практика, в частта с данните на елемента може да се използва като ключов. Ключът може също да се съхранява като една стойност. MDC може да изпълнява следните действия:
- Търсене на върха на ключа.
- Определяне на върха с минималната и максималната стойност на ключ.
- Преминаване към предишната или следващата връх в ключовете реда, определен.
- Поставете върха.
- Премахване на върха.
Binary дърво може да бъде разделена на логически нива. Коренът на дървото е на нулево ниво, потомците на корена - на първо ниво, техните наследници - втори и т.н. Дълбочината на дървото е максималното си ниво. дълбочина концепция може да бъде описан по отношение на пътя, т.е. дълбочината на дървото е дължината на най-дългия път от корен на листа, ако последвано от възела родител на дете. Всеки върха на дървото може да се разглежда като коренът на поддървото, който се определя от даден връх и всички потомци на този възел, преки и непреки. Така че дървото може да бъде описан като рекурсивни структура. дърва търсене ефективност е пряко свързано с равновесие, което е, с максимална разлика между дълбочината на лявото и дясното поддървета на всички възли. Има две крайни случаи - балансирано двоично дърво (където всяко ниво е с пълен набор от върха) и дегенерат дърво, където е необходимо, всяко ниво на върха на един. Дегенеративна дърво е еквивалентно на списъка свързани. Изпълнението на всички основни операции, пропорционално на дълбочината на дървото. Така търсене високоскоростен в спецификациите DCF може да варира от О (log2 N) в случай на пълно дърво О (N) - в случай на дегенеративен.
DCF може да се използва за изпълнение на такива абстракции като сортиран списък, речник (набор от съответствия "ключ-стойност"), приоритетна опашка, и така нататък.
При изпълнението на дърво, освен ключовата стойност (ключ) и данни, да се съхранява три насоки: на родителя (нето), наляво (вляво) и десния (вдясно) потомци. Ако родител или дете на не, показалеца магазини нула (NULL, NIL) стойност.
двоично дърво за търсене поръчка имот
Ако X - е произволна връх в ПДД и у връх се намира в горния ляв под х, след това y.key <= x.key. Если x – это произвольная вершина ДДП, а вершина y находится в правом поддереве вершины x, то y.key>= X.key. От имота следва, че ако y.key == x.key, а след това у връх може да бъде както в ляво и дясно поддърво по отношение на връх х.
Трябва да се помни, че наличието на няколко върха, с едни и същи ключови стойности са някои алгоритми няма да работи коректно. Например, алгоритъма за търсене на винаги ще се върне указател към само един връх. Този проблем може да бъде решен чрез съхраняване на елементите с едни и същи клавиши в една и съща върха в списък. В този случай, ние ще запази същия връх няколко елемента, но случаят не се счита в статията.
Това е двоично дърво за търсене:
Заобикаляне DCF
Има три начина да работят около: Директни (предварителна поръчка), Cross (Inorder), назад (postorder).
- Директен прескачането: първо разходите даден връх, лявото поддърво на този възел, а след това на дясно-дървото на този възел.
- Напречно прескачането: първо разходите ляво поддърво на върховете, а след това връх, след това дясното-дървото на този възел. Пикове при същите ще последват в не-намалява (с ключове ключ) ред.
- Обратните прескачането: първо разходите ляво поддърво на върховете, а след това надясно, след това връх.
На Фигура 3, ред е посочено номера връх преминаването през, се приема, че самите върховете са подредени така, че да образуват DCF.
Най-често използваният кръстосано кръг, както и във всички други начини да заобикалят последователни върхове не са обвързани с условията на връзката.
Търсене върховете в ПДД
Търсене Идеята е проста. Алгоритъмът за търсене на ПДД по своята същност са рекурсивни. описание му е най-лесно да се използва понятието поддърво. Търсенето започва от корена, която се приема като в основата на сегашната-дървото и неговата ключова се сравнява с желания адрес. Ако те са равни, очевидно е, че търсенето е приключила. Ако ключът е, че ние търсим, се оказа по-голям от тока, очевидно е, че желания връх се намира в дясно-дървото, в противен случай - в ляво. Освен това, тази операция се повтаря за ляв или десен-дървото. В конвенционалната код, това може да бъде описан, както следва:
Търсене на върха с минимална и максимална стойност за ключа
Топ с минимална и максимална стойност може да се намери ключа, ходене до ляво (вдясно) знаците от корена (докато стигнем до NIL). Връщане стойност - указател към върха на минимум (максимум) стойност за ключа.
Намирането на следващите и предишните върхове в ПДД
За да намерите предишния и следващия възел, е необходимо още веднъж да си припомним за поръчки имота. Помислете за това, както е например функция за TreeNext. Той смята, че двете дела. Ако дясното-дървото не е празна, а след това на върха на дясната поддървото с минималната стойност на ключа и ще бъде по-нататък. Ако дясното-дървото е празен, тогава ние ще вървим напред, докато не се намери на върха на която е в лявата дете на неговата майка. Този родител (ако има такива) и ще бъде следващата върха. Връщане стойност - указател към върха на следващия (предишна) стойността на клавиш или нулев, ако няма такъв връх.
Добавянето на връх
Добавянето на върха в ПДД е свързано с някои проблеми. След добавянето на DCF би трябвало да запази собствеността на поръчката, което означава, че на върха, където не може да се добави. Ето защо, преди да я поставите на върха, трябва да се намери подходящо място за него, а след това има едно място, след вмъкване, в която дървото ще запази своята поръчка собственост. С други думи, ние се нуждаем от място, след като в началото на ключа с най-високата от всички по-малкото.
Премахване на върха
Проблеми възникват при отстраняване. Ние трябва да се запази разпорежда с имуществото на Движението за демократична промяна. Когато е възможно премахването на три случая: премахнахме върха е без деца, които са отстранили върха има наследник на и отстраняват първите две деца. Ако децата не трябва, можете просто да се премахне горната част. Ако едно дете сам, след това извадете горната част, можете да "рязани", сочейки към родителите си като дете на единствената налична потомък сменяем върха. Ако са необходими потомците на две допълнителни стъпки. Трябва да намерим следното за изтрита (по реда на клавиши) върха, да копирате съдържанието му (ключа и данни), с възможност за сваляне върха (сега тя няма да бъде премахната физически, но логично да изчезне), а след това извадете горната част (тя няма да бъде оставено дете). Първо TreeDelete функция търсения на върха, която искате да изтриете, след nodeTemp променлива се присвоява указател към съществуващата детето напускане на върха (или нулев, ако децата не са). На следващо място, на върха се отстранява от дървото, и случаите, разгледани отделно, когато децата не са и когато сменяем връх - е в основата на дървото. Връщане стойност - указател към горната част на дистанционното управление. На това няма отношение в дървото, но тя все още се памет. Времето на реалното му отстраняване зависи от използваните методи за разпределение на паметта.
NIL, NULL, както и малки трикове
Сега навсякъде в клас променлива Ctree може да се използва treeNil. Предимствата са очевидни. След като прекарва известно дванадесет (3 * sizeof (Ctree *)) байта памет, ние сме на опростяване и ускоряване на развитието на програмата.
Основният проблем за използване на DCF
Основният проблем при използването на DCF е, че вмъквания и отстраняване на върха, като се гарантира запазването на ред имущество, то не е благоприятна за оптимизиране на основните операции в Движението за демократична промяна. Например, ако поставите в последователността PDD увеличаване или намаляване на броя, става в действителност, двойно-свързан списък, както и основните операции ще отнеме време, пропорционално на броя на върховете, а не неговата логаритъм.
По този начин, за O (log2 N) от порядъка на нужда изпълнение на дърво имаше възможно най-високо салдо (т.е. вероятно е по-малка височина). разпределени Обикновено няколко вида баланс. Пълният баланс е, когато на върха на дървото за всяка броят на върховете в лявото и дясното поддървета се различава с не повече от 1. За съжаление, този баланс е трудно да се постигне на практика. Поради това, на практика, тя се използва по-малко строги форми на баланс. Така например, са разработени на българските математици GM Аделсън-Belsky и принципи E.M.Landisom AVL дървета. В AVL дърво за всеки връх двете поддървета на дълбочина дърво не се различават с повече от 1. Друг "напреднали" изглед дърво е т.нар червено-черно дърветата. AVL дървета осигуряват по-добър баланс на дървото, но разходите за поддържането им по-горе. Тъй като на практика разликата в баланса между тези два вида дървета не са високи, често се използва от червено-черно дървета.
Червено-черно дървета (червено-черно дърво, RB-Tree)
Така че, един от начините за решаване на основните проблеми при използването на DCF са червено-черно дървета. Червено и черно (името е исторически свързана с карти за игра, тъй като на техните лесно да се направи прости модели) дървета (PSA) - с DCF, всеки връх на който съхранява още един допълнителен логически поле (цвят), което показва цвета: червено или черно. В действителност, PSA е гарантирано, че нивата на всеки два листа се различават с не повече от два пъти. Това състояние е достатъчно за осигуряване на висока скорост близо изпълнение търсене на О (log2 N). Когато поставите / замяна на допълнителните стъпки на балансиране дърво, което не може да се забави дървото. При описанието на алгоритмите приемем, че NIL - указател към върха на манекена и операции (NIL) .left, (NIL) .right, (NIL) .color смисъл. Ние също така ще приемем, че всеки възел има две деца, а само NIL още няма деца. По този начин, всеки връх става отвътре (като потомци, макар и фиктивна) и листата ще фиктивно само връх нула.
свойства PSA
- Всеки връх може да бъде или червено или черно. Безцветни върхове, или върховете на различен цвят не може да бъде.
- Всеки лист (NIL) е черен.
- Ако възелът е червен, а след това и двете си деца - черно.
- През целия път от корена до листата съдържат еднакъв брой черни възли.
Пример PSA като се има предвид нашите позиции е показано на фигура 4. Обърнете внимание, че най-добре 9 може да е червен, но в бъдеще ще се спрем само на тези дървета, чиито корен е черно. Ние ще направим това, за да се изкорени потомци може да има всеки цвят.
вмъквания и изтривания на върха в PSA свойства могат да нарушат PSA. За да възстановите тези функции, вие ще трябва да се пребоядиса някои върхове и промяна на структурата на дървото. За да се промени структурата използвани операции, наречено ротация. Връщайки се на PSA имоти, въртене също се възстанови баланса на дървото. Ротации се наляво и надясно, те са показани на Фигура 5.
Както може да се види, въртене, преместване върховете не нарушават свойствата на поръчване.
Процедурата RBTLeftRotate Предполага се, че node.right! = Нула. Процедурата RBTRightRotate Предполага се, че node.left! = Нула.
Таблица 6. Отстраняване на ключовия елемент (произволни клавиши)
Постоянно сортиран масив
Не е сортиран масив
Array postsortirovkoy
Таблица 7. Прибавянето елемент (увеличаване ключове)
Постоянно сортиран масив
Не е сортиран масив
Array postsortirovkoy
Таблица 8. Търсене елемент (увеличаване на клавиши)
Постоянно сортиран масив
Не е сортиран масив
Array postsortirovkoy
Таблица 9. Отстраняване на ключовия елемент (увеличаване на клавиши)
Постоянно сортиран масив
Не е сортиран масив
Array postsortirovkoy
Таблица 10. Прибавянето елемент (случайни ключове)
Постоянно сортиран масив
Не е сортиран масив
Array postsortirovkoy
Таблица 11. Търсене елемент (произволни клавиши)
Постоянно сортиран масив
Не е сортиран масив
Array postsortirovkoy
ТАБЛИЦА 12. Премахване на ключовия елемент (произволни клавиши)
Ясно се вижда, че по-големите по размер дървета погледите и дори значително превъзхождат масиви. По този начин става ясно, че изборът на структурите от данни е силно зависим от прогнозния брой елементи и техния размер. Накрая бих искал да кажа, че правилният избор на структурата на данните е един от основните точки, които определят ефективността на програмата. Затова при избора внимателно, мислейки през всичко е възможно - като най-вероятното и най-лошия случай.