Разлика между бинарно дърво и двоично дърво за търсене
Share
Какво е бинарно дърво?
Binary Tree е йерархична структура на данни, в която всеки възел има нула, едно или най-много две деца. Всеки възел съдържа „лев“ указател, „десен“ указател и елемент от данни. „Коренният“ показалец представлява най-горния възел в дървото. Всеки възел в структурата на данните е директно свързан с произволен брой възли от двете страни, посочени като деца. Нулевият показалец представлява двоичното дърво. Няма конкретен ред как да се организират възлите в двоичното дърво. Възлите без деца възли се наричат листови възли или външни възли.
Казано по-просто, тя определя организирана функция за етикетиране на възлите, която от своя страна присвоява някаква произволна стойност на всеки възел. Всичко, което има две деца и един родителски възел, е двоично дърво. Двоичните дървета се използват за съхраняване на информация, която формира йерархия като файловата система на вашия личен компютър. За разлика от масивите, дърветата нямат горна граница на броя на възлите, защото са свързани с помощта на указатели, като свързани списъци. Основните функции на Binary Tree включват представяне на йерархични данни, сортиране на списъци с данни, осигуряване на ефективни операции за вмъкване / изтриване и др. Възлите на дървото са представени с помощта на структури в C.
Какво е дърво за двоично търсене?
Двоично дърво за търсене е вид структура от данни за двоично дърво, в която възлите са подредени по ред, оттук и наричани „подредено бинарно дърво“. Това е възлова базирана структура на данни, която осигурява ефективен и бърз начин за сортиране, извличане, търсене на данни. За всеки възел елементите в лявото поддърво трябва да са по-малки или равни на ключа в неговия родителски възел (LP). Не трябва да има дублиращи се ключове. Казано по-просто, това е специален вид структура от данни за двоично дърво, която ефективно съхранява и управлява елементи в паметта.
Той позволява бърз достъп до информация, вмъкване и премахване на данни, плюс може да се използва за прилагане на таблици за търсене, които позволяват търсене на елементи по техните уникални ключове, като търсене на телефонния номер на човек по име. Уникалните клавиши са сортирани по организиран начин, така че търсенето и други динамични операции могат да се извършват с помощта на двоично търсене. Той поддържа три основни операции: търсене на елементи, вмъкване на елементи и изтриване на елементи. Двоичното дърво за търсене позволява бързо извличане на елементи, съхранявани в дървото, тъй като всеки ключ на възела се сравнява старателно с коренния възел, който изхвърля половината от дървото.
Разлика между бинарно дърво и двоично дърво за търсене
- Определение на Binary Tree и Binary Tree Search - Binary Tree е йерархична структура на данни, в която детето може да има нула, един или максимум два детски възла; всеки възел съдържа лев указател, десен указател и елемент от данни. Няма конкретен ред за това как трябва да бъдат организирани възлите в дървото. Двоичното дърво за търсене, от друга страна, е подредено бинарно дърво, в което има относителен ред за това как трябва да бъдат организирани възлите.
- структура на Двоично дърво и Двоично дърво за търсене- Най-горният възел в дървото представлява кореновия показалец в двоично дърво, а левият и десният указатели представляват по-малките дървета от двете страни. Това е специализирана форма на дърво, която представя данни в дървесна структура. Двоичното дърво за търсене, от друга страна, е вид двоично дърво, при което всички възли в лявото поддърво са по-малки или равни на стойността на коренния възел, а тази на дясното поддърво е по-голяма или равна на стойността на коренния възел.
- операция на Двоично дърво и Двоично дърво за търсене- Бинарното дърво може да бъде всичко, което има две деца и един родител. Общите операции, които могат да се извършват на бинарно дърво, са вмъкване, изтриване и преминаване. Двоичните дървета за търсене са повече от сортирани двоични дървета, което позволява бързо и ефективно търсене, поставяне и изтриване на елементи. За разлика от бинарните дървета, дърветата за двоично търсене поддържат сортирането на ключовете си, така че търсенето обикновено осъществява двоично търсене за операции.
- Видове на Двоично дърво и Двоично дърво за търсене- Съществуват различни видове двоични дървета, като често срещаните са „Пълно бинарно дърво“, „Цялостно бинарно дърво“, „Перфектно бинарно дърво“ и „Удължено двоично дърво“. Някои често срещани видове дървета за двоично търсене включват T-дървета, AVL дървета, Splay дървета, дървета Танго, Червено-Черни дървета и т.н..
Двоично дърво срещу бинарно дърво за търсене: Сравнителна диаграма
| Двоично дърво | Двоично дърво за търсене |
| Двоично дърво е специализирана форма на дърво, която представлява йерархични данни в дървовидна структура. | Двоично дърво за търсене е вид двоично дърво, което поддържа клавишите в подреден ред за бързо търсене. |
| Всеки възел трябва да има най-много два дъщерни възла, като всеки възел е свързан от точно един друг възел чрез насочен ръб. | Стойността на възлите в лявото поддърво е по-малка или равна на стойността на коренния възел, а възлите в дясното поддърво имат стойности, по-големи или равни на стойността на коренния възел. |
| Няма относителен ред за това как трябва да бъдат организирани възлите. | Следва окончателен ред за това как трябва да бъдат организирани възлите в дърво. |
| По същество това е йерархична структура на данните, която е съвкупност от елементи, наречени възли. | Това е вариант на двоичното дърво, в което възлите са подредени в относителен ред. |
| Използва се за бързо и ефективно търсене на данни и информация в дървовидна структура. | Използва се главно за вмъкване, изтриване и търсене на елементи. |
Обобщение на двоичното дърво и бинарното дърво за търсене
Докато и двете симулират йерархична дървовидна структура, представляваща колекция от възли, като всеки възел представлява стойност, те са доста различни един от друг по отношение на начина, по който могат да бъдат реализирани и използвани. Бинарното дърво следва едно просто правило, че всеки родителски възел има не повече от две дъщерни възли, докато бинарното дърво за търсене е само вариант на бинарното дърво, което следва относителен ред на това как възлите трябва да бъдат организирани в дърво.
