Balanced Binary Search Tree

It is the depth of the binary search that affects the performance of it. We say that a binary search tree with $n$ nodes is balanced if its depth is of order $O(\log n)$ (hence we can perform find, insert and delete operations in time $O(\log n)$ ).

If a tree is unbalanced, we can maintain the balance by rotation. Further, we need some criteria to guide the rotation. In what's follows we discuss some of the popular design of the criteria.

By the number of elements of the subtree.

Denote a note $v$ and its left and right child $v.left$ and $v.right$ respectively. Define the size of $v$ ( $s(v)$ ) the number of elements contained in the subtree rooted at $v$ .

A critical observation is that, if for each node $v$ of the tree, the size of each of it subtrees is at most a constant fraction $\big($ denoted as $\epsilon \in (\frac{1}{2}, 1)$ ; Exercise: why can't we pick $\epsilon \in [0, \frac{1}{2}] \big)$ of its size, i.e.,

s(v.left) \le \epsilon s(v) \\ s(v.right) \le \epsilon s(v)

then the depth of the tree is in the order of $O(\log n)$ . The reason is obvious: let $r = v_0, v_1, v_2, ..., v_k$ be any root-to-leaf path of the tree, then

s(v_1) \le \epsilon s(v_0) \\ s(v_2) \le \epsilon s(v_1) \\ ...\\ s(v_k) \le \epsilon s(v_{k - 1})

it follows that $1 = s(v_k) \le \epsilon^k s(v_0) = \epsilon^k n$ and $k \le \log_\epsilon \frac{1}{n} = O(\log n)$ .

Therefore, we can pick arbitrary $\epsilon \in (\frac{1}{2}, 1)$ and maintain this criteria explicitly and recursively.

WLOG, suppose a new element is inserted into the left subtree of a vertex $v$ . Denote the new size function $s$ as $s'$ after insertion. If after insertion, $s'(v.left) \le \epsilon s'(v)$ , we do nothing and check the balance of $v$ 's parent (if there is any). Otherwise, we may try a right rotation on $v$ :

\begin{aligned} &\qquad \qquad v \\ &/ &\setminus \\ &v.left &&v.right \\ / &\setminus \\ v.left.left & \quad v.left.right \end{aligned}

the subtree transform into:

\begin{aligned} &\qquad \qquad v.left \\ &/ &\setminus \\ v.left.left && v\\ &&/ &\setminus \\ && v.left.right & \quad v.right \end{aligned}

Since before insertion, $s(v.left) \le \epsilon s(v)$ , it holds that $s'(v.left.left) \le \epsilon s'(v.left) = \epsilon (s(v) + 1)$ . Therefore, the left subtree no longer violate the balance constraint. However, the constraint could be violated by the right subtree. Since it is possible that

s'(v.left.right) + s'(v.right) + 1 > \epsilon s'(v.left) = \epsilon (s(v) + 1)

For example, suppose that $\epsilon = 0.8$ and $s(v.left.right) = 0.8 s(v.left) = 0.64 s(v)$ and $s(v.right) = 0.2 s(v) - 1$ , then

s(v.left.right) + s(v.right) + 1 = 0.84 s(v)

The reason is that there is so much weight that $v.left.right$ has. Therefore, we don't want to rotate it to the right subtree. An alternative is to perform a left rotate on the left subtree first

\begin{aligned} &\qquad \qquad v \\ &/ &\setminus \\ &v.left.right &&v.right \\ / &\setminus \\ v.left & \quad v.left.right.right \\ / \setminus & \\ v.left.left & \quad v.left.right.left \end{aligned}

Followed by a right rotation on $v$ :

\begin{aligned} &\qquad \qquad v.left.right \\ &/ &\setminus \\ &v.left &&v \\ / &\setminus &&/ \setminus\\ v.left.left &\quad v.left.right.left& \quad v.left.right.right &\quad v.right\\ \end{aligned}

To satisfy the balance requirement, we require that

$s''(v.left.right.left) = s'(v.left.right.left) \le \epsilon s''(v.left) = \epsilon (s'(v.left) - s'(v.left.right.right) -1 )$ .
$s'(v.left.left) \le s'(v.left)$
$s'(v.left.right.right) + s'(v.right) + 1 \le \epsilon s'(v.left.right)$

Condition 1 implies that $s'(v.left.right.right)$ can take up too much weight of $s'(v.left)$ , which imposes an upper bound on $\epsilon$ by

(1 - \epsilon) \epsilon s'(v.left) - 1 \le \epsilon (s'(v.left) - \epsilon^2s'(v.left) - 1)

By the number of elements of the subtree.

By the height of the subtree (AVL Tree)