Search Trees Study Guide

Definitions and Variations

Definitions

binary search trees - binary tree data structure, guarantes keys in left subtree < k, keys in right subtree > k

in order traversal - visiting each node of a BST in sorted order

• traverse left subtree, visit action, traverse right subtree.
• sorted iteration of keys can be made in O(n) time.

binary search - search algorithm in which successive halves of the array of data are chosen; utilizes comparison and equals info

rebalancing - as nodes are added and removed, left and right nodes can become imbalanced, affecting search speed - O(log N) becomes O(N)

rotation - principal operation of rebalancing, rotates a child above its parent

trinode restructuring - restructure connection from grandparent node to grandchild node to shorten path between them

splay tree - binary tree structure in which most frequently used/accessed items are kept near the root

factory method pattern - subclass controls behavior details, implementation handled in parent class

AVL (Adelson-Velski-Landis) tree - self-balancing binary tree that ensures the height is O(log N) by guaranteeing the following:

$ | \mbox{left tree height} - \mbox{right tree height} | \leq 1 $