Week 10

Deletion from BSTs

1/58

Insertion into a binary search tree is easy.

Deletion from a binary search tree is harder.

Four cases to consider ...

• empty tree ... new tree is also empty
• zero subtrees ... unlink node from parent
• one subtree ... replace by child
• two subtrees ... replace by successor

... Deletion from BSTs

2/58

Case 1: value to be deleted is a leaf (zero subtrees)

... Deletion from BSTs

3/58

Case 1: value to be deleted is a leaf (zero subtrees)

... Deletion from BSTs

4/58

Case 2: value to be deleted has one subtree

... Deletion from BSTs

5/58

Case 2: value to be deleted has one subtree

... Deletion from BSTs

6/58

Case 3a: value to be deleted has two subtrees

Replace deleted node by its immediate successor.

... Deletion from BSTs

7/58

Case 3a: value to be deleted has two subtrees

... Deletion from BSTs

8/58

Case 3b: value to be deleted has two subtrees

Merge subtrees of deleted node; replace deleted node by merged tree.

... Deletion from BSTs

9/58

Case 3b: value to be deleted has two subtrees

Exercise 1: Deletion from Search Trees

10/58

Implement the deletion function

BSTree BSTreeDelete(BSTree t, Key k)

which returns a new tree that does not contain k.

Can be done recursively ...

But eventually we need to remove the root of some subtree.

New Binary Search Tree ADT

11/58

Now called simply Tree, and defined as:

// Item, Key, Node, Link, Tree types as before

// operations on keys
#define cmp(k1,k2) ((k1) - (k2))
#define lt(k1,k2) (cmp(k1,k2) < 0)
#define eq(k1,k2) (cmp(k1,k2) == 0)
#define gt(k1,k2) (cmp(k1,k2) > 0)

// standard tree operations
Tree newTree();
Tree TreeInsert(Tree, Item);
Tree TreeDelete(Tree, Key);
int  TreeFind(Tree, Key);

... New Binary Search Tree ADT

12/58

// more standard tree operations
void dropTree(Tree);
void showTree(Tree);
int  TreeDepth(Tree);
int  TreeNumNodes(Tree);

// normally, internal to ADT
Link rotateR(Link);
Link rotateL(Link);
Tree rebalance(Tree);
Item *get_ith(Tree, int);
Tree partition(Tree, int);

Tree insertAtRoot(Tree, Item);
Tree insertRandom(Tree, Item);

TreeLab

13/58

A shell for manipulating binary search trees

• command interpreter (tlab.c) + Tree ADT (Tree.[ch])

n N Ord Seed = make a new tree
i N = insert N into tree
I N = insert N into tree at root
d N = delete N from tree
f N = search for N in tree
g I = get the i'th element in tree
p I = partition tree around i'th element
R = rotate tree right around root
L = rotate tree left around root
q = quit

... TreeLab

14/58

Usage:   ./tlab #Nodes Order Seed

Possible orders to supply values for insertion

• A = ascending   (10 .. N+9),
• D = descending   (N+9 .. 10)
• P = prefix ... builds balanced tree
• R = random ... could do anything ...

Exercise 2: Generating Values in Prefix Order

15/58

Write a function that generates prefix order sequence

• generates values in range lo .. hi
• first is mid-point, second is mid of lower-half, ...
• store values in array v[0..N-1]

void mkprefix(int *v, int N, int lo, int hi)

E.g.   lo..hi = 1..7   ⇒   4 2 1 3 6 5 7

Balanced Trees

Balanced Binary Search Trees

17/58

Goal: build binary search trees which have

• minimum depth ⇒ minimum worst case search cost

• abs(size(LeftSubtree) - size(RightSubtree)) < 2, for every node
• depth of log₂N ⇒ worst case search O(logN)

• randomize  -  reduce chance of worst-case scenario occuring
• amortize  -  do more work at insertion to make search faster
• optimize  -  implement all operations with performance bounds

Operations for Rebalancing

18/58

New ops to assist with rebalancing: rotation, insert-at-root

... Operations for Rebalancing

19/58

Link rotateR(Link n1)
{
   if (n1 == NULL) return NULL;
   Link n2 = n1->left;
   if (n2 == NULL) return n1;
   n1->left = n2->right;
   n2->right = n1;
   return n2;
}

Left rotation is similar with n1/n2 and left/right switched

Exercise 3: Tree Rotations

20/58

Incorporate rotateL() and rotateR() into TreeLab

• add functions into Tree ADT
• add  R  command to main loop
• add  L  command to main loop

Insertion at Root

21/58

Previous description of BSTs inserted at leaves.

Different approach: insert new value at root.

Method for inserting at root (recursive):

• base case:
  • tree is empty; make new node and make it root
• recursive case:
  • insert new node as root of L/R subtree
  • lift new node to root by R/L rotation

... Insertion at Root

22/58

... Insertion at Root

23/58

Function for insert-at-root:

Tree insertAtRoot(Tree t, Item it)
{ 
   if (t == NULL) return newNode(item);
   int diff = cmp(key(it), key(t->value));
   if (diff == 0)
      t->value = it;
   else if (diff < 0) {
      t->left = insertAtRoot(t->left, it);
      t = rotateR(t);
   }
   else if (diff > 0) {
      t->right = insertAtRoot(t->right, it);
      t = rotateL(t);
   }
   return t;
}

Exercise 4: Insertion at Root

24/58

Incorporate insertAtRoot() into TreeLab

• add function into Tree ADT
• add  I val  command to main loop
• add printf's to insert function to trace rotations

... Insertion at Root

25/58

Analysis of insertion-at-root:

• same complexity as for insertion-at-leaf O(depth)
  • although more actual work for each insertion
• tendency to be balanced, but no balance guarantee
• benefit comes in searching
  • for some apps, search favours recently-added items
  • insertion-at-root ensures these are close to root
• could even consider "move to root when found"
  • effectively provides "self-tuning" search tree

Randomized BST Insertion

26/58

Effects of order of insertion on BST shape:

• best case: keys inserted in pre-order
  (median key first, median of lower half, median of upper half, etc.)
• worst case: keys inserted in ascending/descending order
• average case: keys inserted in random order ⇒ O(log₂N)

Can the algorithm itself introduce some randomness?

Exercise: check the best/worst/average cases in TreeLab

... Randomized BST Insertion

27/58

Approach: normally do leaf insert, randomly do root insert.

Tree insertRandom(Tree t, Item it)
{
   if (t == NULL) return newNode(it);

   int chance = rand() % (size(t)+1);
   if (chance < K) return insertAtRoot(t, it);
   int diff = cmp(key(it), key(t->value));
   if (diff == 0)
      t->value = it;
   else if (diff < 0)
      t->left = insert(t->left, it);
   else if (diff > 0)
      t->right = insert(t->right, it);
   t->nnodes = count(t);
   return t;
}

Exercise 5: Randomized Insertion

28/58

Incorporate insertRandom() into TreeLab

• add function into Tree ADT
• use it as insertion method for n command
• try a variety of random chances
  • 1/(N+1) chance of insertAtRoot()
  • 3/(N+1) chance of insertAtRoot()
  • every third insert is insertAtRoot()
  • every tenth insert is insertAtRoot()

... Randomized BST Insertion

29/58

Cost analysis:

• similar to cost for inserting keys in random order O(log₂N)
• does not rely on keys being supplied in random order

• standard method promotes inorder successor to root
• for the randomised method ...
  • promote inorder successor from right subtree, OR
  • promote inorder predecessor from left subtree
• choice depends on relative sizes of subtrees (favours larger)

Warning: Notation Change

30/58

From now on, we use the following function names:

// return depth of Tree (was TreeDepth)
int depth(Tree t) { ... }

// return #nodes in Tree (was TreeNumNodes)
int size(Tree t) { ... }

// return #nodes in Tree (see later)
int count(Tree t) { ... }

This amounts to changing the Tree ADT interface ... bad for clients.

Tree Size

31/58

New functions for determining tree size:

// efficient; use outside Tree-changing functions
int size(Tree t) 
{
   return (t == NULL) ? 0 : t->nnodes;
}
// inefficient; use while making chages to Tree
int count(Tree t)
{
   if (t == NULL)
      return 0;
   else
      return 1 + count(t->left) + count(t->right);
}

Joining Two Trees

32/58

Tree operations so far have involved just one tree.

An operation on two trees:   t = join(t1,t2)

// Pre-conditions:
// takes two BSTs; returns a single BST
// max(key(t1)) < min(key(t2))

Tree join(Tree t1, Tree t2) { ...  }

// Post-conditions:
// result is a BST (i.e. fully ordered)
// result contains all items from t1 and t2

Allows an alternative formulation of delete()

... Joining Two Trees

33/58

Method for performing tree-join:

• find the min node in the right subtree (t2)
• replace min node by its right subtree
• elevate min node to be new root of both trees

x ≤ depth(t) ≤ x+1, where x = max(depth(t1),depth(t2))

Variation: choose deeper subtree; take root from there.

... Joining Two Trees

34/58

Joining two trees:

Note: t2' may be less deep than t2

... Joining Two Trees

35/58

Implementation of tree-join:

Tree join(Tree t1, Tree t2)
{
   if (t1 == NULL) return t2;
   if (t2 == NULL) return t1;
   Node *curr = t2; Node *parent = NULL;
   // find inorder successor
   while (curr->left != NULL) {
      parent = curr;
      curr = curr->left;
   }
   if (parent != NULL) {
      // unlink curr from parent
      parent->left = curr->right;
      curr->right = t2;
   }
   curr->left = t1;
   return curr;
}

... Joining Two Trees

36/58

Implementation of deletion using tree join:

Tree delete(Tree t, Key k)
{
   if (t == NULL) return NULL;
   int diff = cmp(k, keyOf(t->value));
   if (diff < 0)
      t->left = delete(t->left, k);
   else if (diff > 0)
      t->right = delete(t->right, k);
   else { // found an item with key k
      Tree n;
      if (t->left == NULL && t->right == NULL)
         n = NULL;
      else if (t->left == NULL)
         n = t->right;
      else if (t->right == NULL)
         n = t->left;
      else
         n = join(t->left, t->right);
      free(t);
      t = n;
   }
   return t;
}

Exercise 6: Tree Join

37/58

The tree join operation defined above required

• max(key(t1)) < min(key(t2))

You may use existing operations; you must retain

Tree join(tree t1, Tree t2) { ... }

Splay Trees

38/58

Splay tree insertion modifies insertion-at-root method:

• by considering parent-child-granchild (three level analysis)
• by performing double-rotations based on p-c-g orientation

Splay tree implementations also do rotation-in-search:

• can provide similar effect to periodic rebalance
• improves balance, but makes search more expensive

... Splay Trees

39/58

Cases for splay tree double-rotations:

• case 1: grandchild is left-child of left-child
• case 2: grandchild is right-child of left-child
• case 3: grandchild is left-child of right-child
• case 4: grandchild is right-child of right-child

... Splay Trees

40/58

Double-rotation case for left-child of left-child:

... Splay Trees

41/58

Double-rotation case for right-child of left-child:

... Splay Trees

42/58

Gives good overall (amortized) cost:

• splay has higher insert cost because of rotations
• but (potentially) rotations improve balance
• splay has (potentially) higher search cost (rotations)
• but overall search cost is lower (move after search)
  (using assumption that recently searched keys are likely to be searched again)

But ... still has worst case search cost O(N)

Real Balanced Trees

Better Balanced Binary Search Trees

44/58

So far, we have seen ...

• randomised trees ... make poor performance unlikely
• splay trees ... reasonable amortized performance
• but both types still have O(N) worst case

• AVL trees ... fix imbalances as soon as they occur
• 2-3-4 trees ... use varying-sized nodes to assist balance
• red-black trees ... isomorphic to 2-3-4, but binary nodes

AVL Trees

AVL Trees

46/58

Approach:

• insertion (at leaves) may cause imbalance
• repair balance as soon as we notice imbalance
• repairs done locally, not by overall tree restructure

This can be repaired by a single rotation:

• if left subtree too deep, rotate right
• if right subtree too deep, rotate left

... AVL Trees

47/58

Implementation of AVL insertion

Tree insertAVL(Tree t, Item it)
{
   if (t == NULL) return newNode(it);
   int diff = cmp(key(it), key(t->value));
   if (diff == 0)
      t->value = it;
   else if (diff < 0)
      t->left = insertAVL(t->left, it);
   else if (diff > 0)
      t->right = insertAVL(t->right, it);
   int dL = depth(t->left);
   int dR = depth(t->right);
   if ((dL - dR) > 1) t = rotateR(t);
   else if ((dR - dL) > 1) t = rotateL(t);
   return t;
}

Exercise 7: AVL insertion

48/58

Incorporate insertAVL() into TreeLab

• add function into Tree ADT
• add A val command to main loop
• use the inefficient** version of insertAVL()
  (avoids need to change tree node data structure)

• computes depth() as part of recursion
• computes depth() multiple times on same branch
• depth() itself requires multiple recursion

... AVL Trees

49/58

Analysis of AVL trees:

• trees are height-balanced; subtree depths differ by +/-1
• average/worst-case performance of O(logN)
• require extra data to be stored in each node
• may not be weight-balanced; subtree sizes may differ

2-3-4 Trees

2-3-4 Trees

51/58

2-3-4 trees have three kinds of nodes

• 2-nodes, with two children (same as normal BSTs)
• 3-nodes, two values and three children
• 4-nodes, three values and four children

... 2-3-4 Trees

52/58

2-3-4 trees are ordered similarly to BSTs

In a balanced 2-3-4 tree:

• all leaves are at same distance from the root

... 2-3-4 Trees

53/58

2-3-4 tree implementation:

typedef struct node Node;
typedef struct node *Tree;
struct node {
    int  order;    // 2, 3 or 4
    Item data[3];  // items in node
    Tree child[4]; // links to subtrees
};

Note: we change the name value to data here.

... 2-3-4 Trees

54/58

Make a new 2-3-4 node (always order 2):

Node *newNode(Item it)
{
    Node *new = malloc(sizeof(Node));
    assert(new != NULL);
    new->order = 2;
    new->data[0] = it;
    new->child[0] = new->child[1] = NULL;
    return new;
}

... 2-3-4 Trees

55/58

Searching in 2-3-4 trees:

Item *search(Tree t, Key k)
{
    if (t == NULL) return NULL;
    int i;  int diff;  int nitems = t->order-1;
    // find relevant slot in items
    for (i = 0; i < nitems; i++) {
        diff = compare(k, keyOf(t->data[i]));
        if (diff <= 0) break;
    }    
    if (diff == 0)
        // match; return result
        return &(t->data[i]);
    else
        // keep looking in relevant subtree
        return search(t->child[i], k);
}

... 2-3-4 Trees

56/58

2-3-4 tree searching cost analysis:

• as for other trees, worst case determined by depth d
• 2-3-4 trees are always balanced ⇒ depth is O(logN)
• worst case for depth: all nodes are 2-nodes
  same case as for balanced BSTs, i.e. d ≅ log₂N
• best case for depth: all nodes are 4-nodes
  balanced tree with branching factor 4, i.e. d ≅ log₄N

... 2-3-4 Trees

57/58

Building a 2-3-4 tree ... 7 insertions:

Exercise 8: Insertion into 2-3-4 Tree

58/58

Show what happens when S then U are inserted into this tree:

Produced: 4 Oct 2017