磨刀不误砍柴工 系列之 一 : Heap BST AVL

September 22, 2013

学习算法是磨刀不误砍柴工的一件事情。

(磨刀不误砍柴工) 系列是我学习算法的笔记，总结自己学习中的理解，并希望能分享交流。

有一个好的算法基础不仅仅是写好程序的必要条件，同时联系算法也是一件乐事。没有大程序的繁琐，同时也有研究逻辑、数理的乐趣。
PS: 虽然看算法书有点枯燥，但是这是学习算法的必经之路。

这学期上Adv. Algorithms, 参考书有两本：

• Algorithm Design(Foundations, Analysis, and Intent Examples)</li>
• 算法导论(第3版)

第一篇 包括以下几个算法：Heap, Binary Search Tree, AVL

Heap

Previously, I thought Heap is built in O(nlogn) time.
But sometimes, it can also be constructed in O(n) time.

PriorityQueue is NOT necessarily a Heap. Heap is a good implementation of PriorityQueue.

Bottom-Up Heap Construction runs in O(n) time.

Here is the pseudo-code of this construction method, it’s a recursive algorithm.

Algorithm BottomUpHeap(\( S \)):
Input: A sequence \( S \) storing \( n = 2^h - 1 \) keys
Output: A heap \( T \) stroing the keys in \( S \).
if S is empty then
    return an empty heap (consisting of a single external node).
Remove the first key, \(k\), from \( S \).
Split \( S \) into two sequences, \(S_1\) and \(S_2\), each of size \((n-1)/2\).
\(T_1\) <– BottomUpHeap((S_1))
\(T_2\) <– BottomUpHeap((S_2))
Create binary tree \( T \) with root \( r \) storing \( k \), left subtree \(T_1\), and right subtree \(T_2\).
Perform a down-heap bubbling from the root \( r \) of \( T \), if necessary.
return \( T \)

BST

I have implemented the algorithm of a BST without the RemoveElement method before. And the RemoveElement is the most complicated among those common methods of BST.

Here is a good code example of BST. But where I found a bug in remove method. In Node with 2 children scenario, after we copied the data from the leftMost_node of right_subTree(we call it replace_node) to replace the deleted node, we should preserve the replace_node's right_subTree. This means, the replace_node should not be straightly deleted, we need to link its parent’s *left_child to its right_subTree beforehand.

void BinarySearchTree::remove(int d)
{
    ...
    //Node with 2 children
    // replace node with smallest value in right subtree
    if (curr->left != NULL && curr->right != NULL) {
    ...
        if((curr->right)->left != NULL) {
            ...
            while(lcurr->left != NULL)
            {
               lcurrp = lcurr;
               lcurr = lcurr->left;
            }
    curr->data = lcurr->data;
    lcurrp->left = lcurr->right;
            delete lcurr;
    //lcurrp->left = NULL;
        }
    ...
}

#16 is what I have fixed to replace #18.

BST VS. Heap

I was used to mix BST and Heap up. Now I know they are both elementary trees, but totally different.
BST is more well organized where every node satisfies left_subtree < node < right_subtree;
Heap does not necessarily so. What’s more, Heap is a complete tree.

eg: In a MinHeap, root is the minimum of the whole tree. An new node is inserted at the last position at first, then rejust its final position through Up-Heap Bubbling.

While in BST, a new node is compared from ROOT to its real position before it is inserted at the real position. And the real position of a new node must be a leaf.

AVL

A type of restructured BST to be balanced, named after the initials of its inventors: Adel’son-Vel’skii and Landis.

Height-Balance Property: For every internal node v of T, the heights of the children of v can differ by at most 1.

The height of an AVL tree storing n keys is O(lohn).

The insertion and removal operations for AVL trees are similar to those for binary search trees, but with AVL trees we must perform additional computations.

Insertion

An insertion in an AVL tree T begins as in an insertItem operation in BST.

While doing restructure on T, we maintaining the inorder relationships of all the nodes in T.

The modification of a tree T caused by a trinode restructure operation is ofen call a rotation, because of the geometric way we can visualize the way it changes T. (Ranger said: I have never figured out that this operation has any similarity as roatation visually. Just kidding.)

single roatation & double rotation

If b = y, the trinode restructure mothod is called a single rotation; Otherwise, if b = x, the trinode restructure operation is called a double rotation.

signle roation Right-Right signle roation Left-Left signle roation Right-Left signle roation Left-Right

• One rotation (single or double) is sufficient to restore the height-balance in an AVL tree after an insertion.

Removal

We also use trinode restructuring to restore balance in the tree T.

In particular, let \( w \) be the parent of the previously removed node. Let \( z \) be the first unbalanced node encoundtered going up from \( w \) toward the root of T. Also, let ye be the child of \( z \) with larger height (note that node \( y \) is the child of \( z \) that is not an ancestor of \( w \)), and let \( x \) be a child of \( y \) with larger height.

• A single trinode restructuring may not restore the height-balance property globally after a removal. O(logn) trinode restructurings are sufficient.

Running Times for AVL Trees

• a single restructure is \( O(1) \)
  using a linked-structure binary tree
• find is \( O(log n) \)
  height of tree is \( O(log n) \), no restructures needed
• insert is \( O(log n) \)
  initial find is \( O(log n) \)
  Restructuring up the tree, maintaining heights is \( O(log n) \)
• remove is \( O(log n) \)
  initial find is \( O(log n) \)
  Restructuring up the tree, maintaining heights is \( O(log n) \)

There are some points confused me in AVL:

• How does AVL detect the diff between height of left_child and right_right IN DETAIL?
• What’s the algorithm details of rotate operation? Will the 4-types rotation be very complicated?