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

ADTs and Interfaces

Binary Search Tree

Binary search tree interface:

• get
• set
• insert
• remove
• node navigation methods:
  • first
  • last
  • before
  • after
  • parent
  • left/right

TreeMap:

• see map implementation
• inherits from map base class and binary tree class directly (multiple inheritance)

Balanced Search Tree:

• rotate(p) - rotate p and its parent
• restructure(p) - trinode restructuring

AVL Tree:

• Node:
  • int height
  • extends other node classes
• recompute height
• is balanced
• tall child
• tall grandchild
• rebalance

Splay Tree:

• splay
• extends TreeMap type
• utilizes rotation method

(2,4) Tree

• standard map/tree implementation
• Node:
  • Multiple entries per node
  • Use a hash table to keep track of nodes
  • Use a sorted array, b/c O(1) size means its cheap and you go with what is simple

Red Black Trees:

• Node:
  • boolean red black
  • get/set red
  • get/set black
• is leaf
• get red child
• rebalance inset
• resolve red
• rebalance delete
• fix deficit