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.

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

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