Binary Search Trees

In [64]:
class Node:
    def __init__(self, key, parent=None, left=None, right=None, data=None):
        self.key = key
        self.p = parent
        self.left = left
        self.right = right
        self.data = data
        
class BST:
    def __init__(self, root):
        self.root = root
In [65]:
node1 = Node(3)
node2 = Node(7)
node3 = Node(10)
node4 = Node(13)
node5 = Node(20)

node1.p = node2
node3.p = node2
node2.left = node1
node2.right = node3
node2.p = node4
node5.p = node4
node4.left = node2
node4.right = node5

bst = BST(node4)
In [49]:
def InorderTreeWalk(node):
    if node:
        InorderTreeWalk(node.left)
        print(node.key)
        InorderTreeWalk(node.right)
        
InorderTreeWalk(bst.root)
3
7
10
13
20
In [35]:
def TreeSearch(x, k):
    if (x == None) or (k == x.key): return x
    if k < x.key: return TreeSearch(x.left, k)
    else: return TreeSearch(x.right, k)
In [40]:
TreeSearch(bst.root, 7) != None
Out[40]:
True
In [41]:
TreeSearch(bst.root, 8) != None
Out[41]:
False
In [38]:
def IterativeTreeSearch(x, k):
    current = x
    while current and k != current.key:
        if k < current.key: current = current.left
        else: current = current.right
    return current
In [42]:
IterativeTreeSearch(bst.root, 7) != None
Out[42]:
True
In [43]:
TreeSearch(bst.root, 8) != None
Out[43]:
False
In [45]:
def TreeMinimum(x):
    current = x
    while current.left: current = current.left
    return current

TreeMinimum(bst.root).key
Out[45]:
3
In [47]:
def TreeMaximum(x):
    current = x
    while current.right: current = current.right
    return current

TreeMaximum(bst.root).key
Out[47]:
20
In [66]:
def TreeSuccessor(x):
    if x.right: return TreeMinimum(x.right)
    y = x.p
    current = x
    while y and current == y.right:
        current = y
        y = current.p
    return y
In [67]:
TreeSuccessor(node1).key
Out[67]:
7
In [68]:
TreeSuccessor(node2).key
Out[68]:
10
In [70]:
TreeSuccessor(node5) == None
Out[70]:
True
In [73]:
def TreeInsert(T, z):
    y = None
    x = T.root
    while x:
        y = x
        if z.key < x.key: x = x.left
        else: x = x.right
    z.p = y
    if not y: T.root = x     
    else:
        if z.key < y.key: y.left = z
        else: y.right = z
In [75]:
TreeInsert(bst, Node(1))
TreeInsert(bst, Node(9))
InorderTreeWalk(bst.root)
1
3
7
9
10
13
20
In [ ]: