Briefly discuss how the color rules help with balancing the tree (write a bit about 2-4 trees). Compare the performance of this red black tree to a random binary search tree or treap.
The four color rules of the red-black tree help the tree maintain a structure that is balanced. To understand more on red-black trees, it can be think of as first a 2-4 tree structure with colors and more rules. When we try to insert or remove a node, we would change the entire structure of the tree immediately. In 2-4 trees, by adding a leaf we would split w into w and w’, meaning we would get another whole structure. And that’s just the leaf. Removing also has its fix ups. Now, for a red-black tree, we have the same idea – we change the form of the tree by adding or removing. Every after insertion and removal of nodes, we perform a fix-up method for both functions and its implementation is quite complicated. However, the benefit of this is having a good time complexity with no operations running longer than O(log n).
Comparing the performance of red-black trees to a random binary search tree or a treap, I would say that we are more sure that the operations of red-black trees would perform better. This is because as we are adding or removing nodes, we are dynamically changing the shape of the tree, hence balancing the tree. If I were to rank by performance from worst to best, I would say, the random BSTs, treaps then red-black trees. Treaps do have rotations and structure changes when adding and removing values but they don’t have rules like red-black trees do. With this, we would still have the possibility of a worse time complexity of O(n), but it’s at minimum, because of the randomness of the priority. It’s unlike red-black trees, wherein it’s really sure that it has at most, O(log n). However, the cost for this good time complexity for red-black trees is the complicated implementation of it.
Code Used:
Red = 'Red'
Black = 'Black'
# sample RB tree of test_case 1
#
# quick, black
# / \
# fox, red the, black
# / \
# brown, black lazy, black
# / \ / \
# dog, red jumps, red over, red
#
#
class RedBlackNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.parent = None
self.color = Red
class RedBlackTree:
def __init__(self):
NIL = RedBlackNode(0) # We use this NIL node to be used over again when we will attempt to insert a node
NIL.color = Black
self.NIL = NIL
self.root = self.NIL # Our starting root node will be an empty NIL node and its color will always be black
self.fixUpsCount = 0 # counter for the number of fix ups done from addFixUp()
self.comparisonsCount = 0 # counter for the number of the number of searches done by find()
def add(self, u):
y = self.NIL # variable for the parent of the added node
temp = self.root #
while temp != self.NIL: # goes down the tree until at leaf nodes that are NIL nodes
y = temp
if u.data < temp.data:
temp = temp.left
else:
temp = temp.right
if y.data == u.data:
break
u.parent = y
if y == self.NIL:
self.root = u
elif u.data == y.data: # checks if data is already existing, then returns
return
elif u.data < y.data: # if data of child is less than its parent,
y.left = u
else:
y.right = u
# adds a value of NIL (None) values that are still nodes for our leaf nodes in the tree
u.right = self.NIL
u.left = self.NIL
self.addFixup(u) # we apply the fix up, everytime we call up addFixup
def addFixup(self, u):
while u.parent.color == Red:
if u.parent == u.parent.parent.left: # u.parent is the left child
y = u.parent.parent.right #uncle of u
if y.color == Red: #case 1
u.parent.color = Black
y.color = Black
u.parent.parent.color = Red
u = u.parent.parent
self.fixUpsCount += 1
else: # case 2 or case 3
if u == u.parent.right: # case 2
u = u.parent # marked u.parent as new u
self.rotate_left(u)
# case 3
u.parent.color = Black # made parent black
u.parent.parent.color = Red # made parent red
self.rotate_right(u.parent.parent)
self.fixUpsCount += 1
self.fixUpsCount += 1
else: # u.parent is the right child
y = u.parent.parent.left #uncle of u
if y.color == Red:
u.parent.color = Black
y.color = Black
u.parent.parent.color = Red
u = u.parent.parent
self.fixUpsCount += 1
else:
if u == u.parent.left:
u = u.parent # marked u.parent as new u
self.rotate_right(u)
u.parent.color = Black # made parent black
u.parent.parent.color = Red # made parent red
self.rotate_left(u.parent.parent)
self.fixUpsCount += 1
self.fixUpsCount += 1
self.root.color = Black
def rotate_left(self, x):
y = x.right
x.right = y.left
if y.left != self.NIL:
y.left.parent = x
y.parent = x.parent
if x.parent == self.NIL: # x is root
self.root = y
elif x == x.parent.left: # x is left child
x.parent.left = y
else: #x is right child
x.parent.right = y
y.left = x
x.parent = y
def rotate_right(self, x):
y = x.left
x.left = y.right
if y.right != self.NIL:
y.right.parent = x
y.parent = x.parent
if x.parent == self.NIL: # x is root
self.root = y
elif x == x.parent.right: # x is right child
x.parent.right = y
else: # x is left child
x.parent.left = y
y.right = x
x.parent = y
def sizeOfTree(self, node): # recursively gets the number of all nodes except the NIL
if node == None or node == self.NIL:
return 0
else:
return 1 + self.sizeOfTree(node.left) + self.sizeOfTree(node.right)
def blackHeight(self, node):
if node == None:
return 0
if node.color == Black: # gets only the height for black colored nodes
return 1 + max(self.blackHeight(node.left),self.blackHeight(node.right))
else:
return 0 + max(self.blackHeight(node.left),self.blackHeight(node.right))
def find(self, search_node):
cur_node = self.root # starts off at the root node
comparisons = 0 # counter for the number of comparison made
while cur_node is not None:
if search_node < cur_node.data: # if node is at the left side of the tree
cur_node = cur_node.left
comparisons += 1
elif search_node > cur_node.data: # if node is at the right side of the tree
cur_node = cur_node.right
comparisons += 1
else:
comparisons += 1
return comparisons
return comparisons
input_dat = []
# reading from input.dat
with open('Week 9\input.dat', 'r') as input:
for line in input:
input_dat.append(line.split())
input_dat = input_dat[1:]
# print(input_dat)
# print()
for _input in input_dat:
words = _input[1:-1]
search_word = _input[-1]
RBTree = RedBlackTree()
for word in words:
RBTree.add(RedBlackNode(word))
# print(word)
print(RBTree.sizeOfTree(RBTree.root), end=' ')
print(RBTree.fixUpsCount, end=' ')
print(RBTree.blackHeight(RBTree.root), end=' ')
print(RBTree.find(search_word), end=' ')
# print(search_word)
print()
# I can't really get the same sample output for the number of fixups.
# For reference, I used this website
# https://www.codesdope.com/course/data-structures-red-black-trees-insertion/?fbclid=IwAR1POX8pduiRS1NiREzm5m7TqwacuX4WxLSvXjDYUYRm2Iemg9oKneVByFM
Sample Input
3
9 the quick brown fox jumps over the lazy dog over
14 I would rather make a new one line long haiku than this sentence now haiku
18 somebody once told me the world was gonna roll me I ain't the sharpest tool in the shed worldSample Output
8 10 3 4
14 24 4 5
15 20 4 4
Chav's Blog 