CSCE 221 Chapter 9

« previous | Thursday, March 3, 2011 | next »

Search Trees

Binary Search Tree

Binary tree in which everything to the left of the root is less than the root, and everything to the right of the root is less than the root.

Leaves do not store items (elements stored in internal nodes)

Searching

Find k:

1. if root < k, look at left child (else look right child)
2. repeat previous step for each internal node

Insertion

Search for the element, and insert it where it should go

Insertion time depends on height of tree

• if balanced, $O(\log n)$
• if unbalanced, worst case would be $O(n)$

Deletion

Replace node scheduled for deletion with what would follow in an inorder traversal: the smallest node (farthest left) on the right subtree

AVL Trees

A binary search tree in which the height is always logarithmic:

for every internal node v, the height of the children's subtrees can differ from v's height by at most 1

Therefore search will always be logarithmic

Insertion

Insert as normal for a binary search tree. If insertion violates the AVL definition, we rotate the unbalanced subtree closest to the inserted node.

1. Walk up the tree updating the heights of the nodes as we go along.
2. As soon as we run into a problem on a node, include the two previously traversed nodes; these will be the three nodes that need to be rotated.
3. Rotate them using a single or double rotation.

Rotation

Ordered Dictionary Review

(See CSCE 221 Chapter 9#Ordered_Dictionary→)

Easy to find neighbors of an item:

Lookup Tables and Skip lists