Tag Archives: Binary Search Tree

Balanced Binary Search Tree

Deletion Algorithm:

Update Height
Identify height imbalance
Check and do if single rotation is possible else if double rotation if possible

        self.height = 0

def delete(x,T,parent=None):
    if T is None:
        print('Element Not Found')
    elif x<T.data:
        T.left = delete(x,T.left,T)
        if height(T.right) - height(T.left) ==2:
            if T.right.right:
                T = singleRotationWithRight(T)
            elif T.right.left:
                T = doubleRotationWithRight(T)
    elif x>T.data:
        T.right = delete(x,T.right,T)
        if height(T.left) - height(T.right) ==2:
            if T.left.left:
                T = singleRotationWithLeft(T)
            elif T.left.right:
                T = doubleRotationWithLeft(T)
    elif T.count==1:
        # 2 CHILDREN
        if T.left and T.right:
            TempNode = findMin(T.right)
            T.data = TempNode.data
            T.right = delete(TempNode.data,T.right,T)
            #No need to check for rotation here, taken care above
        # 0 CHILDREN
        elif T.left is None and T.right is None:
            T = None
        # 1 CHILDREN
        elif T.right is not None:
            T = T.right
            T.parent = parent
        elif T.left is not None:
            T = T.left
            T.parent = parent
    else:
        T.count = T.count - 1
    if T:
        T.height = max(height(T.left),height(T.right)) + 1
    return T

def insert(x,T,parent=None):
    if T is None:
        T = BSTNode(x,parent)
    elif x<T.data:
        T.left = insert(x,T.left,T)
        if height(T.left) - height(T.right) ==2:
            if x<T.left.data:
                T = singleRotationWithLeft(T)
            else:
                T = doubleRotationWithLeft(T)
    elif x>T.data:
        T.right = insert(x,T.right,T)
        if height(T.right) - height(T.left) ==2:
            if x>T.right.data:
                T = singleRotationWithRight(T)
            else:
                T = doubleRotationWithRight(T)
    else:
        T.count = T.count + 1
    T.height = max(height(T.left),height(T.right)) + 1
    return T

def height(P):
    if P is None:
        return -1
    else:
        return P.height

def singleRotationWithLeft(K2):
    K1 = K2.left
    K2.left = K1.right
    K1.right = K2

    K1.height = max(height(K1.left),height(K1.right)) + 1
    K2.height = max(height(K2.left),height(K2.right)) + 1
    return K1

def doubleRotationWithLeft(K3):
    K3.left = singleRotationWithRight(K3.left)
    return singleRotationWithLeft(K3)

def singleRotationWithRight(K1):
    K2 = K1.right
    K1.right = K2.left
    K2.left = K1

    K1.height = max(height(K1.left),height(K1.right)) + 1
    K2.height = max(height(K2.left),height(K2.right)) + 1
    return K2

def doubleRotationWithRight(K1):
    K1.right = singleRotationWithLeft(K1.right)
    return singleRotationWithRight(K1)

test

T = None

T = insert(4,T)
T = insert(2,T)
T = insert(6,T)
T = insert(1,T)

T = insert(3,T)
T = insert(5,T)
T = insert(7,T)

T = insert(16,T)
T = insert(15,T)
T = insert(14,T)
T = insert(13,T)

T = insert(12,T)
T = insert(11,T)
T = insert(10,T)
T = insert(8,T)

""" """

T = delete(5,T)
T = delete(6,T)
T = delete(1,T)

preorder(T)

T = delete(14,T)
T = delete(16,T)
T = delete(15,T)

preorder(T)
inorder(T)

output

13
    7
        3
            2
            4
        11
            10
                8
            12
    15
        14
        16
7
    3
        2
        4
    11
        10
            8
        13
            12
2 (4) 
('back:', 2)
3 (2) 
('next:', 4)
4  
('back:', 4)
7 (6) 
('next:', 8)
8 (10) 
('next:', 10)
('back:', 8)
10 (11) 
('next:', 11)
('back:', 10)
11 (12) 
('next:', 12)
12 (13) 
('next:', 13)
('back:', 12)
13 (14)

git

unable to make it work for deletion… please refer to red and black trees and Algorithms

Binary Search Tree Python Library

Leave a reply

Count, Parent Pointers

Parent pointers are easily implemented for insertion as the recursion travels top to bottom a copy of the parent is maintained. During deletion, There is no need to reallocate the pointer when data from a successor is copied or when a node is completely deleted. Except when a node is equated to either of its left or right children Its new parent has to be updated from current which is going to be deleted to the currents parent which can be obtained as a recursion parameter.

class BSTNode:
    def __init__(self,x,parent):
        self.data = x
        self.left = None
        self.right = None
        self.count = 1
        self.parent = parent

Insertion

def insert(x,T,parent=None):
    if T is None:
        T = BSTNode(x,parent)
    elif x<T.data:
        T.left = insert(x,T.left,T)
    elif x>T.data:
        T.right = insert(x,T.right,T)
    else:
        T.count = T.count + 1
    return T

Deletion

Similar to heaps, a bubble has to be created and moved down untill a leaf node can be deleted. Here its a little bit complex because of the extra constraints. An element is replaced by its child successor repeatedly until a leaf node or a node with single child is reached which is easily deleted. The recursive definition is easy and elegant.

def delete(x,T,parent=None):
    if T is None:
        print('Element Not Found')
    elif x<T.data:
        T.left = delete(x,T.left,T)
    elif x>T.data:
        T.right = delete(x,T.right,T)
    elif T.count==1:
        # 2 CHILDREN
        if T.left and T.right:
            TempNode = findMin(T.right)
            T.data = TempNode.data
            T.right = delete(TempNode.data,T.right,T)
        # 0 CHILDREN
        elif T.left is None and T.right is None:
            T = None
        # 1 CHILDREN
        elif T.right is not None:
            T = T.right
            T.parent = parent
        elif T.left is not None:
            T = T.left
            T.parent = parent
    else:
        T.count = T.count - 1
    return T

def findMin(T):
    if T.left:
        return findMin(T.left)
    else:
        return T

In order Successor

either (left most child of right child or right child) or (left farthest parent’s right parent or right parent)

def next(node):
    if node is None:
        return
    if node.right:
        n = node.right
        while n.left:
            n = n.left
        return n
    else:
        n = node
        while n.parent and n.parent.right is n:
            n = n.parent
        if n.parent and n.parent.left is n:
            return n.parent
        else:
            return

In order Predecessor

either (right most child of left child or left child) or (right farthest parent’s left parent or left parent)

def back(node):
    if node is None:
        return
    if node.left:
        n = node.left
        while n.right:
            n = n.right
        return n
    else:
        n = node
        while n.parent and n.parent.left is n:
            n = n.parent
        if n.parent and n.parent.right is n:
            return n.parent
        else:
            return

Inorder

import sys
def inorder(T):
    if T is None:
        return
    else:
        inorder(T.left)
        b = back(T)
        if b:
            print("back:",b.data)
        sys.stdout.write(str(T.data)+" ")
        if T.parent:
            sys.stdout.write("("+str(T.parent.data)+")")
        print(" ")
        n = next(T)
        if n:
            print("next:",n.data)
        inorder(T.right)

Preorder

def preorder(T,i=0):
    if T is None:
        return
    else:
        for j in range(i):
            sys.stdout.write("    ")
        print(T.data)
        preorder(T.left,i+1)
        preorder(T.right,i+1)

Test

T = None
T = insert(7,T)
T = insert(4,T)
T = insert(2,T)
T = insert(1,T)

T = insert(13,T)
T = insert(15,T)
T = insert(16,T)
T = insert(6,T)

T = insert(5,T)
T = insert(3,T)
T = insert(11,T)
T = insert(14,T)

T = insert(12,T)
T = insert(9,T)
T = insert(8,T)
T = insert(10,T)

T = delete(11,T)
T = delete(12,T)
T = delete(13,T)
T = delete(8,T)
T = delete(6,T)
T = delete(7,T)
preorder(T)
inorder(T)

Output

9
    4
        2
            1
            3
        5
    14
        10
        15
            16
1 (2) 
('next:', 2)
('back:', 1)
2 (4) 
('next:', 3)
('back:', 2)
3 (2) 
('next:', 4)
('back:', 3)
4 (9) 
('next:', 5)
('back:', 4)
5 (4) 
('next:', 9)
('back:', 5)
9  
('next:', 10)
('back:', 9)
10 (14) 
('next:', 14)
('back:', 10)
14 (9) 
('next:', 15)
('back:', 14)
15 (14) 
('next:', 16)
('back:', 15)
16 (15)

Red Black Tree Python Implementation

git

O(h) algo for the Inorder Successor/Predecessor of a Binary Search Tree Node using parent pointers!

Leave a reply

class Node:
	def __init__(self, data):
		"""
		Node constructor

		@param data node data object
		"""
		self.left = None
		self.right = None
		self.data = data
		self.count = 1
		self.parent = None
	
	def preorder(self):
		print(self.data)
		if self.left:
			self.left.preorder()
		if self.right:
			self.right.preorder()
	def postorder(self):
		if self.left:
			self.left.postorder()
		if self.right:
			self.right.postorder()
		print(self.data)
	def inorder(self):
		if self.left:
			self.left.inorder()
		print(self.data)
		b = self.back()
		if b:
			print("back:",b.data)
		n = self.next()
		if n:
			print("next:",n.data)
		if self.right:
			self.right.inorder()
	
	def insert(self, data):
		if data < self.data:
			if self.left is None:
				self.left = Node(data)
				self.left.parent = self
			else:
				self.left.insert(data)
		elif data > self.data:
			if self.right is None:
				self.right = Node(data)
				self.right.parent = self				
			else:
				self.right.insert(data)
		else:
			self.count = self.count + 1

	def lookup(self, data, parent=None):
		if data < self.data:
			if self.left is None:
				return None, None
			return self.left.lookup(data, self)
		elif data > self.data:
			if self.right is None:
				return None, None
			return self.right.lookup(data, self)
		else:
			return self, parent

	def delete(self, data):
		# get node containing data
		node, parent = self.lookup(data)
		if node.count==1:
			if node is not None:
				children_count = node.children_count()

			if children_count == 0:
				# if node has no children, just remove it
				if parent.left is node:
					parent.left = None
				else:
					parent.right = None
			elif children_count == 1:
				# if node has 1 child
				# replace node by its child
				if node.left:
					n = node.left
				else:
					n = node.right
				n.parent = parent
				if parent.left is node:
					parent.left = n
				else:
					parent.right = n
				del node
			else:
				# if node has 2 children
				# find its successor
				parent = node
				successor = node.right
				while successor.left:
					parent = successor
					successor = successor.left
				# replace node data by its successor data
				node.data = successor.data
				# fix successor's parent's child
				if parent.left == successor:
					parent.left = successor.right
					successor.right.parent = parent.left
				else:
					parent.right = successor.right
					successor.right.parent = parent.right
		elif node.count>1:
			node.count = node.count - 1
	
	def children_count(self):
		"""
		Returns the number of children

		@returns number of children: 0, 1, 2
		"""
		if self is None:
			return None
		cnt = 0
		if self.left:
			cnt += 1
		if self.right:
			cnt += 1
		return cnt
	
	def back(self):
		if self.left:
			n = self.left
			while n.right:
				n = n.right
			return n
		else:
			n = self
			while n.parent and n.parent.left is n:
				n = n.parent
			if n.parent and n.parent.right is n:
				return n.parent
			else:
				return None
	
	def next(self):
		if self.right:
			n = self.right
			while n.left:
				n = n.left
			return n
		else:
			n = self
			while n.parent and n.parent.right is n:
				n = n.parent
			if n.parent and n.parent.left is n:
				return n.parent
			return None
		return self

if __name__ == "__main__":
	root = Node(8)
	root.insert(3)
	root.insert(10)
	root.insert(1)
	root.insert(6)
	root.insert(4)
	root.insert(7)
	root.insert(14)
	root.insert(13)
	
	# DELETION
	#root.delete(3)
	
	# FIND
	'''
	node, parent = root.lookup(8)
	if node:
		print(node.data, "x", node.count)
	if parent:
		print("-->", parent.data)
	'''
	
	# NEXT
	#node2 = node.next()
	#node3 = node.back()
	#print("next: ",node2.data)
	#print("back",node3.data)
	
	# TRAVERSAL
	#root.preorder()
	#print("---")
	#root.postorder()
	#print("===")
	root.inorder()

'''
output
1
next: 3
3
back: 1
next: 4
4
back: 3
next: 6
6
back: 4
next: 7
7
back: 6
next: 8
8
back: 7
next: 10
10
back: 8
next: 13
13
back: 10
next: 14
14
back: 13
'''

On-line Insertion into Sorted Arrays BST and Heaps

Leave a reply

Insertion of 50,000 integers in Python
Sorted Array
execution time: 62.228999853134155 seconds
Binary Search Tree
execution time: 0.8529999256134033 seconds
Heap
execution time: 0.15599989891052246 seconds

I can see the array has nothing but leniar progression to figure out the location of an element thus taking so much time. Heaps though need to bubble up unlike BST, functions better than the BST because it is always balanced or depth of tree is lowest.!

Binary Search Tree with Repetition In Python

Leave a reply

minor code adaptations from Laurent Luce’s Blog

refer Weiss for theory!

class Node:
	"""
	Tree node: left and right child + data which can be any object
	"""
	def __init__(self, data):
		"""
		Node constructor

		@param data node data object
		"""
		self.left = None
		self.right = None
		self.data = data
		self.count = 1

	def insert(self, data):
		"""
		Insert new node with data

		@param data node data object to insert
		"""
		if data < self.data:
			if self.left is None:
				self.left = Node(data)
			else:
				self.left.insert(data)
		elif data > self.data:
			if self.right is None:
				self.right = Node(data)
			else:
				self.right.insert(data)
		else:
			self.count = self.count + 1

	def lookup(self, data, parent=None):
		"""
		Lookup node containing data

		@param data node data object to look up
		@param parent node's parent
		@returns node and node's parent if found or None, None
		"""
		if data < self.data:
			if self.left is None:
				return None, None
			return self.left.lookup(data, self)
		elif data > self.data:
			if self.right is None:
				return None, None
			return self.right.lookup(data, self)
		else:
			return self, parent

	def delete(self, data):
		"""
		Delete node containing data

		@param data node's content to delete
		"""
		# get node containing data
		node, parent = self.lookup(data)
		if node.count==1:
			if node is not None:
				children_count = node.children_count()

			if children_count == 0:
				# if node has no children, just remove it
				if parent.left is node:
					parent.left = None
				else:
					parent.right = None
			elif children_count == 1:
				# if node has 1 child
				# replace node by its child
				if node.left:
					n = node.left
				else:
					n = node.right
				if parent.left is node:
					parent.left = n
				else:
					parent.right = n
				del node
			else:
				# if node has 2 children
				# find its successor
				parent = node
				successor = node.right
				while successor.left:
					parent = successor
					successor = successor.left
				# replace node data by its successor data
				node.data = successor.data
				# fix successor's parent's child
				if parent.left == successor:
					parent.left = successor.right
				else:
					parent.right = successor.right
		elif node.count>1:
			node.count = node.count - 1
	
	def children_count(self):
		"""
		Returns the number of children

		@returns number of children: 0, 1, 2
		"""
		if self is None:
			return None
		cnt = 0
		if self.left:
			cnt += 1
		if self.right:
			cnt += 1
		return cnt



if __name__ == "__main__":
	root = Node(8)
	root.insert(3)
	root.insert(3)
	root.insert(10)
	root.insert(1)
	root.insert(6)
	root.insert(4)
	root.insert(7)
	root.insert(14)
	root.insert(13)
	
	root.delete(3)
	root.delete(3)
	
	node, parent = root.lookup(4)
	print(str(node.data) + " x " + str(node.count) + "-->" + str(parent.data))
	node, parent = root.lookup(6)
	print(str(node.data) + " x " + str(node.count) + "-->" + str(parent.data))