# Search Trees Study Guide

### From charlesreid1

## Contents

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

**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

# Flags

Search TreesSeries on Data Structures
Binary Search Trees Trees/OOP
(Note that heaps are also value-sorting trees with minimums at the top. See Template:PriorityQueuesFlag and Priority Queues.)
· Template:SearchTreesFlagBase · e |