5. Binary Search Tree

Binary Search Tree¶

In [7]:

from utils.nodes import BinaryTreeNode as Node
from utils.tree_traversal import TreeTraversal as tt

from utils.nodes import BinaryTreeNode as Node from utils.tree_traversal import TreeTraversal as tt

Insertion¶

• Steps
  1. root is none, make a new node, assign to root and return
  2. if root is not none then check for the following
  3. if data is already present at the current root.data, return root
  4. else if data is less than current root.data, insertion is to be done to the left. Create a new node and point root.left to it
  5. similarly do this to right

In [8]:

def insert(root, data):

    # create a new node when there is none
    if root is None:
        root = Node(data)
        return root
    else:
        if root.data == data:
            return root
        elif data < root.data:
            root.left = insert(root.left, data)
        else:
            root.right = insert(root.right, data)

    return root

def insert(root, data): # create a new node when there is none if root is None: root = Node(data) return root else: if root.data == data: return root elif data < root.data: root.left = insert(root.left, data) else: root.right = insert(root.right, data) return root

Deletion¶

• Case

  • Key to be deleted is a leaf
    • Simply remove the leaf
  • Key to be deleted is a node with one child(either left or right)
    • Copy the child to this root.data and remove child

  • Key to be deleted is a node with 2 subtrees.

    • 2 cases are possible therefore 2 trees are possible

      • replace this node with it's largest in order predecessor

        OR

      • replace this node with it's smallest in order successor

In [9]:

def get_largest_inorder_predecessor(root):
    current = root

    while current.right is not None:
        current = current.right

    return current

def get_largest_inorder_predecessor(root): current = root while current.right is not None: current = current.right return current

In [10]:

def get_smallest_inorder_successor(root):
    temp = root
    while temp.left is not None:
        temp = temp.left
    return temp

def get_smallest_inorder_successor(root): temp = root while temp.left is not None: temp = temp.left return temp

In [18]:

def delete_node(root, item, successor_tree=True):

    # base case
    if root is None:
        return root

    # if item is in left sub tree
    if item < root.data:
        root.left = delete_node(root.left, item)

    # if item is in right sub tree
    elif item > root.data:
        root.right = delete_node(root.right, item)
    else:
        if root.left is None:
            temp = root.right
            root = None
            return temp

        elif root.right is None:
            temp = root.left
            root = None
            return temp

        if successor_tree:
            successor = get_smallest_inorder_successor(root.right)
            root.data = successor.data
            root.right = delete_node(root.right, successor.data)
        else:
            predecessor = get_largest_inorder_predecessor(root.left)
            root.data = predecessor.data
            root.left = delete_node(root.left, predecessor.data)

    return root

def delete_node(root, item, successor_tree=True): # base case if root is None: return root # if item is in left sub tree if item < root.data: root.left = delete_node(root.left, item) # if item is in right sub tree elif item > root.data: root.right = delete_node(root.right, item) else: if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp if successor_tree: successor = get_smallest_inorder_successor(root.right) root.data = successor.data root.right = delete_node(root.right, successor.data) else: predecessor = get_largest_inorder_predecessor(root.left) root.data = predecessor.data root.left = delete_node(root.left, predecessor.data) return root

In [24]:

root = None
root = insert(root, 8)
root = insert(root, 3)
root = insert(root, 1)
root = insert(root, 6)
root = insert(root, 7)
root = insert(root, 10)
root = insert(root, 14)
root = insert(root, 4)

root = None root = insert(root, 8) root = insert(root, 3) root = insert(root, 1) root = insert(root, 6) root = insert(root, 7) root = insert(root, 10) root = insert(root, 14) root = insert(root, 4)

In [25]:

tt.traverse_inorder(root)

tt.traverse_inorder(root)

1
3
4
6
7
8
10
14

In [26]:

root = delete_node(root, 14)

root = delete_node(root, 14)

came here: 14

In [22]:

tt.traverse_inorder(root)

tt.traverse_inorder(root)

1
3
4
6
7
8
14

In [23]:

root = delete_node(root, 6)

root = delete_node(root, 6)

came here: 7

In [17]:

tt.traverse_inorder(root)

tt.traverse_inorder(root)

1
3
4
7
8
10
14

In [ ]: