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, Implementations

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

Algorithms for Operations

Binary Search Tree

find min method:

• deal with empty case
• public method calls private method

find min subtree method:

• if has lef:
  • return find min(left)
• else:
  • return self

find max subtree method:

• if has right:
  • return find max(right)
• else:
  • return self

before(p) method:

after(p) method:

• 2 cases
• case 1: right != null
  • walk right once
  • walk left until left == null
  • return walk
• case 2: right == null
  • walk up once
  • walk up until parent == null or walk = left(parent)
  • return parent

search(k) method:

• deal with empty case
• call private method

search(p, subtree) method:

• if k equal p:
  • return p
• else if k < p and left(p) exists:
  • search(left, k)
• else if k > p and right(p) exists:
  • search(right, k)
• else:
  • unsuccessful search

insert(kv) method:

• p = search(k)
• if found:
  • update p value
• else if k < p:
  • add new item as p.left
• else:
  • add new item as p.right

delete(K) method:

• p = search(k)
• if not found:
  • return null
• if p has 0 children:
  • remove p
• if p has 1 child:
  • remove p
  • replace p with p's child
• if p has 2 children:
  • find before(p)
  • replace p with before(p) (node only, not the subtree)
  • remove before(p) from its ol position (it must hae o-01 children)

find range(k1, k2) method:

• deal with empty tree case
• p = search(k)
• while p not null:
  • p = after(p)
  • yield next key/value

find ge(k) method:

• deal with empty tree case
• p = search(k)
• return after(p)
• otherwise return null

get(k) method:

• deal with empty case
• p = search(k)
• rebalance tree
• return p

set(k,v) method:

• deal with empty case
• p = search(k)
• if found,
  • set new value
• else,
  • create new node
  • add to p (left or right)
• rebalance tree

delete(p) method:

• if 2 children:
  • replacement = last position in left subtree of p
  • replace p with replacement
  • p = replacement
• get parent of p
• delete p
• rebalance (parent)

delete(k) method:

• deal with empty case
• p = find(k)
• if p is our node (p==key):
  • delete p
  • return
• rebalnace

Balanced Search Tree

rotate(p) algorithm:

• x = p
• y = x.parent
• z = y.parent
• if z is none:
  • root = x
  • x.parent = none
• else:
  • relink(z, x, y equals z.left)
• if x equsl y.left:
  • relink(y, x.right, true)
  • relink(x, y, false)
• else:
  • relink(,y x.left, false)
  • relink(x, y, true)

restructure(p):

• x = p
• y = x.parent
• z = y.parent
• if ( (x equals y.right) equals ( y equals z.right) )
  • rotate(y)
  • return y
• else:
  • rotate x
  • rotate x
  • return x

relink(parent, child, make left) method:

• if make left:
  • parent.left = child
• else:
  • parent.right = child
• if child is not none:
  • child.parent = parent

AVL Tree

recompute height(p) method:

• height = 1 + max( height(left), height(right))

is balanced(p) method:

• return abs(p.left.height - p.right.height) <= 1

tall child(p) method:

• if node.left.height > node.right.height:
  • return p.left
• else:
  • return p.right

tall grandchild(p) method:

• child = tall child(p)
• favor left grandchild if child on left
• favor right grandchild if child on right
• return tall child(child)

rebalance(p) method:

• while p not none:
  • save old height
  • if p is not balanced:
    • p = restructure(tall grandchild(p))
    • recompute height(p.left)
    • recompute height(p.right)
  • recompute height(p)
  • if new height equals old height:
    • p = none / done
  • else:
    • p = p.parent / repeat with parent

Splay Tree

rebalance(p) method:

• splay(p)

splay(p) method:

• while p is not root:
  • p = p.parent
  • grandp = parent.parent
  • if grandp is none:
    • zig case:
    • rotate(p)
  • else if ( (parent equals grandp.left) equals (p equals parent.left) ):
    • zig zig case:
    • rotate(parent)
    • rotate(p)
  • else:
    • zig zag case
    • rotate(p)
    • rotate(p)

(2,4) Tree

insert(k,v) method:

• z = search(p)
• w = parent9z)
• if found:
  • update z
• else:
  • insert(k,v,w)
  • if overflow(w):
    • split(w)

delete(w) method:

• z = saerch(p)
• if not found:
  • return none
• if z is internal node, swap (ki, vi) with node w whose children are all external
• to find w:
  • find right-most internal node w in the subtree rooted at the ith child of z
  • swap item (ki, vi) of z with last item of w
• remove (ki, vi) from w
• remove ith external node from w
• fusion or transfer(w)

fusion or transfer(w):

• if sibling of w is 3-node or 4-node:
  • transfer child of s into w
  • transfer key of s into u (parent of w and s)
  • transfer key of u into w
• if 1 sibling or if 2-node siblings:
  • fusion(w) case
  • merge w with new sibling
  • make new node w'
  • move a key from u (parent) to w'
• if underflow(w):
  • fusion or transfer(u)