BST - General BST, AVL, LCA

Successor node
#1, with parent pointer
From page 292, CLRS 
TREE-SUCCESSOR.(x)
  if x:right != NIL
  return TREE-MINIMUM.(x:right)
  y = x:p
  while y != NIL and x == y:right
  x = y
  y = y:p
  return y
No need to compare keys

#2, without parent pointer

struct node * inOrderSuccessor(struct node *root, struct node *n)
{
    // step 1 of the above algorithm
    if( n->right != NULL )
        return minValue(n->right);
 
    struct node *succ = NULL;
 
    // Start from root and search for successor down the tree
    while (root != NULL)
    {
        if (n->data < root->data)
        {
            succ = root;
            root = root->left;
        }
        else if (n->data > root->data)
            root = root->right;
        else
           break;
    }
 
    return succ;
}

--------------------------------------------
node insertion
TREE-INSERT.T; ´/
1 y D NIL
2 x D T:root
3 while x ¤ NIL
4 y D x
5 if ´:key < x:key
6 x D x:left
7 else x D x:right
8 ´:p D y
9 if y == NIL
10 T:root D ´ // tree T was empty
11 elseif ´:key < y:key
12 y:left D ´
13 else y:right D ´
node deletion, Page 295, CLRS
3 basic cases:
If ´ has no children, then we simply remove it by modifying its parent to replace ´ with NIL as its child.

If ´ has just one child, then we elevate that child to take ´’s position in the tree by modifying ´’s parent to replace ´ by ´’s child.


If ´ has two children, then we find ´’s successor y—which must be in ´’s right subtree—and have y take ´’s position in the tree. The rest of ´’s original right subtree becomes y’s new right subtree, and ´’s left subtree becomes y’s new left subtree. This case is the tricky one because, as we shall see, it matters whether y is ´’s right child.

Check Wiki for all all operations of BST
"Another way to explain insertion is that in order to insert a new node in the tree, its key is first compared with that of the root. If its key is less than the root's, it is then compared with the key of the root's left child. If its key is greater, it is compared with the root's right child. This process continues, until the new node is compared with a leaf node, and then it is added as this node's right or left child, depending on its key."

----------------------------------------------

AVL, from Wiki
rotation

 if (balance_factor(L) == 2) { //The left column
   let P=left_child(L)
   if (balance_factor(P) == -1) { //The "Left Right Case"
      rotate_left(P) //reduce to "Left Left Case"
   }
   //Left Left Case
   rotate_right(L);
 } else { // balance_factor(L) == -2, the right column
   let P=right_child(L)
   if (balance_factor(P) == 1) { //The "Right Left Case"
      rotate_right(P) //reduce to "Right Right Case"
   }
   //Right Right Case
   rotate_left(L);
 }

Deletion
Steps to consider when deleting a node in an AVL tree are the following:

1. If node X is a leaf or has only one child, skip to step 5. (node Z will be node X)
2. Otherwise, determine node Y by finding the largest node in node X's left sub tree (in-order predecessor) or the smallest in its right sub tree (in-order successor).
3. Replace node X with node Y (remember, tree structure doesn't change here, only the values). In this step, node X is essentially deleted when its internal values were overwritten with node Y's.
4. Choose node Z to be the old node Y.
5. Attach node Z's subtree to its parent (if it has a subtree). If node Z's parent is null, update root. (node Z is currently root)
6. Delete node Z.
7. Retrace the path back up the tree (starting with node Z's parent) to the root, adjusting the balance factors as needed.

The retracing can stop if the balance factor becomes −1 or +1 indicating that the height of that subtree has remained unchanged. If the balance factor becomes 0 then the height of the subtree has decreased by one and the retracing needs to continue. If the balance factor becomes −2 or +2 then the subtree is unbalanced and needs to be rotated to fix it. If the rotation leaves the subtree's balance factor at 0 then the retracing towards the root must continue since the height of this subtree has decreased by one. This is in contrast to an insertion where a rotation resulting in a balance factor of 0 indicated that the subtree's height has remained unchanged.

The time required is O(log n) for lookup, plus a maximum of O(log n) rotations on the way back to the root, so the operation can be completed in O(log n) time.

---------------------------------------------------------

Red black tree with size attribute in each node, page 341, CLRS

Retrieving an element with a given rank

OS-SELECT.x; i /

1 r D x:left:size C 1

2 if i == r

3 return x

4 elseif i < r

5 return OS-SELECT.x: left; i/

6 else return OS-SELECT.x:right; i r/

Determining the rank of an element

OS-RANK.T; x/

1 r D x:left:size C 1

2 y D x

3 while y ¢¥ T:root

4 if y == y:p:right

5 r D r C y:p: left:size C 1

6 y D y:p

7 return r

--------------------------------------------------
List all keys between two given keys in a bst

LIST(tree;l;h)
lca=LCA(tree;l;h)
result=[]
NODE-LIST(lca;l;h;result)
return result

NODE-LIST(node;l;h;result)
if node==NIL
return
if l <= node.key and node.key >= h
ADD-KEY(result;node:key)
if node.key >= l
NODE-LIST(node.left;l;h;result)
if node.key <= h
NODE-LIST(node.right;l;h;result)

LCA(tree;l;h)
node=tree:root
until node==NIL or (l <= node.key and h >= node.key)
if l < node.key
node = node.left
else
node = node.right
return node