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 $

balanced AVL tree - height difference is maximum of 1

unbalanced AVL tree - height difference is larger than 1

splay - moving a node x to the root via a restructuring sequence (zig-zig, zig-zag, and zig); each move shifts the node closer to the root

multiway search tree - search tree in which internal nodes have more than 2 children

d-node - a tree node with d children

secondary data structure - a data structure that serves in support of another, primary data structure; for example, d-nodes have maps

bootstrapping - use of a simpler solution to create a more advanced solution (O(n) map is OK, if 1-10 items max)

(2,4) tree - tree in which every internal node has at most 4 children

red-black tree - search tree in which nodes are colored red or black to maintain balance