View source for 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

[[Image:SearchTree_Rotation.jpg|500px]]

[[Image:SearchTree_TrinodeRestructuring.jpg|500px]]

'''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:

<math>
| \mbox{left tree height} - \mbox{right tree height} | \leq 1
</math>

'''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==

{| class="wikitable" cellpadding="100" width="66%"
!colspan="4"|Big-O Complexity of Lists
|-
|
|<br /><br />
General/Unbalanced
Binary Search Tree
|<br /><br />
Balanced 
Binary Search Tree
|<br /><br />
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==

{| class="wikitable" cellpadding="100" width="33%"
!colspan="4"|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

=Flags=

{{StudyGuideFlag}}
[[Category:Study Guide]]

{{SearchTreesFlag}}
[[Category:Binary Trees]]
[[Category:Binary Search Trees]]