Двоично дърво за търсене - studopediya

А двоично дърво се нареди, ако за всеки връх х е вярно такъв имот: всички елементи, съхранени в лявата-дървото е по-малко, отколкото се съхранява при х елемент. и всички елементи, които се съхраняват в дясното поддърво голям елемент се съхранява при х.

Важно наредено дърво имот: всички негови елементи са различни. Ако има едни и същи елементи в дървото, дървото е частично наредено.

В бъдеще, ще има да се поръча само двоични дървета, думата "хармонизиране" ще бъдат пропуснати.

Tree Search (търсене дървета) ви позволяват да извършвате следните операции с Дийн
мическите комплекта: Search (търсене), Минимална (най-малко), Максимална (макро-
максимума на), предшественик (предишен), наследник (следващо), Insert (vsta-
вит) и Delete (изтриване). По този начин, дървото за търсене може да бъде Използването
Поканата и други подобни речник, и като приоритетна опашка.

Основният път на работа е пропорционално на височината на дървото. ако
двоично дърво "гъсто попълнено" (всичките му нива са с максимално възможно
Noe брой върхове), височината му (и по този начин изпълнението на операциите)
е пропорционално на логаритъма на броя на върховете. Напротив, ако predstavlya- на дърво
линейна от п върхове, този път расте.

Разбира се, в практиката възникват двоично дърво за търсене може да бъде
далеч от случаен. Въпреки това, чрез приемането на специални мерки за балансиране на де-
revev, можете да се гарантира, че височината на едно дърво с N върха е O (дневник н).

Изпълнение на дейностите ще се счита за двоично дърво представени като динамична структура.

Изпълнение на това може да се намери под формата на подходящи процедури.

Алгоритъмът за търсене може да се запише в рекурсивно форма. Ако стойността е по-малко, т Tree ^ .Data, търсенето продължава в левия поддървото ако е - търсене се счита за успешно, ако повече - търсенето продължава в правилната-дървото; търсене се счита за провал, ако стигне празен поддърво, а той не бе намерен елемент.

функционира TreeSearch (т: TypeElement; Дърво: PTree): булева;

ако Tree <> нула след това да започне

ако в момента ^ .Data = т тогава

TreeSearch: = TreeSearch (т, в момента ^ .Left)

TreeSearch: = TreeSearch (т, Current ^ .Right);

Обява 3.15 - Процесът на търсене в двоично дърво в Паскал

Обява 3.24 - рекурсивни процедура за търсене в двоично дърво за търсене

Обява 3.25 - nonrecursive (повтарящ се) Търсете процедура в двоично дърво за търсене

Минимален и максимален

Минимална ключ в дървото на търсене може да се намери, като следвате оставени знаци
от корена (докато стигнем до NIL). Процедурата връща указател
минимален елемент на поддървото с корен х.

Обява 3.26 - процедура за търсене на минималната елемент в двоично дърво за търсене

поръчване функция осигурява правилните процедури

Tree-
Минимална. Ако върховете х не лявото дете, минималният елемент
поддърво с корен х е х. тъй като всеки ключ в правилната-дървото не е
по-малко ключ [X]. Ако левият-дървото на връх х не е празна, а след минимум
поддърво корен елемент х е разположен в лявото поддървото (като
той е всички елементи на дясното поддърво-голям).

Дърво-Максимална симетричен алгоритъм:

Обява 3.27 - търсене процедура максимален елемент в двоично дърво за търсене

И двата алгоритми изискват време O (з), където H - височина на дървото (защото дървото само се движи надолу).

Следващите и предишните елементи

Как да намерите в двоичен дърво елемент след данните? имот
поръчка ви позволява да направите това чрез преместване на дървото. Това е процедурата,
която връща указател към следващия елемент на х (ако всички ключове
са различни, тя съдържа следващият по-голям ключ) или нулев, ако елемента -
последни в дърво:

Обява 3.28 - процедури за търсене трябва да са (в смисъл на ред на клавишите) в двоично дърво за търсене

процедура Tree-Приемник отделно помисли два случая. Ако pra-
вой поддърво връх х празна, на следващия елемент на х минимален елемент в този поддърво и равно Tree-Минимална (вдясно [х]).

Да предположим сега, че дясното-дървото на връх х е празен. След това отидете от х до
докато не намерим връх, който е в лявата детето от неговите родители (линии
3-7). Това родител (ако има такава) е желания елемент. официално
казано, цикълът на линии 4-6 запазва имота: у = р [Z]; търсене артикул
елементи веднага следва поддървото корени на х.

Докато работи процедури Tree-наследник на височина ч дървото има O (з),
защото ние се движим или само нагоре или само надолу.

процедура Tree-предшественик е симетрична. По този начин, ние сме се оказа следната теорема.

Теорема. Операция Търсене, минимални, максимални, наследник и височина предшественик ч на дървото се изпълняват във време O (з).

Добавяне и премахване на

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

процедура TreeAdd (т: TypeElement; Var Дърво: PTree);

NewNode, в момента: PTree;

ако Tree = нула след това да започне

Обява 3.31 - Процедура за премахване на елемент от двоично дърво за търсене

Обява 3.32 - Процедура за премахване на елемент от двоично дърво за търсене

Фигура 3.14 - Премахване на елемент от двоично дърво за търсене

Изтриването на връх Z от двоично дърво за търсене. (А) Ако възел Z е без деца може да се отстранява без проблеми. (6) Ако възел Z има едно дете, ние го въведе връх Z. (В) ако връх Z има две деца, процесът се намалява
към предишния случай, т.е. вместо да го премахнете от върха до непосредствено след
ключова стойност (в този дете върховете един) и поставяне на ключ KEU [Y] (и свързаните с тях
допълнителни данни) за пускане на връх Z.

Процесът на обработка на дървесина се прилага метод обратна прекосява. Използване на обратната заобиколно решение гарантира, че първо ще бъдат посетени и отстранява всички потомци на прародител преди самият премахване прародител.

процедура TreeClear (VAR Дърво: PTree);

ако Tree <> нула след това да започне

Обява 3.33 - Процедура за двоично дърво за търсене клиринг

сложността на време на тази операция е O (N).

Случайни Дървета Търсене

Случайни търсене дървета са подредени двоично дърво за търсене, за създаването на която елементите (ключове) се вмъкват в случаен ред.

Създаването на такива дървета, използващи същия алгоритъм като при добавяне на върха в двоично дърво за търсене. Ще създаде ли това дърво на случаен принцип, или не, това зависи от реда, в който елементите идват да добавите. Примери на различни дървета, създадени при различни FIFO елементи са дадени по-долу.

Фигура 3.15 - Случайни и изродени търсене дървета

Като елементи пристигат случайно получите едно дърво с височина часа (вж. Фиг. 3.12.a) и съответно намалява търсене елемент време в такова дърво, което е пропорционално на O (влезте н). Като елементи пристигат в един подреден начин (вж. Фиг. 3.12.b) или в малко по-необичаен начин (вж. Фиг. 3.12.v) дървета от търсенето изграждане дегенерат (тя се изроди в линеен списък), която не се намали времето за търсене, което е О (п).

Оптимални за търсене дървета

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

пи - вероятността аргумент за търсене е Ki;

q0 - вероятността, че аргументът за търсене е по-малко от К1;

QN - вероятността, че аргументът за търсене е по-голямо от Кн;

След това търсене дърво цена C ще се определи по следния начин:

където levelrootj - ниво възел й. и levellistk - ниво лист к.

търсене дърво се нарича оптимален, ако цената е минимална или, с други думи, за оптимално двоично търсене дървото - това е двоично дърво за търсене изградени въз основа на постигане на максимална ефективност за дадена дистрибуция на данни, необходими за търсене вероятности.

Има подход за изграждане на оптимални търсене дървета, в които са вмъкнати елементи в низходящ ред по отношение на честотата, което дава средно по добри от търсенето дървета. Въпреки това, този подход може да осигури дегенерат търсене дърво, което е далеч от оптималното.

Друг подход е да изберете основата на к, така че максималната сума от вероятностите за върховете на лявото-дървото и дясното-дървото е толкова малка, колкото е възможно. Този подход може да бъде лошо в случая на избор, като корен елемент с малка стойност на РК.

Има алгоритми, които позволяват да се изгради оптимална търсене дърво. Те включват, например, на алгоритъм Гарсия Vocea. Въпреки това, тези алгоритми имат сложност време на ред O (N 2), и някои от тях дори имат една и съща пространствена сложност. По този начин, създаването на оптимални търсене дървета изисква много режийни разходи, които не винаги могат да бъдат основание за печалби в бързо търсене.