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)

Complexity and Cost

Big O Complexity Table

Big-O Complexity of Lists
	General/Unbalanced Binary Search Tree	Balanced Binary Search Tree	AVL Tree
search	O(h)	O(log N)	O(log N)
insert	O(h)	O(log N)	O(log N)
remove	O(h)	O(log N)	O(log N)
find range	O(h + S)	O(log N + S)	O(log N + S)
rotation	-	O(1)	O(1)
restructure	-	O(1)	O(1)
find lt/gt	-	O(log N)	O(log N)
iterate	O(N)	O(N)	O(N)

Splay Trees

Big-O Complexity of Lists
	Splay Tree
height	O(d) (zigs and zags) O(h) ~ O(N) (worst case) O(log N) amortized

OOP Principles

Search trees are rife with applications of object-oriented programming. These are a great place to focus for object-oriented examples.

More delegation of roles:

• Who performs comparisons?
• Who gets left child and how?
• Who gets ancestors?
• Know, before you start, how these questions will be resolved.
• The answer to these questions will rapidly propagate throughout your solution

Separation of position and node:

• Position object points to tree and points to node
• Node holds data, position does not
• Tree has a validate method to turn positions into nodes
• Why use this mode?
  • allows for validation - is this position actually in our tree?
  • protects data/node while also allowing users a way to point to locations and have O(1) accesss
• Why not?
  • confusing, abstract, a bit wishy-washy
  • Extra level of cognitive burden - how to convert position to node? do I return a node? what if protected? position? value?

Multiple inheritance:

• inherit from abstract map or abstract data type interfaces to implement a tree map
• inherit from linked binary tree to implement a tree map as a tree directly
• This is why it is important, even early on, to decide your abstraction and inheritance diagram

Hooks:

• pseudo-virtual methods useful for different purposes

Inheritance diagram:

• AVL, Splay, RedBlack trees inherit from TreeMap
• TreeMap inherits from Abstract Map and Linked Bin Map

Tree Node factory:

• Subtlety in design of LinkedBinTree and TreeMap classes:
• Node class is defined in parent class
• However, a balanced search tree requires storing additional info (AVL - height, redblack - color)
• The classes all use the BASE Node class in the parent implementation
• This is not linked to the specific parent class's implementation of the node - rather, we utilize polymorphism and maintain parent type pointer (ore general) so that it can still refer to the child type (Node carrying more information)
• Polymorphism in action