DS C1 Trees01

Preliminaries

Definition

Recursive def of a tree:

A tree is a collection of $N(N \geq 0)$ nodes and edges. The collection could be empty; otherwise the tree consists of a distinguished node $r$ called root, and more than $0$ nonempty (sub)trees $T_1, T_2, \cdots,T_k$, each of whose roots are connected from $r$ by a directed edge.

• parents/children: $A$ is the parent of $B$ and $B$ is a child of $A$ if there’s an edge from $A$ to $B$.
• siblings: $A$ and $B$ are siblings if their roots are same.
• leaves: Node that has no children.
• path (from $n_1$ to $n_k$) and length: path is defined as a sequence of $n_1,n_2,\cdots,n_k$ such that $n_i$ is parent of $n_{i+1}$ for $1 \leq i\leq k$. The length of the path is $k-1$.
• depth/height (of $n_i$): $dep(n_i) = len(path(root,n_i)), \quad height(n_i) = \max_{l \in leaves}len(path(n_i,l))$
• depth/height (of tree $T$): $dep(T) = \max_{l \in leaves}dep(l) = height(T) = height(root))$
• ancestors/descendant : $A$ is a ancestor of $B$ and $B$ is a descendant of $A$ if there’s a path from $A$ to $B$.

NOTE The height of an empty tree is defined -1 usually.

Propositions

1. A tree of $N$ nodes has $N - 1$ edges.
2. There’s exactly $1$ path from root to each node.

Implementations

typedef struct _TreeNode* PtrToNode;
typedef struct _TreeNode{
    ElementType Element;
    PtrToNode FirstChild;
    PtrToNode NextSib;
}TreeNode;

Traversals

All traversals’ time complexity is $O(N)$.

Preorder

Algorithm Preorder(PtrToNode T){
	Visit(T);
	Next := T -> FirstChild;
    While(Next){
    	Vist(Next);
		Next = Next -> NextSib;
	}
}

Postorder

Algorithm Postorder(PtrToNode T){
	Next := T -> FirstChild;
    While(Next){
    	Vist(Next);
		Next = Next -> NextSib;
	}
	Visit(T);
}

Binary Trees

typedef struct _BTreeNode* PtrToNode;
typedef struct _BTreeNode{
    ElementType Element;
    PtrToNode Left;
    PtrToNode Right;
}BTreeNode;

Propositions

Inorder

Algorithm Inorder(PtrToNode T){
	Visit(T -> Left);
	Visit(T);
	Visit(T -> Right);
}

Examples :Expression Tree

The leaves of an expression tree are operands, and the other nodes contain operators.

• infix: traverse the tree in inoder.
• prefix: traverse the tree in preorder.
• post: traverse the tree in postorder.

Binary Search Tree

Properties

$$\max_{n_i \in lsubtree} val(n_i) \leq val(root) \leq \min_{n_i \in rsubtree} val(n_i)$$

The inorder traversal of BST is ascending.

Operations

• Make empty

  SearchTree MakeEmpty(SearchTree T){
  	if(T != null){
  		MakeEmpty(T -> Left);
  		MakeEmpty(T -> Right);
  		free(T);
  	}
  	return Null;
  }

• Find/FindMin/FindMax

  Position Find(ElementType X, SearchTree T){
  	if(T == null)
  		return null;
  	if(X < T -> Element)
  		return Find(X,T -> Left);
  	else if(X > T -> Element)
  		return Find(X,T -> Right);
  	else
  		return T;
  }
  Position FindMin(SearchTree T){ //leftmost
  	if(T == null)
  		return null;
  	if(T -> Left)
  		return FindMin(T -> Left);
      else 
          return T;
  }
  Position FindMax(SearchTree T){//rightmost
  	if(T == null)
  		return null;
  	if(T -> Right)
  		return FindMax(T -> Right);
      else 
          return T;
  }

• Insert

  SearchTree Insert(ElementType X,SearchTree T){
  	if(T == null){
  		T = malloc(sizeof(struct TreeNode));
  		if(T == null) FatalError("OOS!")
  		else{
  			T -> Element = X;
  			T -> Left = T -> Right = null;
  		}
  	}
  	else if(X < T -> Element)
  		T -> Left = Insert(X,T -> Left);
  	else if(X > T -> Element)
  		T -> Right = Insert(X,T -> Right);
  	return T;
  }

• Delete

  SearchTree Delete(ElementType X,SearchTree T){
  	Position TempCell;
  	if(T == null){
  		Error("Element not found");
  	}
  	else if(X < T -> Element)
  		T -> Left = Delete(X,T -> Left);
  	else if(X > T -> Element)
  		T -> Right = Delete(X,T -> Right);
  	else if(T -> Left && T -> Right){
  		TempCell = FindMin(T -> Right);
  		T -> Element = TempCell -> Element;
  		T -> Right = Delete(TempCell -> Element,T -> Right);
  	}
  	else{
  		TempCell = T;
  		if(T -> Left == null)
  			T = T -> Right;
  		else
  			T = T -> Left;
  		free(TempCell);
  	}
  	return T;
  }

Average-Case Analysis

AVL Tree

AVL tree is a BST with a balance condition.

height balanced

1. An empty binary tree is height balanced.
2. If T is a nonempty binary tree with $T_L$ and $T_R$ as its left and right subtrees(could be empty), then T is height balanced iff
   • $T_L$ and $T_R$ are height balanced, and
   • $|h_L - h_R| \leq 1$, where $h_L$ and $h_R$ are the heights of $T_L$ and $T_R$.

The balance factor (BF)

$$BF(node) = h_L - h_R$$

In an AVL tree, $BF(node) \in \{-1,0,1\}$.

Insertion and rotation

After an insertion, the nodes on the path from the insertion to the root may have their balance altered.

Hence after an insertion,

1. follow the path up to the root and keep updating the balancing info until we met the first unbalanced node $\alpha$, i.e $BF(node) \in \mathbb{Z} - \{-1,0,1\}$.

2. Address and fix the violation for different cases.

   BF	Child	Child’s Subtree	Solution	Note
   2	Left	Left	single rotation	LL
   2	Left	Right	double rotation	LR
   -2	Right	Left	double rotation	RL
   -2	Right	Right	single rotation	RR

3. Repeat 1 - 2 until we gets to root.

Tree rotation: an operation on a binary tree that changes the structure without interfering with the order of the elements whose time complexity is $O(1)$.

NOTEAfter a rotation, the side of the rotation increases its height by 1 while the side opposite the rotation decreases its height by 1 similarly.

• LL Rotation: single right rotation is enough and no more need to rotate.

  

• RR Rotation: single left rotation is enough and no more need to rotate.

  

• LR Rotation: take $k_3$ as the new root of the whole subtree by a left rotation and then a right rotation. This may cause new unbanlance.

  

• RL Rotation: take $k_3$ as the new root of the whole subtree by a right rotation and then a left rotation. This may cause new unbanlance.

  

height estimation

Let $n_h$ be the minimum number of nodes in a height balanced tree of height h. Then the tree must look like

$$n_h = n_{h - 1} + n_{h - 2} + 1$$

with initial conditions $F_0 = 1,F_1 = 2$.

$$n_h= Fib_{h+2} - 1 \approx \frac{1}{\sqrt{5}}(\frac{1 + \sqrt{5}}{2})^{h+2} - 1$$

Hence

$$h = O(\log n)$$

$$T(N) = O(h) = O(\log N)$$

Splay Tree

A splay tree is to control the time Any M consecutive tree operations starting from an empty tree taken at most $O(M\log N)$ time.

Although this guarantee does not preclude the possibility that any single operation might take $O(N)$ time.
But there are no bad input sequences.

Generally, when a sequence of $M$ operations has total worst-case running time of $O(MF(N))$, we say that the amortized running time is $O(F(N))$.

Rotations

We will still rotate bottom up along the access path.
Let $X$ be a nonroot node on the access path at which we are rotating.

1. The parent of $X$ is the root of the tree: merely rotate $X$ and the root $P$.
   
2. $X$ has both a parent ($P$) and a grandparent ($G$):
   • zig-zag case: $X$ is a right child and $P$ is a left child (or vice versa). Exactly same as LR rotation or RL rotation of AVL tree.
     
   • zig-zig case: $X$ and $P$ are either both left children or both right children. take $X$ as the new root of the whole subtree by a rotation between $P$ and $G$ and then a rotation between $X$ and $P$.
     

Splaying not only moves the accessed node to the root, but also roughly halves the depth of most nodes on the path.

Amortized Analysis

ref Introduction to Algorithms, P451-462.

In an amortized analysis, we average the time required to perform a sequence of data-structure operations over all the operations performed.

• Amortized analysis differs from average-case analysis in that probability is not involved;
• amortized analysis guarantees the average performance of each operation in the worst case.

NOTE The amortized cost applies to each operation, even when there are several types of operations in the sequence.

Aggregate analysis

For all $n$, a sequence of $n$ operations takes worst-case time $T(n)$in total. The amortized cost per operation is $\frac{T(n)}{n}$.

Exp: MultiStack

1. PUSH(S, x) pushes object x onto stack S.
2. POP(S) pops the top of stack S and returns the popped object.
   err Calling POP on an empty stack.
3. MULTIPOP(S, k) removes the k top objects of stack S.
   note popping the entire stack if the stack contains fewer than k objects; leaving the stack unchanged if k is not positive.

Then analyze a sequence of n PUSH,POP,and MULTIPOP operations on an initially empty stack. It’s easy to know that the worst case $O(N)$ of MULTIPOP won’t exist continuously.

We can pop each object from the stack at most once for each time we have pushed it onto the stack. Therefore, the number of times that POP(including calls within MULTIPOP) can be called on a nonempty stack is at most the number of PUSH operations. Hence

$$T(n) = 2n = O(n)$$

$$\frac{T(n)}{n} = O(1)$$

Exp: Incrementing a binary counter

A binary number x that is stored in the counter has its lowest-order bit in A[0] and its highest-order bit in A[k - 1].

INCREMENT(A) adds 1 (modulo 2k) to the value in the counter.

i = 0;
while i < A.length and A[i] == 1
	A[i] = 0;
	i = i + 1;
if i < A.length
	A[i] = 1;

In the worst case in which array A contains all 1s, a single execution of INCREMENT takes time $\Theta(k)$ . On an initially zero counter, $A[i]$ flips $\lfloor\frac{n}{2^i}\rfloor$ times in a sequence of n INCREMENT operations.

$$T(n) = \sum_{i = 0}^{k -1}\lfloor\frac{n}{2^i}\rfloor < n\sum_{i = 0}^{\inf}\frac{1}{2^i} = 2n = O(n)$$

$$\frac{T(n)}{n} = O(1)$$

Accounting method

Assign differing charges to different operations with some operations charged more or less than they actually cost.

amortized cost $\hat{c_i}$: the amount we charge the operation.

credit $credit_i$: the difference to specific objects in the data structure.

NOTECredit can help pay for later operations whose amortized cost$\hat c_i$ is less than their actual cost$c_i$.

NOTE All operations have the same amortized cost in aggregate analysis, while they may differ from each other in accounting method.

And we require

$$\sum_{i = 1}^{b}\hat{c_i} \ge \sum_{i = 0}^{n}{c_i}$$

for all sequences of n operations. i.e

$$\sum_{i = 1}^{n}credit_i = \sum_{i = 1}^{n}\hat{c_i}-\sum_{i = 0}^{n}{c_i}\ge 0$$

The total credit associated with the data structure must be nonnegative at all times. Or the total amortized cost would not be an upper bound on the total actual cost!

Exp: MultiStack

Op	$c_i$	$\hat{c_i}$(designed)	$credit_i$
PUSH	1	2	1
POP	1	0	-1
MULTIPOP	k	0	-k

$$\sum_{i = 1}^{n}credit_i = \sum_{i = 1}^{n}\hat{c_i}-\sum_{i = 0}^{n}{c_i}\ge 0$$

The sum of the credit equals the number of objects in the stack, which is nonnegative. Hence

$$T_{Amortized}(n) = O(1)$$

Exp: Incrementing a binary counter

Charge an amortized cost of 2 to set a bit to 1, 1 to pay for the actual setting of the bit, and another to be used later when the bit is flipped back to 0.

And charge nothing to reset a bit to 0.

$$\sum_{i = 1}^{n}credit_i = \sum_{i = 1}^{n}\hat{c_i}-\sum_{i = 0}^{n}{c_i}\ge 0$$

The sum of the credit equals the number of 1s in the counter, which is nonnegative.

$$T_{Amortized}(n) = O(1)$$

Potential method

Perform n operations starting with an initial data structure $D_0$. For each $i = 1, 2,\cdots n$:

• $c_i$: actual cost of the $i^{th}$ operation

• $D_i$: the data structure that results after applying the $i^{th}$ operation to data structure $D_{i-1}$

• $\Phi$ : a potential function maps each $D_i$ to a real number $\Phi(D_i)$, which is the potential associated with $D_i$.

  $$\hat{c_i} = c_i + credit_i = c_i + \Phi(D_i) - \Phi(D_{i - 1})$$

• $\hat{c_i}$ : the amortized cost of the $i^{th}$ operation.

The amortized cost is

$$\begin{align} \sum_{i = 1}^{n}\hat{c_i} &= \sum_{i = 0}^{n}(c_i + \Phi(D_i) - \Phi(D_{i - 1}))\\ &= \sum_{i = 0}^{n}c_i + \Phi(D_n) - \Phi(D_0) \ge \sum_{i = 0}^{n}c_i \end{align}$$

Hence the only requirements for potential method is

$$\Phi(D_n) - \Phi(D_0) \ge 0$$

for all sequences of n operations.

A good potential function should always assume its minimum at the start of the sequence.

Exp: MultiStack

Define the potential function $\Phi$ on a stack to be the number of objects in the stack.

$$\Phi(D_0) = 0$$

$$\Phi(D_n) = size(S)$$

Hence,

Op	$c_i$	$\Phi(D_i) - \Phi(D_{i - 1})$	$\hat{c_i}$
PUSH	1	1	2
POP	1	-1	0
MULTIPOP	k	-k	0

Exp: Incrementing a binary counter

Define the potential function $\Phi$ on a stack to be the number of 1s in the counter.

$$\Phi(D_0) = 0$$

$$\Phi(D_n) = numof1(A)$$

Hence, assume $m_i$ 1s are set to 0 in a single execution,

Op	$c_i$	$\Phi(D_i) - \Phi(D_{i - 1})$	$\hat{c_i}$
INCREMENT	1 + $m_i$	1 - $m_i$	2

Exp: Splay Tree

The potential function:

functions	NOTEs
$\Phi(D_i) = \sum_{i \in D_i}{height(i)}$	Almost every node’s height changes after a rotation!
$\Phi(D_i) = \sum_{i \in D_i}size(i)$	The difference is too large, causing a loose bound!
$\Phi(D_i) = \sum_{i \in D_i}\log size(i) = \sum_{i \in D_i}Rank(i)$	Great !

lemma If $a + b ≤ c, a,b,c \in \mathbb{Z}+$, then

$$\log a + \log b \le 2\log c - 2$$

PF:

$$\begin{align} \sqrt{ab} &\le \frac{a + b}{2} \le \frac{c}{2} \\ ab &\le \frac{c^2}{4}\\ \log a + \log b &\le 2\log c - 2\log 2 = 2\log c - 2 \end{align}$$

For Zig:

$$\begin{align} \hat{c_i} &= 1 + R_2(X) - R1(X) + R_2(P) - R_1(P)\\ &= 1 + R_2(P) - R_1(X)\\ &\le1 + R_2(X) - R_1(X) \end{align}$$

For Zig-zag:

$$\begin{align} \hat{c_i} &= 2 + R_2(X) - R1(X) + R_2(P) - R_1(P) + R_2(G) - R_1(G)\\ &= 2 - R_1(X) - R_1(P) + (R_2(G)+ R_2(P))\\ &\le 2 - R_1(X) - R_1(P) + 2R_2(X) - 2\\ &\le 2R_2(X) - 2R_1(X) \end{align}$$

For Zig-zig:

$$\begin{align} \hat{c_i} &= 2 + R_2(X) - R1(X) + R_2(P) - R1(P) + R_2(G) - R_1(G)\\ &= 2 - 2R_1(X)+( R_1(X) + R_2(G) )- R1(P)+ R_2(P)\\ &\le 2 - 2R1(X) + 2R2(X) - 2 - R1(P)+ R_2(P)\\ &\le 3R_2(X) - 3R_1(X) \end{align}$$

Hence the amortized time of the insertion of k rotations is

$$\sum_{i = 1}^{k}\hat{c_i} \le 3( R( T ) – R ( X ) ) + 1 \le 3(\log N - \log 1) + 1 = 3\log N + 1 = O(\log N).$$

The rotation of zig happens once at most .