List → Tree
Representation of Tree
Categories
Binary Search Tree(BST)
Definition
- BSTs are Trees with some property.
Runtime: log N
Method
search
insert
(A common rookie bad habit to avoid)
delete
- No child: delete it.
- One child: delete it, and link its child to its parent.
- Two child:
Find its precursor or successor in in-order.(The biggest one in left child tree (has no right child) or smallest one in right child tree (has no left child))
Red-Black Trees
Isometric with a 2-3 tree
Balanced Search Tree
Tree Rotation
B-Tree
Balanced and no require rotations.
M is the number of children a node could have and M-1 is the item cap.
(For M = 4, 2-3-4 Tree; For M = 3, 2-3 Tree)
A B-Tree of order n is a tree whose M = n.