Trees and their properties

Содержание и основные понятия

Back to the table of contents
Alterna · Chapter 25 · page 25.1
Trees and their properties
The tree is a connected graph without cycles. It is built on BST, piles, file systems, organizational hierarchy.
Tree
The main characteristic is that there is exactly one way between any two vertices. The trees are at the core of BST, the pile, file systems, XML and DOM.
GEF
PIF
EGE No. 12
01
Main properties
V, E, root, height, depth
In a tree with
V
The tops are straight
E = V − 1
Rubber.
The root
The tree usually has one root, and the rest have descendants.
Height
- the length of the longest journey from the root to the leaf.
Top depth
- distance from the root to this summit.
List
- the top without offspring.
Host
- the top with at least one offspring.
02
Binary tree
Each knot has no more than two children
B
Binary tree
Each knot has no more than two children:
left
and
Right
.
Number of knots in a complete binary tree h:
N(h) = 2
h+1
− 1
Example: at h=3 ~ N = 24 - 1 = 15 knots.
BST Binary Search Tree
B
BST
For each node, the rule is fulfilled: all keys in the left support are smaller, in the right are larger. This allows the element to be found after O(h), where h is the height.
If the tree is balanced, h x log2N, and the search works for O(log N). If it is due (as a list), it is for O (N).
Plenty of it.
Lots.
is an almost complete binary tree where the value in each node is ≤ (min-cush) or ≥ (max-cuch) of its descendants, used in pyramidal sorting and priority.
BFS and DFS in trees
Width bypass (BFS)
- Visits all levels of lion L before lion L+1. Uses the line to search for the shortest path in a tree, a level-to-level seal.
Deep Entrance (DFS)
- We go as deep as possible one branch, then we go back. Three options: pre-order, in-order (left), post-order.
BFS (levels)
5 → 3, 7 → 1, 4, 6, 8
DFS Preorder
5, 3, 1, 4, 7, 6, 8
DFS Inorder
1, 3, 4, 5, 6, 7, 8
DFS Postorder
1, 4, 3, 6, 8, 7, 5
03
Rounds of wood
3 Classical Ways to Overtake A Binary Tree
Direct (preorder)
The root of the left
К, Л, П
Symmetrical (inorder)
Left root right
Л, К, П
Reverse (postorder)
Left ♪ Right root ♪
Л, П, К
Example: BST with keys 5, 3, 7, 1, 4, 6, 8
5
3
7
1
4
6
8
①
②
③
④
⑤
⑥
⑦
Predator:
①→②→③→④→⑤→⑥→⑦ →
5, 3, 1, 4, 7, 6, 8
Inorder (LCR):
③→②→④→①→⑥→⑤→⑦ →
1, 3, 4, 5, 6, 7, 8
Sorted!
Postorder (PCA):
③→④→②→⑥→⑦→⑤→① →
1, 4, 3, 6, 8, 7, 5
How to Read a Tree:
Left descendant < red < right descendant.
class BSTNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def bst_insert(root, key):
if root is None: return BSTNode(key)
if key < root.key: root.left = bst_insert(root.left, key)
else: root.right = bst_insert(root.right, key)
return root
def bst_search(root, key):
while root:
if key == root.key: return root
root = root.left if key < root.key else root.right
return None
def bst_inorder(root, res=[]):
if root:
bst_inorder(root.left, res)
res.append(root.key)
bst_inorder(root.right, res)
# Сборка дерева:
root = None
for k in [5, 3, 7, 1, 4, 6, 8]:
root = bst_insert(root, k)
seq = []; bst_inorder(root, seq)
print(seq) # [1, 3, 4, 5, 6, 7, 8]
🌲
BST: Paste and bypasses
🎯
Mini-test: 5 questions
XP: 0
🧩
Quick test on the subject
Five questions, 20 XP for every correct answer.