When would you use a binary search tree over a treap?
I think I would use a binary search tree over a treap in terms of complexity in implementation. Binary search trees are simpler. However, practical-wise, I would use a binary search three if I have a set of numbers that are sorted randomly because if it’s sorted, then my binary tree would be like a linked list.
Discuss how a treap balances itself.
One difference with a treap is that it contains a numerical priority p. This random number will help us “randomize” and balance our treap. When we put in our nodes in the treap, we act first as if it was a binary search tree. Afterwards, we use the bubble-up function to change the positions of our nodes in terms of priority p. Inside the bubble-up function, we call on the rotations, either rotate left or rotate right, on our nodes and we base it up with p. Once this happens, our treap becomes balanced, because we are getting the idea of random binary trees, but instead of the value of the node, we are using a random priority queue p. This “randomness” will help us balance our treap.
Discuss how you would implement a treap without storing the priority.
Discuss how you would implement a treap without storing the priority $p$ (hint-hint: #tables).
I would implement a treap without storing the priority number p, with the use of hash tables. Hash tables usually have a randomizer with the use of hash codes. We can get the value of the new node, put that value in a hash code, and from there, we can put the new node to where it should be placed. Hash codes can be very random at times, especially when they produce a complicated and random value. This can be very useful for us if we would want to implement a treap without storing the priority.
Code Used:
class Node: # creates the node class
def __init__(self, data):
self.data = data
self.parent = None
self.left = None
self.right = None
# stack implementation
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if (self.size() == 0):
raise "Nothing to remove since stack is empty!"
else:
return self.items.pop()
def display(self):
print(self.items)
return
def size(self):
return len(self.items)
# binary expression tree implementation
class BinaryExpressionTree:
def __init__(self):
self.stack = Stack() # uses the stack implementation
def preorder(self, root): # prints the pre-order traversal
# prints root --> left --> right
if root:
print(root.data, end = " "),
self.preorder(root.left)
self.preorder(root.right)
return
def inorder(self, root): # prints the in-order traversal with modified code for parenthesis ()
# prints left --> root --> right
if root:
if root.data in "0123456789": # checks if the node is an operand
print(root.data, end = "")
else:
print("(", end = "")
self.inorder(root.left)
print("", root.data, "", end = "")
self.inorder(root.right)
print(")", end = "")
return
def postorder(self, root): # prints the post-order traversal
# prints left --> right --> root
if root:
self.postorder(root.left)
self.postorder(root.right)
print(root.data,end = " ")
return
def evaluate(self, root): # evaluating the binary expression tree
# if the tree is empty
if root is None:
return 0
# if the current node is leaf node
if root.left is None and root.right is None:
return int(root.data)
# evaluate left tree
left_sum = self.evaluate(root.left)
# evaluate right tree
right_sum = self.evaluate(root.right)
# check which operation to apply
if root.data == '+':
return int(left_sum + right_sum)
elif root.data == '-':
return int(left_sum - right_sum)
elif root.data == '*':
return int(left_sum * right_sum)
else:
return int(left_sum / right_sum)
input_dat = []
# reading input.dat
with open('input.dat', 'r') as input:
input.readline()
input.readline()
for line in input:
input.readline()
input_dat.append(line.split())
# print(input_dat)
expressionTrees = [] # creates a list for all test cases of binary expression trees
# evaluating the expression tree from the output
# in here, the binary expression tree is also created using the stack implementation
for expression in input_dat:
expressionTree = BinaryExpressionTree()
for character in expression: # If character is an operator ('+', '-', '/', '*'), pop() 2 values out and make the 2 values the children of the operator (don't forget to set the parent as well); push(x) this node back into the stack.
if character == "+":
node = Node(character)
node.parent = character
node.right = expressionTree.stack.pop()
node.left = expressionTree.stack.pop()
expressionTree.stack.push(node)
continue
elif character == "-":
node = Node(character)
node.parent = character
node.right = expressionTree.stack.pop()
node.left = expressionTree.stack.pop()
expressionTree.stack.push(node)
continue
elif character == "*":
node = Node(character)
node.parent = character
node.right = expressionTree.stack.pop()
node.left = expressionTree.stack.pop()
expressionTree.stack.push(node)
continue
elif character == "/":
node = Node(character)
node.parent = character
node.right = expressionTree.stack.pop()
node.left = expressionTree.stack.pop()
expressionTree.stack.push(node)
continue
else:
expressionTree.stack.push(Node(character)) # If character is an operand, push(x) into the stack.
expressionTrees.append(expressionTree) # appending all the expression trees in a list
# print(expressionTrees)
# print()
# printing the outputs
for i in expressionTrees:
i.preorder(i.stack.items[0])
print()
i.inorder(i.stack.items[0])
print()
i.postorder(i.stack.items[0])
print()
print(i.evaluate(i.stack.items[0]))
Sample Input
490 73 515 983 968 111 635 577 940 243 629 940 114 267 510 120 822 333 308 744 83 304 522 817 976 924 834 71 557 781 750 372 881 141 106 649 644 106 245 103 885 790 283 401 14 474 257 787 749 848
-82 24 63 -35 28 97 37 -89 -26 -6
-79 -44 87 19 -16 85 53 3 27 56
-44 -26 -16 -6 87 19 85 53 3 27
-91 -84 -71 -59 -56 -13 89 59 31 50
-44 -29 -8 8 12 29 62 63 84 91Sample Output
5 5
7 7
9 7
10 5
10 4
Chav's Blog 