ADT Dictionary
Operations Insert, Delete, Search
Cristyn Howard
Monday, January 22, 2018
Data Structure
BST
Balanced Trees { 2-3 trees, B-trees, red-black trees, AVL trees }
Problems with BSTs…
CSC263 – Week 3, Lecture 1
suppose we start with…
(2) (1) (3)
and add 4, 5, 6…
(2) (1) (3)
(4)
(5)
(6)
Unbalanced trees such as the one above results in height ∈ Θ(n), ops ∈ Θ(n). Today we will explore a new
data structure, balanced trees. First, some definitions.
• Height(v): # of edges on the longest path from node v to a leaf
• BalanceFactor(v): Height(v.rightSubTree) − Height(v.leftSubTree)
AVL
1