Структури на данни: Дървета
Тази публикация е третата от поредица за структури от данни. Темите, обхванати в тази серия, са 6 основни структури от данни, които ще се появят на всеки вид интервю за софтуерно инженерство:
- Хеш карти
- Свързани списъци
- Дървета
- „Стекове и опашки“
- Купчища
- Графики
Какво е дърво?
Дървото е нелинейна структура от данни, която организира данните по йерархичен начин. Можете да ги оприличите на родословно дърво с много поколения; баби и дядовци, родители, деца и т.н. Родословните дървета са организирани йерархично.
Дървовидната структура на данните е колекция от възли. Тези възли са свързани помежду си чрез ръбове. Всеки възел съдържа стойност (данни) и може да има или да няма дъщерен възел. Във всяко (непразно) дърво първият възел на дървото се нарича корен.
Ако този основен възел е свързан с един или повече възли, той е родителският възел, а свързаните възли са неговите деца. Възлите без деца се наричат листаили външнивъзли. Възлите, които не са листа, се наричат вътрешни възли. Вътрешните възли имат поне едно дете. Възлите с един и същ родител се наричат братя и сестри.
В горното дърво:
- A е родител на B и C.
- B се нарича дете на A.
- B и C са братя и сестри.
- E, F, H, I и J са листа.
Дълбочината на възел е броят на ръбовете от корена до възела. (Дължината на пътя до неговия корен). В горното дърво дълбочината на възела I е 3.
Височината на възел е броят на ръбовете от възела до най-дълбокия лист. (Дължината на най-дългия път до листа). Височината на възелBе 2.
Двоични дървета
Дървовидните възли могат да имат нула или повече деца. Двоично дърво е дърво, в което неговите възли могат да имат не повече от два дъщерни възела. Всеки възел може да има ляв възел и десен възел.
Възлите на двоично дърво обикновено съдържат три части от данни:
- Стойността на възела: цяло число, низ, символ и т.н.
- Указател към лявото дете.
- Указател към десно дете.
Двоични дървета за търсене
Двоичните дървета за търсене са двоични дървета, които изпълняват специфично свойство за подреждане:
Във всяко поддърво левите възли са по-малко от основния възел, който е по-малък от всички десни възли.
Това свойство за подреждане прави търсенето на конкретен възел много бързо, защото можете да имате добра представа къде да търсите в дървото в зависимост от стойността, която търсите.
Да кажем, че търсим възела, който съдържа стойността 4:
Първо разглеждаме основния възел = 10. 4 е по-малко от 10, така че възелът трябва да е от лявата страна.
След това разглеждаме лявото дете = 5. 4 е по-малко от 5, така че възелът трябва да е от лявата страна.
Лявото дете е = 3. 4 е по-голямо от 3, така че възелът трябва да е от дясната страна.
Правилното дете е на 4! Стигнахме до възела, който търсим. С всяка стъпка игнорираме половината от дървото.
Вмъкване в двоични дървета за търсене
Нека се върнем към нашия пример за двоично дърво за търсене:
Да кажем, че искаме да добавим стойността 6.
- Разглеждаме коренния възел = 10. 6 е по-малко от 10, така че отиваме при лявото дете.
- Лявото дете е на5г. 6 е по-голямо от 5, така че отиваме при дясното му дете.
- Дясното дете е9. 6 е по-малко от 9, така че отиваме при лявото дете.
- Лявото дете е нула. Можем да поставим нашия възел там.
Използвайки този метод на вмъкване, понякога можем да имаме небалансирани дървета, в зависимост от това как получаваме възли за вмъкване и как работи алгоритъмът за изграждане на дърво.
В най-лошия случай, ако получим възли: 1 → 2 → 3 → 4, можем да получим дърво като това:
Не е идеален. Това дърво изглежда като свързан списък. Намирането и вмъкването вече няма да бъде толкова бързо, колкото дърво. Балансирано двоично дърво за търсене може да бъде претърсено за O(log n) време, където n е броят на възлите в дървото. Небалансирано дърво като това по-горе ще отнеме O(n) време (линейно време).
Обхождане на двоично дърво за търсене
Има три начина, по които можем да преминем през едно дърво:
- Обхождане по ред: Първо посетете левия възел, след това корена, след това десния. A → B → C.
- Преминаване на предварителна поръчка: Първо посетете корена, след това посетете левия му възел, след това десния. B → A → C.
- Обхождане след поръчка: Първо посетете левия възел, след това десния възел, след това корена. A →C →B.
В бинарните дървета за търсене обикновено искаме да използваме обхождане в ред, защото ни позволява да отпечатаме възлите в ред.
Два алгоритъма, които обикновено се използват за обхождане, са Търсене първо в дълбочина (DFS) и Търсене първо в ширина (BFS). В Depth-First-Search започваме от корена и изследваме, доколкото е възможно, надолу по всеки клон, преди да се върнем назад. Преминаването по ред, преди поръчка и след поръчка попада в DFS. В Breadth-First-Search започваме от корена и изследваме съседните възли, преди да преминем на следващото ниво.
Внедряване на двоично дърво за търсене
Нека създадем Клас възел:
Нашият възел има три части: стойност, ляв указател и десен указател. Нашите указатели първоначално са зададени на нула, защото нашият възел няма деца (все още).
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
Вмъкване
Нека създадем метод за Вмъкване:
Ако стойността, която искаме да добавим, е по-малка или равна на стойността на текущия възел, проверяваме дали вляво. Ако лявото дете е празно, създаваме нов възел с нашата стойност и го добавяме там. Ако не е празно, рекурсивно извикваме нашата функция за вмъкване в левия клон на нашето дърво.
Ако стойността, която искаме да добавим, е по-голяма от текущия възел, поставяме отметка надясно. Ако дясното дете е празно, създаваме нов възел с нашата стойност и го добавяме там. Ако не е празно, рекурсивно извикваме нашата функция за вмъкване в десния клон на нашето дърво.
def insert(self, value):
if value <= self.value:
if self.left == None:
self.left = Node(value)
else:
self.left.insert(value)
else:
if self.right == None:
self.right = Node(value)
else:
self.right.insert(value)
намирам
Следващият метод, който искаме да добавим, е намиране. Find също работи рекурсивно и е подобно на вмъкването по някои начини. find ще приеме стойност и ще върне true, ако я намери, и false, ако не го намери.
Започваме от корена. Ако стойността на корена е равна на стойността, която търсим, връщаме true. Ако не, проверяваме дали стойността е по-малка от стойността на основния възел. Ако е по-малко, проверяваме дали лявата е празна. Ако лявата ни страна е празна, това означава, че дървото не съдържа стойността, която търсим. Ако left сочи към възел, ние рекурсивно извикваме нашия метод за намиране, за да проверим лявата страна на дървото за стойността.
Ако стойността, която търсим, е по-голяма от стойността в основния възел, проверяваме дали десният възел е празен. Ако е така, връщаме false, защото нашето дърво не съдържа тази стойност. Ако дясната страна не е празна, рекурсивно извикваме нашия метод за намиране от дясната страна на дървото.
def find(self, value):
if value == self.value:
return True
elif value < self.value:
if self.left == None:
return False
else:
return self.left.find(value)
else:
if self.right == None:
return False
else:
return self.right.find(value)
Печат (първо търсене в дълбочина)
Нека напишем In-Order DFS метод за печат за нашия клас Node. Както бе споменато по-горе, In-Order отпечатва левия възел, след това корена, след това десния възел.
В нашия метод първо проверяваме дали лявата страна на дървото не е празна. Ако имаме лява страна, рекурсивно извикваме нашия метод за лявата страна на дървото.
Когато достигнем точката, в която лявата страна на възел е нула, ние отпечатваме стойността на този възел. След това се връщаме стъпка назад, за да отпечатаме корена. След това проверяваме дали дясната страна на възела не е празна. Ако има възел вдясно, ние извикваме нашия метод рекурсивно на този десен възел.
def printInOrder(self):
if self.left != None:
self.left.printInOrder()
print(self.value)
if self.right != None:
self.right.printInOrder()
И това е всичко за сега!
Ако искате да знаете как да приложите метода Първо търсене в ширина, това обикновено се прави с помощта на структура от данни Опашка като помощник. Ще разгледам опашките в следващата публикация от поредицата, така че следете!
Благодаря за четенето!
