Lesson 12 Skip List, Binary Search Tree, AVL Tree

Skip List

Hashing: extend array to map
Use linked list to map:

• unordered: fast insertion, slow search
• ordered: slow insertion, slow search

Reason: sequential

How to speed up?
mimic: quick/ slow train
turn sequential search to binary search(ordered)

Skip List to fast search

• 1. find the end of the ordered linked liststore end and mid
• 1. compare with the mid, define the new mid
• 1. Compare in the quicker list

Skip List: linked list (ordered)

• “faster” linked list
  
• “faster faster” linked list
  
• ….
  
• list of quard
  
• list of mid
  space: need double space

Skip List to fast insertion

Skip List:

Question: How to insert “6” into each list of the skip list?
#card=math&code=O%28n%29) if update all ypper linked list
When update, randomize 1/2 to the upper linked list, removal also.

Binary Search Tree

From Skip List to Tree:

Search smaller for left, bigger for right

BST-Search Algorithm:

BST_Search(k,T){
    mid <- root of T
    if (k<mid)
        return BST-Search(k,T->left)
    if(k>mid)
        return BST-Search(k,T->right)
    else (k = mid)
        return mid.value
}

• time complexity:
  O(h) for search, #card=math&code=O%28log%20n%29) for best, #card=math&code=O%28n%29) for worst

Relation between types of tree

• strict binary tree complexity analysis
  
  need much more effort to move the node to the right position

AVL Tree

brief for Adelson, Velskii, Landis (1962)
Definition
A BST such that %20-%20height(TR)%20%5Cright%20%7C%20%5Cleq%201#card=math&code=%5Cleft%20%7C%20height%28T_L%29%20-%20height%28T_R%29%20%5Cright%20%7C%20%5Cleq%201) for every sub-tree

Another definition:
%3Dh%7BL%7D-h%7BR%7D%5Cleft%5C%7B%5Cbegin%7Barray%7D%7Bl%7D1%20%5C%5C%200%20%5C%5C%20%5Ctext%20%7B%20-1%20%7D%5Cend%7Barray%7D%5Cright.#card=math&code=%5Coperatorname%7BBF%7D%28T%29%3Dh%7BL%7D-h_%7BR%7D%5Cleft%5C%7B%5Cbegin%7Barray%7D%7Bl%7D1%20%5C%5C%200%20%5C%5C%20%5Ctext%20%7B%20-1%20%7D%5Cend%7Barray%7D%5Cright.)
BL: Balance factor

Example of AVL Tree

• Simple version of maintaining
  
• More general example

1. B is balanced
   
2. After an insertion to
   
   This is a complex version of the former.
   A is not balanced now, because a “-2” height gap
3. Like the simple version, try to drag “B” to maintain the AVL Tree
   Firstly,choose B as the root, balance and
   
4. Secondly, move to the right sub-tree of A
   
   In this transformation, the only changed links are the purple one in the graph:
   
   A->right B->left
   B->left A
   A, B(RR rotation)
5. Similarly, an insertion in the left sub-tree, a similar LL rotation
6. After balance, the height is not changed

Another Example of AVL Tree

Task: use {1,2,3,4,5,6,7} to construct an AVL tree

Special case LR/RL will be teached in the next lesson