Trees Flashcards
What is a tree?
- Дървото е абстрактна нелинейна структура от данни;
- Има само един Root
- Всеки Node има само един Parent
- Дори и да няма нито един елемент (Node) все още се води за дърво
- Node, който е с нула или повече деца също е дърво сам по себе си;
- Дървото е рекурсивна структура (трябва да се обхожда чрез рекурсия, за да достигнем до всеки елемент). Тази дефиниция трябва да е изпълнена рекурсивно за всички елементи (Nodes), за да можем да кажем, че тази структура е дърво
- Дървото не може да зацикля. Посоката е винаги от родител към деца. Не може да имаме повече от един родител.
Tree Terminology
Node - възел/елемент, който съдържа стойност
Edge – ребро/ връзки между Nodes
Root – корен, той няма корен сам по себе си
Child – дете, има само един родител
Parent – Node, който има деца
Siblings – Node-ве, които имат един и същ родител
Descendant – наследници – това са всички Node-ве, които могат да бъдат достъпени тръгвайки от даден родител към децата на децата.
Ancestor – това са Node-ве, които могат да бъдат достъпени в посока от детето към Root (корена)
Leaf – Node, който няма деца
Node Degree – брой деца
Node Height – броят на връзките, започвайки от този Node по най-дългия път надолу до най-далечното листо
Node Depth – броят на връзките между този Node и Root на това дърво
Sub-Tree - поддърво
Node Level – започваме от Root (Level 1) като за всяко следващо ниво е +1
What is a Binary Tree?
Двоично дърво (Binary Tree) е структура от данни, в която всеки възел има най-много два дъщерни възела: ляво и дясно.
What is BFS? Why would we use it for?
BFS (Breadth-First Search) е алгоритъм за обхождане на граф или дърво, който изследва всички възли на дадено ниво преди да премине на следващото ниво. Използва се за намиране на най-краткия път в графи или за търсене в широчина при дървета. Изпълнява се с опашка.
What is the difference between PostOrder, PreOrder, and InOrder DFS traversal?
DFS (Depth-First Search) е алгоритъм за търсене в дълбочина, който обхожда граф или дърво, като започва от root-a и следва всяко разклонение, преди да се върне и да изследва друг път. Алгоритъмът използва стек или рекурсия за запаметяване на node-овете, които предстои да бъдат посетени.
- PreOrder (корен, ляво, дясно) - за копиране
- InOrder (ляво, корен, дясно) - за сортиране
- PostOrder (ляво, дясно, корен) - за изтриване
What is a Binary Search Tree?
Двоично търсещо дърво (Binary Search Tree - BST) е специален вид двоично дърво, в което всеки възел спазва следните правила:
- Лявото поддърво съдържа само възли с по-малки стойности от тази на корена.
- Дясното поддърво съдържа само възли с по-големи стойности от тази на корена.
- И двете поддървета също са двоични търсещи дървета.
Това позволява ефективно търсене, добавяне и изтриване на елементи за време O(log n), ако дървото е балансирано, в противен случай е O(n).
Балансирано дърво - разликата между височината на лявото и дясното дърво е 0 или 1. Сложността е O(log n) за всички операции.
What is Binary Heap? Which data structure in Java use Binary Heap for implementation?
- Complete Binary Tree – Завършено дърво (всички нива са запълнение с изключение на последното ниво. Новите елементи се добавят от ляво на дясно);
- Всеки един Node е по-добър(по-голям/ по-малък) от неговите наследници;
- Heap не е дърво за търсене;
- използва се за имплементиране на Priority Queue (сортирани в natural order или използваме Comparator)
Операции:
- search - O(n)
- insert - O(log n)
- delete - O(log n)
- get best - O(1) - Min Heap/Max Heap
What are TreeSet and TreeMap?
TreeSet
Дефиниция:
- Съхранява уникални елементи
- Не запазва реда на добавяне
- Сортира елементите в natural order или като използва Comparator
- Имплементация: Self-balancing binary search tree (Red/Black Tree)
TreeMap
Дефиниция:
- Сортират се по ключове
- Не може да има повтарящи се ключове
- Сортира елементите в natural order или като използва Comparator
- Имплементация: Self-balancing binary search tree (Red/Black Tree)
