FCI-4 Binary Search Tree

Delete, Rotate, Balance

Recall that a binary search tree stores an arbitrary number of values in sorted order.

Delete

Move left subtree up to replace deleted node

Move right subtree to right-most leaf of left

Rotate

A rotation in a BST involves moving a ndoe below one of its children.

Balance

A BST is balanced if at every node in the tree, the depth of the left subtree is within 1 of the depth of the right subtree, i.e.

A balanced BST has search time, while the worst case for a BST’s search time is when values inserted in order, or reverse order.

Day’s Algorithm

An unbalanced tree can be made balanced via rotations.

Day’s Algorithm:

Firstly, use right rotations to linearize the tree to the right, turning the tree into a vine (or called backbone)

Secondly, perform left rotations on alternating nodes of the vind, in repeated passes, to construct a balanced tree.

Initial backbond length is blen = len(vine) - 1
Number of left rotations is m = blen // 2
Revised backbone lenght: blen = blen - m - 1
Recompute m = blen // 2

iterate on m until m = 0

BST Code Implementation

BST class


class BinaryTree:
    class _BTNode:
        def __init__(self, value, left = None, right = None):
            self._value = value
            self._left = left
            self._right = right

    def __init__(self):
        self._top = None

    def insert(self, value):
        if self._top == None:
            self._top = BinaryTree._BTNode(value)
        else:
            self._insert_help(self._top, value)

    def _insert_help(self, cur_node, value):
        if value < cur_node._value:
            if cur_node._left == None:
                cur_node._left = BinaryTree._BTNode(value)
            else:
                self._insert_help(cur_node._left, value)
        elif value > cur_node._value:
            if cur_node._right == None:
                cur_node._right = BinaryTree._BTNode(value)
            else:
                self._insert_help(cur_node._right, value)

    def __str__(self):
        return self._str_help(self._top)

    def _str_help(self, cur_node):
        if cur_node == None:
            return ''
        else:
            left_str = self._str_help(cur_node._left)
            right_str = self._str_help(cur_node._right)
            ret = str(cur_node._value)
            if left_str:
                ret = left_str + ' ' + ret
            if right_str:
                ret = ret + ' ' + right_str
            return ret
    
    def sum(self):
        return self._sum_help(self._top)
    
    def _sum_help(self, cur_node):
        if cur_node == None:
            return 0
        else:
            return (self._sum_help(cur_node._left)
                    + cur_node._value
                    + self._sum_help(cur_node._right))
    
    def size(self):
        return self._size_help(self._top)
    
    def _size_help(self, cur_node):
        if cur_node == None:
            return 0
        else:
            return (self._size_help(cur_node._left)
                    + 1
                    + self._size_help(cur_node._right))
    
    def print_pretty(self):
        return self._print_pretty_help(self._top, 0)
    
    def _print_pretty_help(self, cur_node, indent_level):
        if cur_node == None:
            return
        else:
            self._print_pretty_help(cur_node._right, indent_level + 1)
            print(' ' * indent_level * 8, cur_node._value)
            self._print_pretty_help(cur_node._left, indent_level + 1)
    
    def depth(self):
        return self._depth_help(self._top)
    
    def _depth_help(self, cur_node):
        if cur_node == None:
            return 0
        else:
            left_d = self._depth_help(cur_node._left)
            right_d = self._depth_help(cur_node._right)
            return 1 + (left_d if left_d > right_d else right_d)
    
    def __eq__(self, other):
        return str(self) == str(other)
    
    def min(self):
        if self._top == None:
            return None
        else:
            # the minimum is the left-most value
            cur_node = self._top
            while cur_node._left != None:
                cur_node = cur_node._left
            return cur_node._value
    
    def max(self):
        if self._top == None:
            return None
        else:
            # the maximum is the right-most value
            cur_node = self._top
            while cur_node._right != None:
                cur_node = cur_node._right
            return cur_node._value
    
    def mean(self):
        if self._top == None:
            return None
        else:
            return self.sum() / self.size()
    
    def __contains__(self, value):
        if self._top == None:
            return False
        else:
            return self._contains_help(self._top, value)
    
    def _contains_help(self, cur_node, value):
        if cur_node == None:
            return False
        elif cur_node._value == value:
            return True
        elif cur_node._value < value:
            return self._contains_help(cur_node._right, value)
        else:    # cur_node._value > value
            return self._contains_help(cur_node._left, value)
    
    def copy(self):
        bt_new = BinaryTree()
        bt_new._top = self._copy_help(self._top)
        return bt_new
    
    def _copy_help(self, cur_node):
        if cur_node == None:
            return None
        else:
            return BinaryTree._BTNode(cur_node._value,
                                      self._copy_help(cur_node._left),
                                      self._copy_help(cur_node._right))
    
    def negate(self):
        if self._top != None:
            self._negate_help(self._top)
    
    def _negate_help(self, cur_node):
        if cur_node == None:
            return
        else:
            cur_node._value *= -1
            self._negate_help(cur_node._left)
            self._negate_help(cur_node._right)
            cur_node._left, cur_node._right = cur_node._right, cur_node._left

    def delete(self, value):
        assert self._top, "the tree is empty"
        p_node = self._BTNode(None, None, self._top)
        cur_node = self._top
        while cur_node:
            if cur_node._value < value: 
                p_node = cur_node
                cur_node = cur_node._right
            elif cur_node._value > value:
                p_node = cur_node
                cur_node = cur_node._left
            else:
                left_sub, right_sub = cur_node._left, cur_node._right

                if left_sub: # append right sub on left sub
                    cur_node = left_sub
                    while cur_node._right:
                        cur_node = cur_node._right
                    else:
                        cur_node._right = right_sub
                else:
                    left_sub = right_sub
                
                if not p_node._value or p_node._value < value:
                    p_node._right = left_sub
                else:
                    p_node._left = left_sub

                if not p_node._value: # if top is deleted
                    self._top = p_node._right
                break

    def is_balanced_helper(self, cur_node):
        if not cur_node:
            return True
        return abs(self._depth_help(cur_node._left) - self._depth_help(cur_node._right)) <= 1 \
                and self.is_balanced_helper(cur_node._left) \
                and self.is_balanced_helper(cur_node._right)
    
    def is_balanced(self):
        return self.is_balanced_helper(self._top)
    
    def rotate_left(self, value):
        p_node = self._BTNode(None, None, self._top)
        cur_node = self._top
        dir = 'right'
        while cur_node: # find the node
            if cur_node._value < value: 
                p_node = cur_node
                cur_node = cur_node._right
                dir = 'right'
            elif cur_node._value > value:
                p_node = cur_node
                cur_node = cur_node._left
                dir = 'left'
            else:
                _, right_sub = cur_node._left, cur_node._right
                cur_node._right = right_sub._left
                right_sub._left = cur_node
                if dir == 'right':
                    p_node._right = right_sub
                else:
                    p_node._left = right_sub
                if not p_node._value: # if is operating on root node
                    self._top = right_sub
                break

    def rotate_right(self, value):
        p_node = self._BTNode(None, None, self._top)
        cur_node = self._top
        dir = 'right'
        while cur_node: # find the node
            if cur_node._value < value: 
                p_node = cur_node
                cur_node = cur_node._right
                dir = 'right'
            elif cur_node._value > value:
                p_node = cur_node
                cur_node = cur_node._left
                dir = 'left'
            else:
                left_sub, _ = cur_node._left, cur_node._right
                cur_node._left = left_sub._right
                left_sub._right = cur_node
                if dir == 'right':
                    p_node._right = left_sub
                else:
                    p_node._left = left_sub
                if not p_node._value: # if is operating on root node
                    self._top = left_sub
                break

    def linearize(self):
        cur_node = self._top
        while cur_node:
            if cur_node._left:
                self.rotate_right(cur_node._value)
                self.linearize()
            else:
                cur_node = cur_node._right

    def Day_balance(self):
        self.linearize()
        blen = self.size() - 1
        m = blen // 2
        while m:
            r_values = []
            cur_node = self._top
            for _ in range(m):
                r_values.append(cur_node._value)
                cur_node = cur_node._right._right
            for v in r_values:
                self.rotate_left(v)
            blen -= (m+1)
            m = blen // 2

Main Script


import BinaryTree_hw3 as bt

# 1.a
print('\x1b[6;30;42m' + '======【 a 】======' + '\x1b[0m')
bt1 = bt.BinaryTree()     # an empty BinaryTree
bt1.insert(12)
bt1.insert(7)
bt1.insert(22)
bt1.insert(-4)
bt1.insert(3)
bt1.insert(6)
bt1.insert(15)
bt1.insert(18)

bt2 = bt.BinaryTree()     # an empty tree

print('bt1:', bt1)        # bt1: -4 3 6 7 12 15 18 22
print('bt2:', bt2)        # bt2:

print('bt1.sum():', bt1.sum())   # bt1.sum(): 79

print('bt1.size():', bt1.size())    # should display 8
print('bt2.size():', bt2.size())    # should display 0

print('\nbt1.print_pretty():')
bt1.print_pretty()      # should display:
            #         22
            #                         18
            #                 15
            # 12
            #         7
            #                                 6
            #                         3
            #                 -4
print('\nbt2.print_pretty():')
bt2.print_pretty()      # should display no output

print('bt1.depth():', bt1.depth())    # should display 5 (not 3!)
print('bt2.depth():', bt2.depth())    # should display 0

# 1.b
print('\x1b[6;30;42m' + '======【 b 】======' + '\x1b[0m')
bt1.delete(6)
print('\nafter bt1.delete(6): bt1.print_pretty():')
bt1.print_pretty()      # should display:
            #         22
            #                         18
            #                 15
            # 12
            #         7
            #                         3
            #                 -4
bt1.delete(15)
print('\nafter bt1.delete(15): bt1.print_pretty():')
bt1.print_pretty()      # should display:
            #         22
            #                 18
            # 12
            #         7
            #                         3
            #                 -4
bt1.delete(8)           # there is no 8: nothing should happen
print('\nafter bt1.delete(8): bt1.print_pretty():')
bt1.print_pretty()      # should display:
            #         22
            #                 18
            # 12
            #         7
            #                         3
            #                 -4
bt1.delete(12)
print('\nafter bt1.delete(12): bt1.print_pretty():')
bt1.print_pretty()      # should display:
            #         22
            #                 18
            # 7
            #                 3
            #         -4


# 1.c
print('\x1b[6;30;42m' + '======【 c 】======' + '\x1b[0m')
bt3 = bt.BinaryTree()
bt3.insert(8)
bt3.insert(14)
bt3.insert(12)
bt3.insert(19)
bt3.insert(15)
print('\nbt3.print_pretty():')
bt3.print_pretty()      # should display:
            #                 19
            #                         15
            #         14
            #                 12
            # 8

print('\nbt1.is_balanced():', bt1.is_balanced())  # True
print('\nbt2.is_balanced():', bt2.is_balanced())  # True
print('\nbt3.is_balanced():', bt3.is_balanced())  # False


# 1.d
print('\x1b[6;30;42m' + '======【 d 】======' + '\x1b[0m')
print('\nbt1.print_pretty():')
bt1.print_pretty()      # should display:
            #         22
            #                 18
            # 7
            #                 3
            #         -4
bt1.rotate_left(-4)
print('\nafter bt1.rotate_left(-4): bt1.print_pretty():')
bt1.print_pretty()      # should display:
            #         22
            #                 18
            # 7
            #         3
            #                 -4
bt1.rotate_left(7)
print('\nafter bt1.rotate_left(7): bt1.print_pretty():')
bt1.print_pretty()      # should display:
            # 22
            #                 18
            #         7
            #                 3
            #                         -4
bt1.rotate_left(2)    # nothing happens
print('\nafter bt1.rotate_left(2): bt1.print_pretty():')
bt1.print_pretty()      # should display:
            # 22
            #                 18
            #         7
            #                 3
            #                         -4
print('\nbt1.is_balanced():', bt1.is_balanced())  # False


# 1.e
print('\x1b[6;30;42m' + '======【 e 】======' + '\x1b[0m')
print('\nbt1.print_pretty():')
bt1.print_pretty()
      # should display:
            # 22
            #                 18
            #         7
            #                 3
            #                         -4
bt1.rotate_right(2)    # nothing happens
print('\nafter bt1.rotate_right(2): bt1.print_pretty():')
bt1.print_pretty()
      # should display:
            # 22
            #                 18
            #         7
            #                 3
            #                         -4
bt1.rotate_right(22)
print('\nafter bt1.rotate_right(22): bt1.print_pretty():')
bt1.print_pretty()
      # should display:
            #         22
            #                 18
            # 7
            #         3
            #                 -4
bt1.rotate_right(3)
print('\nafter bt1.rotate_right(3): bt1.print_pretty():')
bt1.print_pretty()
      # should display:
            #         22
            #                 18
            # 7
            #                 3
            #         -4
print('\nbt1.is_balanced():', bt1.is_balanced())  # True


# 1.f
print('\x1b[6;30;42m' + '======【 f 】======' + '\x1b[0m')
print('\nbt3.print_pretty():')
bt3.print_pretty()      # should display:
            #                 19
            #                         15
            #         14
            #                 12
            # 8
print('\nbt3.is_balanced():', bt3.is_balanced())  # False
bt3.Day_balance()
print('\nafter bt3.Day_balance(): bt3.print_pretty():')
bt3.print_pretty()
print('\nbt3.is_balanced():', bt3.is_balanced())  # True

bt4 = bt.BinaryTree()
for j in range(20):
    bt4.insert(j)
print('\nbt4.print_pretty():')
bt4.print_pretty()
print('\nbt4.is_balanced():', bt4.is_balanced())  # False
bt4.Day_balance()
print('\nafter bt4.Day_balance(): bt4.print_pretty():')
bt4.print_pretty()
print('\nbt4.is_balanced():', bt4.is_balanced())  # True

AVL Tree

AVL tree and Red-Black Tree are both self-balancing trees. The self-balancing BST remains balanced after each insert or delete.

In an AVL Tree, each node is augmented with the height of the node. The node’s balance factor is then BF(node) = height(node.left) - height(node.right)

if BF(node) > 0: the node is left-heavy

if BF(node) < 0: the node is right-heavy

if BF(node) == 0: the node is balanced

When we insert or delete a node, we must maintain the balance factor invariant for each node, within the values of . Therefore, we need to check the BF at each node on the way up to the top, a BF of +-2 requires rotation to restore balance. Four cases:

BF(cur) > 1 and BF(cur._left) ≥ 0

BF(cur) > 1 and BF(cur._left) < 0

BF(cur) < -1 and BF(cur._right) ≤ 0

BF(cur) < -1 and BF(cur._right) > 0

AVL Class Implementation


class AVLTree:
    class _AVLNode:
        def __init__(self, value):
            self._value = value
            self._left = None
            self._right = None
            self._ht = 1  # a new node has _ht of 1


    def __init__(self):
        self._top = None


    def insert(self, v):
        if self._top is None:
            self._top = AVLTree._AVLNode(v)
        else:
            self._top = self._insert_helper(self._top, v)


    def _insert_helper(self, cur, v):
        # insert the new v
        if v < cur._value:
            if cur._left is None:
                cur._left = self._AVLNode(v)
            else:
                cur._left = self._insert_helper(cur._left, v)
        elif v > cur._value:
            # pass  # !!! FINISH ME !!!
            if cur._right is None:
                cur._right = self._AVLNode(v)
            else:
                cur._right = self._insert_helper(cur._right, v)

        # update the current node's height
        cur._ht = 1 + self._max_child_height(cur)

        # check balance factor, and rotate as necessary
        bf = self._bal_factor(cur)

        if bf > 1 and v < cur._left._value:
            cur = self._rotate_right(cur)
        elif bf < -1 and v > cur._right._value:
            cur = self._rotate_left(cur)
        elif bf > 1 and v > cur._left._value:
            cur._left = self._rotate_left(cur._left)
            cur = self._rotate_right(cur)
        elif bf < -1 and v < cur._right._value:
            cur._right = self._rotate_right(cur._right)
            cur = self._rotate_left(cur)

        return cur


    def _max_child_height(self, cur):
        lf_ht = 0 if not cur._left else cur._left._ht
        rt_ht = 0 if not cur._right else cur._right._ht
        return max(lf_ht, rt_ht)


    def _bal_factor(self, cur):
        lf_ht = 0 if not cur._left else cur._left._ht
        rt_ht = 0 if not cur._right else cur._right._ht
        return lf_ht - rt_ht


    def _rotate_left(self, cur):
        rt = cur._right
        rt_lf = rt._left
        rt._left = cur
        cur._right = rt_lf
        cur._ht = 1 + self._max_child_height(cur)
        rt._ht = 1 + self._max_child_height(rt)
        return rt


    def _rotate_right(self, cur):
        # pass # !!! FINISH ME !!!
        lt = cur._left
        lt_rt = lt._right
        lt._right = cur
        cur._left = lt_rt
        cur._ht = 1 + self._max_child_height(cur)
        lt._ht = 1 + self._max_child_height(lt)
        return lt


    def print_pretty(self):
        self._print_pretty_help(self._top, 0)


    def _print_pretty_help(self, cur, space): # iterate by right->middle->left
        if cur == None:
            return
        space += 8
        self._print_pretty_help(cur._right, space) # print right
        print('')
        for i in range(8, space):
            print(end=" ")
        print(f"{cur._value} ({cur._ht})")                         # print middle
        self._print_pretty_help(cur._left, space) # print right!


    def delete(self, v):
        # pass # !!! FINISH ME !!!
        if self._top is None:
            return
        else:
            self._top = self._delete_helper(self._top, v)


    def _delete_helper(self, cur, v):
        if not cur:
            return cur

        # Search for the node to delete
        if v < cur._value:
            cur._left = self._delete_helper(cur._left, v)
        elif v > cur._value:
            cur._right = self._delete_helper(cur._right, v)
        else:
            # Node with only one child or no child (Case 1, 2)
            if not cur._left:
                return cur._right
            elif not cur._right:
                return cur._left

            # Node with two children, get the in-order successor (Case 3)
            temp = self._get_min_value_node(cur._right)
            cur._value = temp._value
            cur._right = self._delete_helper(cur._right, temp._value)

        # Update height of the current node
        cur._ht = 1 + self._max_child_height(cur)

        # Check balance factor and apply rotations if necessary
        bf = self._bal_factor(cur)

        # Left heavy
        if bf > 1 and self._bal_factor(cur._left) >= 0:
            return self._rotate_right(cur)
        if bf > 1 and self._bal_factor(cur._left) < 0:
            cur._left = self._rotate_left(cur._left)
            return self._rotate_right(cur)
        # Right heavy
        if bf < -1 and self._bal_factor(cur._right) <= 0:
            return self._rotate_left(cur)
        if bf < -1 and self._bal_factor(cur._right) > 0:
            cur._right = self._rotate_right(cur._right)
            return self._rotate_left(cur)

        return cur


    def _get_min_value_node(self, cur):
        if cur is None or cur._left is None:
            return cur
        return self._get_min_value_node(cur._left)


    def is_AVLTree(self):   # a tree is an AVL tree if it is a BST and its height values are correct
        return self._is_valid_BST(self._top) and self._has_valid_heights(self._top)


    def _is_valid_BST(self, cur):
        if cur is None:
            return True
        if cur._left and cur._left._value >= cur._value:
            return False
        if cur._right and cur._right._value <= cur._value:
            return False
        return self._is_valid_BST(cur._left) and self._is_valid_BST(cur._right)


    def _has_valid_heights(self, cur):
        if cur is None:
            return True
        if cur._ht != 1 + max(self._height(cur._left), self._height(cur._right)):
            return False
        return self._has_valid_heights(cur._left) and self._has_valid_heights(cur._right)


    def _height(self, node):
        if node is None:
            return 0
        return 1 + max(self._height(node._left), self._height(node._right))

AVL main script


import numpy as np
import AVLTree as avl

# 1.a -- test the insert() method
print('\nTesting left-side inserts...')
t1 = avl.AVLTree()
for k in range(100, -1, -10):
    t1.insert(k)
    print('after t1.insert(' + str(k) + '):', end=' ')
    if t1.is_AVLTree():
        print('t1 is a valid AVL Tree')
    else:
        print('t1 is NOT a valid AVL Tree!')
        exit(0)

input('Left-side insert tests complete.  Press Enter to continue...')


print('\nTesting right-side inserts...')
t2 = avl.AVLTree()
for k in range(0, 101, 10):
    t2.insert(k)
    print('after t2.insert(' + str(k) + '):', end=' ')
    if t2.is_AVLTree():
        print('t2 is a valid AVL Tree')
    else:
        print('t2 is NOT a valid AVL Tree!')
        exit(0)

input('Right-side insert tests complete.  Press Enter to continue...')



print('\nTesting random inserts...')
np.random.seed(0)
t3 = avl.AVLTree()
for k in range(30):
    val = np.random.randint(-100, 100)
    t3.insert(val)
    print('after t3.insert(' + str(val) + '):', end=' ')
    if t3.is_AVLTree():
        print('t3 is a valid AVL Tree')
    else:
        print('t3 is NOT a valid AVL Tree!')
        exit(0)

input('Random insert tests complete.  Press Enter to continue...')


# 1.b -- test the print_pretty() method
t4 = avl.AVLTree()
print('\nt4 initially contains:')
t4.print_pretty()    # should display an empty line
input('\nDone displaying initial t4.  Press Enter to continue...')
t4.insert(12)
t4.insert(9)
t4.insert(5)
print('\nt4 after inserts of 12, 9, and 5:')
t4.print_pretty()    # should display val (ht) for each node, approximately like this:
#       12 (1)
#  9 (2)
#       5 (1)
input('\nDone displaying t4 after three inserts.  Press Enter to continue...')
print('\nt1:')
t1.print_pretty()
input('\nDone displaying t1.  Press Enter to continue...')
print('\nt2:')
t2.print_pretty()
input('\nDone displaying t2.  Press Enter to continue...')
print('\nt3:')
t3.print_pretty()
input('\nDone displaying t3.  Press Enter to continue...')


# 1.c -- test random inserts and deletes
np.random.seed(0)
a50 = np.random.randint(-100, 100, 50) # 50 random ints, from -100 to 100
a50_copy = a50.copy()
np.random.shuffle(a50_copy)   # shuffle a50_copy values in random order
t5 = avl.AVLTree()
for i in a50:
    t5.insert(i)
print('t5 after 50 random inserts:')
t5.print_pretty()
input('\nDone displaying t5.  Press Enter to continue...')
for i in range(25):
    t5.delete(a50_copy[i])    # delete a value known to be in t5
    t5.delete(np.random.randint(-100, 100))  # delete a value that may or may not be in t5
print('t5 after 50 random deletes:')
t5.print_pretty()
input('\nDone displaying t5.  Press Enter to continue...')