2-3 Trees 1
Balanced Trees - 2-3 Tree
2-3 Trees 2
Balanced Trees
Binary search trees are not guaranteed
to be balanced given random inserts
and deletes
! Tree could degrade to O(n) operations
Balanced search trees
! Operations maintain a balanced tree
2-3 Trees 3
2-3 Tree
Guaranteed to always be balanced
! O(lg n) operations
Each interior node has two or three
children
! Nodes with 2 children are called 2 nodes
! Nodes with 3 children are called 3 nodes
! NOT A BINARY TREE
Data is stored in both internal nodes
and leaves
2-3 Trees 4
2 Node
S
Search keys < S
Search keys >= S
2 nodes have one data item and 2
children