Transcript Nov 11 - Joshua Stough

CSCI 62
Data Structures
Dr. Joshua Stough
November 11, 2008
Today
• Binary Search Trees
– Splay Trees
– Red-Black Trees
Binary Search Trees
• Binary Search Tree: binary tree that is
trivial or if every node > (every value in
left subtree) and <= (every value in right
subtree).
Binary Search Tree
• Ordered Structure
Binary Search Tree
• More methods
Binary Search Tree
• implementation
Binary Search Tree-locate
(easy idea), lot of code
BST- contains
BST
add
If value not found,
locate gives node to
add leaf to
containing value,
If locate finds
equivalent, insert
new value as right
child of predecessor
of node returned by
locate.
Predecessor-the
right-most child of
the left subtree
Found it, so insert as
predecessor.
Got to a leaf > newNode,
make newNode left child.
BST-remove top
BST-removeTop
BST-removeTop
• Disconnect top node.
• If no left or no right subtree, or no right
subtree of left, easy
• Otherwise
get
predec.
Make it
root
removeTop on this
Splay Tree
• BST worst case complexity O(height)
– If balanced, O(log n). No assurance though
• Splay Tree
– BST where tree can reconfigure itself using a
splay:
• Move node (to be added or removed) to top of
tree:
• Amortized performace O(log n)—like skew heaps
Splay
• Rotation: replace root with one of its
children
Splay
Do rotateLeft()
Splay at a particular node
Splay at a particular node
splay
• After splay(x), x is new root. Tree is not
necessarily more balanced.
• Splay tree: extends BST, but every op splays
on the node accessed or modified.
– Future accesses to x or children of x are faster
though, so amortized cost is O(log n) (under
certain assumptions of access).
• Sect 14.6 spends time on iterating through a
Splay tree (confusing since every access
changes the tree).
Red-Black Trees
• BST and Splay – bad performance if
evil insertion or access order.
• Red-Black – keeps tree balanced within
factor of 2.
– Nodes of a BST colored black,red
– Height is O(log n), max ~2*log(n)
Review