Trees and their properties

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

Back to the table of contents
Alterna · Chapter 22 · page 22.1
Trees and their properties
BST, rounds, lots of rounds, BST designer.
Tree
The main characteristic is that there is exactly one path between any two vertices. The trees have BST (search), heap (priority), pile (heap sort) and file systems.
GEF
PIF
EGE No. 12.23
01
Binary Search Tree (BST)
In BST, for each node, all keys in the left support < less, in the right are larger. This allows you to find an element over O(h), where h is the height.
For a balanced BST h x log2N, search O(log N). For a degenerate (as a list) h = N, search o(N).
02
3 Rounds of Tree
🔼
Preorder
The root of the left
Used for copying/serializing wood.
↔
Inorder
Left root right
For BST, it's sorted order!
🔽
Postorder
Left ♪ Right root ♪
It is used to remove a tree (children first).
03
BST Designer
Enter the numbers - see BST and the rounds
🌳
BST Designer
Numbers (by decimal place)