Transcript Notes on Weiss, Chapter 4

EECS 311: Chapter 4 Notes
Chris Riesbeck
EECS Northwestern
 Unless otherwise noted, all tables,
graphs and code from Mark Allen
Weiss' Data Structures and Algorithm
Analysis in C++, 3rd ed, copyright ©
2006 by Pearson Education, Inc.
Binary Search Trees
Binary
Search
Tree
Not a
Binary
Search
Tree
BST with = left/right depths
AVL Trees
AVL Tree
Not AVL
Tree
Right Rotation
Parent pointer to
k2…
changed to point
to k1
becomes left
subtree
Right subtree
of of k2
k1…
Rotate right when
left left subtree
too deep
Left Rotation
Rotate left when
right right subtree
too deep
Left-Right Rotation
When right
subtree of left
subtree too deep
…then rotate k2
right through k3
Rotate k2 left
through k1 first…
Red-Black Trees
 AVL-style rotations to balance
 No numbers, just one red-black bit
per node (or link)
 Use rotations and recoloring to
guarantee:
 Never two red nodes in a row
 All leaves same depth counting black
nodes
Rotations in Red-Black Trees
Recoloring in Red-Black Trees
Splay Tree





Balance on access, not insertion
Use AVL-style rotations
Move item just accessed to the root
Typically makes tree shallower
Complexity
 Can be O(N) worst case single access
 O(M log N) on for M accesses
 Amortized O(log N)
 No bookkeeping data needed
Zig-zag Rotation
Zig-zig Rotation
B-Trees




No rotations
N-way tree (N subtrees, N-1 keys)
Keys sorted in each node
When passing through a full node:
 Make a new node
 Move the keys and pointers on the right to the
new node
 Move middle key and the pointer to the new
node to parent node
 Note: parent can't be full. Why?
Adding and splitting
now add 57
After adding 55
now add 55
After adding 57
now add 40
After adding 40