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

Binary Search Tree

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

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

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

Задача за множество от числа

Нека разгледаме следната задача, която ще се опитаме да решим ефективно.
Дадени са ви много заявки, всяка от които може да е едно от следните пет неща:
  1. Запомни числото X (добавяне на елемент към множеството);
  2. Забрави числото X (премахване на елемент от множеството);
  3. Провери дали числото X в момента е запомнено (питане дали елемент присъства или не в множеството);
  4. Намери най-близкото число до X (търсене на най-близкия по-малък или равен или най-близкия стриктно по-голям елемент на множеството).
  5. Намери най-малкото и най-голямото в момента запомнено число (питане за min/max елемент).
Измислете начин, по който да можете да изпълнявате бързо всяка от заявките.
Понякога последната заявка е не просто за min() и max(), ами за k-тия по големина елемент - генерализация, която също може да се поддържа без промяна в сложностите на останалите операции. В темата, обаче, не сме я имплементирали, за да можем по-чисто да покажем основната идея на двоичните дървета за търсене.

Досегашни знания

Какво можем да направим с досегашните си знания за тази задача?

Масив

Най-най-простият вариант е да ползваме динамичен масив. При всяка заявка от първия тип обхождаме целия вектор за да проверим дали числото вече е запомнено. В случай, че не е, го добавяме в края. При всяка заявка от втория тип обхождаме всички числа за да проверим дали числото присъства (и ако да - на коя позиция). Ако го намерим, го премахваме от вектора. За третия тип заявки отново обхождаме всички елементи и в зависимост дали го намерим отговаряме "да", иначе "не". При четвъртия тип заявки правим пълно обхождане, пазейки търсения най-близък елемент, а за петия - най-малкия и най-големия. Тъй като всяка от операциите е свързана с пълно обхождане на масива, сложностите на всички са O(N).

Сортиран масив

Какво забелязваме при предходния вариант? В много от случаите би било далеч по-удобно, ако през цялото време пазим динамичния масив сортиран. Така, например, третата и четвъртата операция биха били O(log(N)) (ползвайки двоично търсене), а петата - едва O(1). Все пак, тъй като ползваме масив, който трябва да държим сортиран, за да добавим или премахнем елемент ще ни се налага да изместваме известна част от елементите наляво или надясно. Сложността на операции 1) и 2) остава O(N). По-добре, но все пак можем повече!

Сортиран списък

Във варианта със сортиран динамичен масив проблемът идваше от това, че не можем бързо да добавяме и премахваме елементи. Ако помните, в структурата данни свързан списък това ставаше много бързо (константно, т.е. O(1)). За съжаление, ако ползваме списък вместо масив, възниква друг проблем: вече нямаме произволен достъп (random access) до елементите, и, съответно, не можем да прилагаме двоично търсене. Така търсенето на елемент става с O(N), което води и до останалите операции да бъдат с тази сложност. Единствено намирането на минимума и максимума си остават O(1), но като цяло това решение не е подобрение на предходното.

От списък към дърво

Нека разгледаме дали не можем да направим някакви промени по списъка, за да се справим с (част от) проблемите му. Нека имаме двадесет и пет произволни числа в интервала [1, 100]: {63, 86, 3, 12, 5, 6, 68, 99, 86, 4, 36, 32, 41, 27, 58, 77, 78, 93, 100, 91, 17, 42, 23, 74, 32}. Тъй като държим списъка сортиран, подредени те са: (3, 4, 5, 6, 12, 17, 23, 27, 32, 32, 36, 41, 42, 58, 63, 68, 74, 77, 78, 86, 86, 91, 93, 99, 100), тоест списъкът изглежда по следния начин:

Указател към средата

Проблемът на списъка идваше от това, че търсенето на елемент може да отнеме евентуално до N стъпки (където N е броят елементи в списъка).

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

Рекурсивен указател към средата

Хубаво де, но ако разглеждаме "левите" и "десните" елементи на средния като два отделни списъка, то сме в същата задача - трябва отново да намерим някакъв елемент сред някакъв списък. Защо да не приложим трика с указателя към средата още веднъж? Така ще имаме указател към средата (1/2 от списъка), а също така и указатели към елементите в 1/4 и 3/4 от списъка.
Следователно, сега, когато ни питат за елемент X, първо ще гледаме средата. Ако елементът е по-малък от този в средата, ще разглеждаме "левите" елементи, в които пък го сравняваме с елемента в 1/4 (средата на "левите"). В противен случай бихме гледали "десните" елементи, в които бихме го сравнили с елемента в 3/4 (средата на "десните"). Така с три допълнителни елемента и две допълнителни проверки си спестихме 75% (3/4) от работата!

Продължавайки рекурсивно, можем да видим, че със седем допълнителни елемента и три допълнителни проверки бихме си спестили 87.5% (7/8) от работата.

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

Проблем

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

Представете си, че имаме 100 елемента. Указателят към средата ще сочи 50-тия (в сортирания им списък). Сега си представете, че добавим още 100 много малки елемента, които, тъй като държим списъка сортиран, ще отидат в началото му. Понеже не правим нищо да променим указателя към средата, той все още ще си сочи към същия елемент. Това, обаче, сега ще е 150-тия елемент от 200, което определено не е средата.

?Потенциален компромис, който можем да направим, е да имаме указател на всеки sqrt(N) елемента. Така както търсенето, така и обновяването на указателите, ще е със сложност O(sqrt(N)).
Ако след всяка стъпка не обновяваме указателите да сочат към правилните елементи (среди), то не можем да гарантираме, че ще елиминираме половината елементи при избиране на "лява" или "дясна" страна. Тъй като се налага да обновим всички допълнителни елементи, то макар и самото търсене и вмъкване да са бързи, поддръжката на указателите ще е с цена O(N). Което е точно нещото, което искахме да избегнем.

Наблюдение

Забележете, че ако през цялото време вкарваме и изкарваме елементи с произволни (random) стойности, то шансът да попаднат между всеки две "среди" е що-годе равен. Тогава, обаче, средите ще си остават (относително) балансирани дори без допълнително да ги побутваме наляво или надясно всеки път (въпросната "поддръжка", с която се опитвахме да се справим по-рано)!

Така, ако разчитаме, че добавянията и изтриванията ще са на относително random елементи, бихме могли наистина да ползваме O(N) допълнителни указателя, постигайки O(log(N)) сложност на операциите. След като можем да си позволим голям брой "среди", ще ползваме N/2 такива. И тъй като на всяка стъпка елиминираме половината оставащи елементи, реално намирането на елемент ще става за O(log(N)). А тъй като ползваме (нещо като) свързан списък, вмъкването и премахването на елемент между два други ще става за O(1), което означава, че цялата операция се доминира от търсенето, тоест е O(log(N)).

Двоично дърво

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

Донякъде интуитивно, за всеки връх е изпълнено следното:
  • Или няма ляво дете, или то, а и всички негови деца, са по-малки от текущия връх. Наистина, тъй като под-дървото на лявото дете представлява всички елементи "наляво" от дадена среда (текущия връх), то е логично те да са по-малки.
  • Или няма дясно дете, или то, а и всички негови деца, са по-големи или равни на текущия връх. Аналогично на предходната точка, това са елементите, отговарящи на дясната половина от интервала, разцепен от текущия връх (среда).
Забележете, че изискванията за двоично дърво не налагат еднакви числа да бъдат едно до друго в дървото - например, двете срещания на 32 са през един връх едно от друго. Въпреки всичко, всички по-малки числа са "наляво", а всички по-големи или равни - "надясно" от всеки от върховете.

Балансираност на дървото

!Балансирано двоично дърво е двоично дърво, в което разликата във височината на лявото и дясното под-дърво на всеки връх е най-много едно.
Забележете, че в горната картинка дървото е точно такова, каквото го искаме - почти всички върхове имат по два наследника, а които имат по-малко са или листа или просто няма как връх да е под тях без да създадем друг връх на дървото с липсващ наследник.

Такова дърво наричаме "балансирано". Забележете, че то не е "перфектно балансирано", тъй като двете под-дървета на по-горното 32 имат разлика по-голяма от едно.
!Перфектно балансирано двоично дърво наричаме балансирано двоично дърво, в което броя върхове в лявото и дясното под-дърво на всеки връх се различава с най-много едно.
На практика перфектно балансирани дървета се получават много рядко - дори при произволни елементи се очаква то да е поне отчасти небалансирано. За щастие, при рандом елементи то най-често си остава балансирано (или поне е достатъчно близко до такова), че да се запазва сложността от O(log(N)) за всички операции.

Като пример, ето как би изглеждало дървото, ако добавяхме елементите в реда, в който ги генерираме (63, 86, 3, 12, 5, 6, 68, 99, 86, 4, 36, 32, 41, 27, 58, 77, 78, 93, 100, 91, 17, 42, 23, 74, 32). Забележете, че този път двете 32-ки са съседни върхове в дървото, но пък 86-ците не са:
Това дърво е значително по-"грозно" от предходното и има цели осем нива (вместо пет, колкото имаше предходното). Този път то дори не е "балансирано", тъй като лявото под-дърво на корена е с две нива по-високо от дясното такова.

Израждане

В зависимост как постъпват елементите при строенето на дървото, то може да се "изроди" много - потенциално до нещо силно наподобяващо свързан списък! Това, например, би станало ако вкараме вече сортиран лист от елементи. Затова и сложностите на операциите на двоичното дърво за търсене са реално O(N) ако нямаме ограничения какви елементи постъпват в него.

Балансирани дървета

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

Имплементация

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

Данни

Всеки връх от дървото ще държи следните три неща:
  • Един елемент от данните, които искаме да пазим - например, число
  • Указател към лявото дете (или nullptr, ако няма такова)
  • Указател към дясното дете (или nullptr, ако няма такова)
struct
Node {
int
value
;
Node
*
left
,
*
right
;
Node(
int
value_)
:
value(value_)
,
left(nullptr)
,
right(nullptr) {} }
;
Забележете, че не е нужно да държим указател към бащата, тъй като всички операции ще имплементираме рекурсивно и винаги ще го знаем. Вместо да хабим памет и да го пазим във всеки връх, можем да го подаваме като аргумент на рекурсията. Реално, в имплементацията, която сме показали, така сме направили функциите, че дори не е нужно да го подаваме!

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

Търсене на елемент

За да намерим елемент (връх от дървото), почваме от корена и се спускаме надолу по децата, докато намерим този, който ни трябва (или видим, че такъв няма). На всяка стъпка:
  1. Ако стойността на текущия връх е тази, която търсим, спираме.
  2. Ако стойността на текущия връх е по-голяма от тази, която търсим, отиваме в лявото дете. Ако такова дете няма, то значи търсеният елемент не присъства в дървото.
  3. Ако стойността на текущия връх е по-малка от тази, която търсим, отиваме в дясното дете. Ако такова дете няма, то значи търсеният елемент не присъства в дървото.
Точка 1) е тривиална. В точка 2) се справяме със случая, в който трябва да идем в "лявата" половина на списъка - тоест тази, с по-малки елементи. Тъй като търсената стойност е по-малка от текущия връх, а всички по-малки стойности се намират в неговото ляво под-дърво, то е логично да продължим търсенето там. Аналогично, в 3) се справяме със случая, в който трябва да идем в дясната половина на списъка - тоест тази, с по-големи елементи.
Node
*
find(Node
*
current
,
int
value) {
if
(current
=
=
nullptr)
return
nullptr
;
if
(current
-
>
value
=
=
value)
return
current
;
return
find(value
<
current
-
>
value
?
current
-
>
left
:
current
-
>
right
,
value)
;
}
Нека, например, търсим дали дървото съдържа стойността 30. Спускайки се надолу, стигаме до nullptr като се опитаме да слезем в дясното под-дърво на 27, в следствие на което стигаме до извода, че дървото не го съдържа:

Добавяне на елемент

За да добавим нов елемент в дървото, първо трябва да намерим неговата позиция - към кой връх да го закачим. Сходно на търсенето, ще се спускаме надолу към дървото докато стигнем връх, в който можем да го добавим като дете (ляво, ако върхът е по-голям, и дясно в противен случай). Създаваме новия връх и го свързваме в дървото.
Node
*
insert(Node
*
current
,
int
value) {
if
(current
=
=
nullptr) {
return
new
Node(value)
;
}
else
if
(value
<
current
-
>
value) { current
-
>
left
=
insert(current
-
>
left
,
value)
;
}
else
{ current
-
>
right
=
insert(current
-
>
right
,
value)
;
}
return
current
;
}
Нека видим как бихме добавили числото 72 в дървото:

Премахване на елемент

Премахването на елемент е малко по-сложно, тъй като искаме да запазим дървото "двоично" - тоест с максимум два наследника от всеки връх. Отново пускаме търсене в дървото. Има няколко случая:
  1. Ако търсенето не намери връх с тази стойност, то няма какво да премахваме и приключваме (стойността, която искаме да премахнем, я няма и без друго).
  2. Ако търсенето намери връх с тази стойност и този връх няма деца, директно го премахваме. Отбелязваме в бащата му, че въпросният син вече не съществува.
  3. Ако търсенето намери връх с тази стойност и този връх има едно дете, то премахваме върха и закачаме детето му (съответно под-дървото с корен това дете) към бащата му вместо премахнатия връх.
  4. Ако търсенето намери връх с тази стойност и този връх има две деца, то трябва някак да закачим и двете деца за бащата на върха. Тъй като това е невъзможно, вместо това ще сложим друг връх от дървото на мястото на сегашния, запазвайки свойствата на дървото. Този връх трябва да е такъв, че всички върхове в под-дървото на лявото дете да са по-малки от него и всички върхове, в под-дървото на дясното дете да са по-големи или равни. Един връх, който изпълнява тези изисквания, е най-малкият в под-дървото на дясното дете.

Забележете, че в последния (най-сложния) случай, копирайки стойността на най-малкия връх в под-дървото на дясното дете в текущия връх, на практика "изтриваме" стойността на върха, който искахме да изтрием, но пък получаваме второ копие на върха, който копираме. Оригиналното копие, обаче, е по-лесно за изтриване: тъй като той е най-малък в дясното под-дърво, това означава, че има максимум един наследник (десен), тоест влиза в предходните случаи. Така просто пускаме рекурсивно да изтрием него (за да остане отново само едно негово копие).
Node
*
erase(Node
*
current
,
int
value) {
if
(current
=
=
nullptr) {
return
nullptr
;
}
else
if
(value
<
current
-
>
value) { current
-
>
left
=
erase(current
-
>
left
,
value)
;
}
else
if
(value
>
current
-
>
value) { current
-
>
right
=
erase(current
-
>
right
,
value)
;
}
else
{
if
(current
-
>
left
=
=
nullptr
|
|
current
-
>
right
=
=
nullptr) { Node
*
child
=
current
-
>
left
=
=
nullptr
?
current
-
>
right
:
current
-
>
left
;
delete
current
;
return
child
;
}
else
{ current
-
>
value
=
findMin(current
-
>
right)
;
current
-
>
right
=
erase(current
-
>
right
,
current
-
>
value)
;
} }
return
current
;
}
Нека видим какво би се случило, ако решим да изтрием стойността 91 от графа:
Можете да се уверите, че заменяйки 91 с 93 (и "разкачайки" го от 99) графът отново става двоично наредено дърво.

Минимум и максимум

Минимумът и максимумът в двоично дърво се намират доста лесно. До минимума стигаме като вървим единствено по левите деца, докато стигнем до връх без такова. Стойността в този връх е търсеният минимум.
int
findMin(Node
*
current) {
return
current
-
>
left
=
=
nullptr
?
current
-
>
value
:
findMin(current
-
>
left)
;
}
Максимумът е аналогичен, само че движейки се по десните деца.
int
findMax(Node
*
current) {
return
current
-
>
right
=
=
nullptr
?
current
-
>
value
:
findMax(current
-
>
right)
;
}

Най-близък елемент

Често, когато ползваме такива дървета, не ни интересува дали елемент с точно някаква стойност присъства в дървото, а кой е най-близкият по стойност до него. В повечето имплементации за това се имплементират функциите lower_bound(X) и upper_bound(X). Първата намира най-близкото число, по-голямо или равно на X, докато втората - най-близкото, строго по-голямо от X. Тъй като двете са доста подобни, в темата ще покажем само първата (в пълната имплементация можете да видите и втората). Търсенето на по-малки елементи от X отново става доста сходно, затова също са пропуснати.
Node
*
lowerBound(Node
*
current
,
int
value) {
if
(current
=
=
nullptr)
return
nullptr
;
if
(current
-
>
value
=
=
value)
return
current
;
if
(current
-
>
value
<
value)
return
lowerBound(current
-
>
right
,
value)
;
Node
*
left
=
lowerBound(current
-
>
left
,
value)
;
return
left
!
=
nullptr
?
left
:
current
;
}
Например, за lower_bound() за числото X = 10 бихме върнали върха със стойност 12.

Печатане на стойностите

Поради начина, по който дървото държи елементите си, ако изведем стойностите на дървото в ред ляво-корен-дясно, това би довело до печатането им в сортиран ред.
void
printElements(Node
*
current) {
if
(current
=
=
nullptr)
return
;
printElements(current
-
>
left)
;
fprintf(
stdout
,
"%d\n"
,
current
-
>
value)
;
printElements(current
-
>
right)
;
}

Цялостна имплементация

Цялостна имплементация и тестове може да намерите тук: BST.h | BSTTester.cpp.

Допълнителни материали



За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
предишна тема
версия за печат
следваща тема
Страницата е посетена 10003 пъти.

Предложете корекция

Selected text (if you see this, there is something wrong)

(Незадължително) E-mail за обратна връзка: