#id1:207032764
#name1:Nitsan Honen
#username1:nitsanhonen
#id2:206539496
#name2:Nitzan Zacharia
#username2:zacharia1
"""A class represnting a node in an AVL tree"""
class AVLNode(object):
"""Constructor, you are allowed to add more fields.
@type key: int
@param key: key of your node
@type value: string
@param value: data of your node
"""
def __init__(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None
self.parent = None
self.height = -1
"""returns whether self is not a virtual node
@rtype: bool
@returns: False if self is a virtual node, True otherwise.
"""
def is_real_node(self):
if self.height == -1:
return False
return True
"""
A class implementing an AVL tree.
"""
class AVLTree(object):
"""
Constructor, you are allowed to add more fields.
"""
def __init__(self):
self.root = AVLNode(None, None)
self.max = None
self.tree_size = 0
#internal functions
"""A function for internal use, checks if a child is its father left child or not.
creator: Nitzan Z.
@type node: AVLNode
@pre: the node must have a parent attribute different then null
@param node: the node of the child
@rtype: boolean
@returns: true if the child is its father left child, false otherwise
"""
def childIsLeft(self, node):
if (node.parent.left == node):
return True
return False
"""A function for internal use, updates a node's height.
creator: Nitsan H.
@type node: AVLNode
@param node: the node whose height needs to be changed
@rtype: None
"""
def updateHeight(self, node):
height = max(node.right.height, node.left.height)
node.height = height+1
"""A function for internal use, rotates the tree and updates relevant heights and sizes.
creator: Nitsan H.
@type parent: AVLNode
@param parent: the parent that needs to become a child
@type child: AVLNode
@pre: the child is a right or left child of the parent
@param: child: the child that needs to become a parent
@rtype: None
"""
def rotation(self, parent, child):
#find if the child is its father's left or right child, and rotate accordingly.
direction = self.childIsLeft(child)
grandpa = parent.parent
#if parent wasn't the root, update the child as the grandpa's child, instead of parent
#else update the root
if grandpa != None:
if self.childIsLeft(parent):
grandpa.left = child
else:
grandpa.right = child
else:
self.root = child
#move its inner child to be a child of the old parent,
#change the parent to be the child's child and the other way around
match direction:
case True:
childHolder = child.right
child.right = parent
parent.left = childHolder
childHolder.parent = parent
case False:
childHolder = child.left
child.left = parent
parent.right = childHolder
childHolder.parent = parent
parent.parent = child
child.parent = grandpa
#only child's and parent's heights and sizes changed, so update them
self.updateHeight(parent)
self.updateHeight(child)
"""A function for internal use, returns the sibling of a given node.
creator: Nitsan H.
@type child_node: AVLNode
@pre: child_node is a real node
@rtype: AVLNode (virtual or real)
@returns: right son of the nodes parent if node is the left son, left son of the nodes parent if node is the right son
"""
def getOtherSon(self, child_node):
parent = child_node.parent
if not parent:
return None
if self.childIsLeft(child_node):
return parent.right
else:
return parent.left
"""A function for internal use, returns the height difference between the nodes parent and the parent's other son.
creator: Nitzan Z.
@type child_node: AVLNode
@pre: child_node has a parent
@rtype: int
@returns: rheight difference between the nodes parent and his other child
"""
def getOtherDiff(self,child_node):
return child_node.parent.height - self.getOtherSon(child_node).height
"""A function for internal use, rebalnces the tree after insertations by promoting nodes and performing rotations when needed.
creator: Nitzan Z.
@type child_node: AVLNode
@param child_node: node that requires promotion
@pre: child_node's parent was a leaf before insertation, making the tree imbalanced after insertion
@type count: int
@param count: counter of the number of promotions performed
@rtype: int
@returns: sum of total promotions performed untill reaching a correctly balanced tree
"""
def promote(self, child_node, count):
count += 1 #increment promotion count
parent = child_node.parent
#if we reached the root, promotion is not needed, subtract 1 from count and return
if parent is None:
return count-1
grandparent = parent.parent
#case 1: height difference between the current node and parent is 0, and parent and sibling is 1.
if self.getOtherDiff(child_node) == 1 and parent.height==child_node.height:
parent.height +=1 #correct parent's height
if grandparent is not None: #imbalance problem might moved up, continue recursively
count = self.promote(parent, count)
else: #imbalance solved, return
return count
else: #compute height differences
height_dif_org = parent.height - child_node.height
height_dif_other = self.getOtherDiff(child_node)
#Cases 2,3 : check if one height diff is 2, and the other one is 0
if max(height_dif_org,height_dif_other)-min(height_dif_org,height_dif_other) == 2:
if self.childIsLeft(child_node): #check if we're in case 2:
if child_node.height-child_node.left.height == 1 and child_node.height - child_node.right.height == 2:
self.rotation(parent, child_node) #preform a single rotation
#check if we're in case 3:
elif child_node.height-child_node.left.height == 2 and child_node.height - child_node.right.height == 1:
self.rotation(child_node, child_node.right) #preform a double rotation
self.rotation(parent, child_node.parent)
return count-1
##double rotate
else:
#check if we're in case 2:
if child_node.height-child_node.left.height == 2 and child_node.height - child_node.right.height == 1:
self.rotation(parent, child_node) #preform a single rotation
#check if we're in case 3:
elif child_node.height-child_node.left.height == 1 and child_node.height - child_node.right.height == 2:
self.rotation(child_node, child_node.left) #preform a double rotation
self.rotation(parent, child_node.parent)
return count-1
return count
"""A function for internal use, attaches a new node to a specific parent as a leaf, with corresponding key and value
creator: Nitzan Z.
@type key: int
@pre: parent is the correct insertion point in the tree
@param key: key of item that is to be inserted to self
@type val: string
@param val: the value of the item
@type parent: AVL Node
@param parent: parent is either a leaf or has one child, opposite of side
@type side: int
@param side: 0 for attaching to the left, 1 for attaching to the right
@rtype: AVLNode
@returns: returns the new node that was attached.
"""
def hang_child (self, parent, key, val, side=0):
child = AVLNode(key, val)
child.right = AVLNode(None, None)
child.left = AVLNode(None, None)
child.height = 0
self.tree_size += 1
if parent is None: #if parent is None, the new node will be the root of the tree
self.root = child
self.max = self.root
else:
if side == 1 or key > parent.key : #insert to the right
parent.right = child
else:
parent.left = child #insert to the left
if self.max and key>self.max.key: #update max if needed
self.max = child
elif not self.max:
self.max = child
child.parent = parent
child.right.parent = child
child.left.parent = child
return child
"""A function for internal use, returns the AVLNoded following node according
to the sorted order of keys.
creator: Nitsan H.
@type node: AVLNode
@param node: the node forwhich we want to find a successor
@rtype: AVLNode
@returns: an AVLNode which is the successor of node or None if node is the max node.
"""
def getSuccessor(self, node):
#follows the exact algorithm we saw in class
if node.right.is_real_node():
nextNode = node.right
while nextNode.left.is_real_node():
nextNode = nextNode.left
return nextNode
nextNode = node.parent
while nextNode != None and node == nextNode.right:
node = nextNode
nextNode = node.parent
return nextNode
"""A function for internal use, returns the AVLNoded preceding node according
to the sorted order of keys.
creator: Nitsan H.
@type node: AVLNode
@param node: the node forwhich we want to find a predecessor
@rtype: AVLNode
@returns: an AVLNode which is the predecessor of node or None if node is the minimum node.
"""
def getPredecessor(self, node):
#follows the exact algorithm we saw in class
if node.left.is_real_node():
nextNode = node.left
while nextNode.right.is_real_node():
nextNode = nextNode.right
return nextNode
nextNode = node.parent
while nextNode != None and node == nextNode.left:
node = nextNode
nextNode = node.parent
return nextNode
"""A function for internal use, replaces a node as its parent child with the given node
creator: Nitsan H.
@type child: AVLNode
@pre: node has a parent
@param child: the node to be replaces
@type otherChild: AVLNode
@pre: its height won't cause the AVL to be illegal
@param otherChild: the node to replace with
"""
def replaceAsChild(self, child, otherChild):
#check if the current child is a left child or not and replace accordingly
isLeft = self.childIsLeft(child)
if isLeft:
child.parent.left = otherChild
else:
child.parent.right = otherChild
otherChild.parent = child.parent
child.parent = None
"""A function for internal use, checks if the local subtree (me, parent, sibling) is a legal subtree in an AVL
creator: Nitsan H.
@type node: AVLNode
@pre: node has a parent
@param node: one of the children in the subtree
@rtype: boolean, int
@returns: true if the subtree is legal, false if its not.
also for k my height, p my sibling's height, will return |k-p|.
"""
def isLegalSubTree(self, node):
#checks each of the cases where it will be a legal AVL
heightDiff = node.parent.height - node.height
otherDiff = self.getOtherDiff(node)
if(heightDiff == 1 and otherDiff == 1):
return True,0
elif(heightDiff == 2 and otherDiff == 1):
return True,1
elif(heightDiff == 1 and otherDiff == 2):
return True,1
#if its not a legal AVL, return false and the height diff.
diffsDiff = max(heightDiff, otherDiff) - min(heightDiff, otherDiff)
return False,diffsDiff
"""A function for internal use, does rotations and demotions as necessary, until tree after deletion is a legal AVL
creator: Nitsan H.
@type node: AVLNode
@param node: a child of the subtree forwhich we want to fix the deletion upwards, after deletion
"""
def fixDeletion(self, node):
#if I got to the root, everything below must be legal
if node == self.root:
return
#check if we've reached a legal subtree (me, my parent and my sibling)
isLegal, currDiff = self.isLegalSubTree(node)
if isLegal:
return
#if we and my sibling are of the same height, demote parent and keep fixing upwards
elif currDiff == 0:
node.parent.height -= 1
self.fixDeletion(node.parent)
#if i'm at height k and sibling is k+2, we are intersted in its closest child to us (inner nephew)
elif currDiff == 2:
sibling = self.getOtherSon(node)
if self.childIsLeft(node):
inNephew = sibling.left
else:
inNephew = sibling.right
nephewsDiff = self.isLegalSubTree(inNephew)[1]
#if both nephews are of the same height, do a single rotation (demotion will happen there)
#which will fix the tree
if nephewsDiff == 0:
self.rotation(node.parent, sibling)
return
#else if the inner nephew is the same height as me, do a single rotation (demotion will happen there)
#and continue fixing upwards
elif nephewsDiff == 1 and inNephew.height == node.height:
self.rotation(node.parent, sibling)
self.fixDeletion(sibling)
#else I know inner newphew is of k+1 height (I'm of k height)
#do a double rotation (demotion will happen there)
#and continue fixing upwards
else:
self.rotation(sibling, inNephew)
self.rotation(node.parent, inNephew)
self.fixDeletion(inNephew)
return
"""A function for internal use, updates the pointers of a node so that they won't point on any real nodes
creator: Nitzan Z.
@type node: AVLNode
@param node: node that should point to no other nodes
@rtype: None
"""
def nullify(self, node):
if node.is_real_node():
node.parent = None
node.left = AVLNode(None, None)
node.right = AVLNode(None, None)
"""A function for internal use, finds the maximum node in the left subtree of a given node
creator: Nitzan Z.
@type node: AVLNode
@pre: node has a real left son
@param node: root of the subtree where we're looking for the maximum node
@rtype: AVLNode
@returns: node with maximum key in the left subtreee of the original node
"""
def maxInLeft(self, node):
curr = node.left
while curr.right.is_real_node():
curr = curr.right
return curr
"""A function for internal use, finds the maximum node in the right subtree of a given node
needed only if when we perform join when splitting, the max key is higher up (at a different subtree)
and we want to preserve the correct max node during those joins.
creator: Nitzan Z.
@type node: AVLNode
@pre: node has a real right son
@param node: root of the subtree where we're looking for the maximum node
@rtype: AVLNode
@returns: node with maximum key in the right subtreee of the original node
"""
def maxInRight(self, node):
#if we're looking for the maximum node in the whole tree, no need to traverse
if node.key == self.root.key:
return self.max
curr = node.right
while curr.right.is_real_node():
curr = curr.right
return curr
"""A function for internal use, builds an AVL subtree that node is his root
creator: Nitzan Z.
@type node: AVLNode
@pre: node has a parent
@param node: the root of the subtree we want to build
@rtype: AVLTree
@returns: subtree of node as a new AVL tree
"""
def buildSubtree(self, node):
subTree = AVLTree()
if not node.is_real_node():
return subTree
else:
if self.childIsLeft(node): #updates the max field of the new tree
subTree.max = self.maxInLeft(node.parent)
else:
subTree.max = self.maxInRight(node.parent)
subTree.root = node
subTree.root.parent = None
return subTree
"""A function for internal use, a recursive in order walk of the tree, updates a given list
creator: Nitsan H.
@type node: AVLNode
@param node: the root of the (sub)tree forwhich we want a sorted array
@rtype: None
"""
def inOrderWalk(self, node, curr_array):
#follows the exact algorithm we saw in class, but insted of printing the key, value, appendning to an array
if node.is_real_node():
self.inOrderWalk(node.left, curr_array)
curr_array.append((node.key, node.value))
self.inOrderWalk(node.right, curr_array)
"""A function for internal use, will do a normal search within the tree, starting with a custom node.
creator: Nitsan H.
@type key: int
@param key: a key to be searched
@type start: AVLNode
@param start: the node to start searching from
@rtype: (AVLNode,int)
@returns: a tuple (x,e,p) where x is the node corresponding to key (or None if not found),
e is the number of edges on the path between the starting node and ending node+1,
p is the parent a node corresponding to key should've been under if it wasnt found (None if we found it)
"""
def searchFrom(self, key, start):
node = start
e = 0
#as long as we didnt find the requested key, continue searching
while node.key != key:
e += 1
#continue searching down the tree
#unless the next node would be virtual
if node.key < key:
if not node.right.is_real_node():
return None,e,node
node = node.right
elif node.key > key:
if not node.left.is_real_node():
return None,e,node
node = node.left
return node,e+1,None
#External functions
"""searches for a node in the dictionary corresponding to the key (starting at the root)
creator: Nitsan H.
@type key: int
@param key: a key to be searched
@rtype: (AVLNode,int)
@returns: a tuple (x,e) where x is the node corresponding to key (or None if not found),
and e is the number of edges on the path between the starting node and ending node+1.
"""
def search(self, key):
if not self.root.is_real_node():
return None, 0
#start searching from the root
node, e, parent = self.searchFrom(key, self.root)
return node, e
"""searches for a node in the dictionary corresponding to the key, starting at the max
creator: Nitzan Z.
@type key: int
@param key: a key to be searched
@rtype: (AVLNode,int)
@returns: a tuple (x,e) where x is the node corresponding to key (or None if not found),
and e is the number of edges on the path between the starting node and ending node+1.
"""
def finger_search(self, key):
root_key = self.root.key
node = self.max
count = 0
if not self.root.is_real_node():
return None, 0
if key > node.key:
return None, 1
#starting from the maximum node (as long as it's not the root),
#go up until you reach a node with smaller\equal key then the one we're searching for
while node.key!=root_key and node.key>key :
node = node.parent
count+=1
#if we stopped at the key we're looking for, return it's node and num of edges
if node.key==key:
return (node, count+1)
#from the node we stopped at, search the key per usual
node_found, e, h = self.searchFrom(key, node)
if key > node.key and e>0:
#if the last edge we visited will be repeated, subtract 2 to resolve
return (node_found, e+count-2)
if key < node.key and count>0:
return (node, e+count)
if(node_found == None): #if key was not found
return (node_found, e)
"""inserts a new node into the dictionary with corresponding key and value (starting at the root)
creator: Nitzan Z.
@type key: int
@pre: key currently does not appear in the dictionary
@param key: key of item that is to be inserted to self
@type val: string
@param val: the value of the item
@rtype: (AVLNode,int,int)
@returns: a 3-tuple (x,e,h) where x is the new node,
e is the number of edges on the path between the starting node and new node before rebalancing,
and h is the number of PROMOTE cases during the AVL rebalancing
"""
def insert(self, key, val):
h = 0
e = 0
node = self.root
if not node.is_real_node(): #check if the AVL tree is empty - if so, insert as root
return self.hang_child(None,key,val),e, h
else:
nodeFound, e, parent = self.searchFrom(key, node)
if key > parent.key: #attaches the child to the correct parent
child = self.hang_child(parent,key,val,1)
else:
child = self.hang_child(parent, key, val)
#case 1: parent was not a leaf, no rebalancing needed
if parent.right.is_real_node() and parent.left.is_real_node():
return child, e, h
# case 2: parent was a leaf, rebalancing needed
else:
h = self.promote(child,0)
return child, e, h
"""inserts a new node into the dictionary with corresponding key and value, starting at the max
creator: Nitzan Z.
@type key: int
@pre: key currently does not appear in the dictionary
@param key: key of item that is to be inserted to self
@type val: string
@param val: the value of the item
@rtype: (AVLNode,int,int)
@returns: a 3-tuple (x,e,h) where x is the new node,
e is the number of edges on the path between the starting node and new node before rebalancing,
and h is the number of PROMOTE cases during the AVL rebalancing
"""
def finger_insert(self, key, val):
if not self.root.is_real_node():
self.hang_child(None, key, val)
return self.root, 0, 0
else:
node = self.max
max_key = node.key
count = 0
h = 0
while node.key != self.root.key and node.key > key:
node = node.parent
count += 1
if key > node.key and count>0:
#if the last edge we visited will be repeated,
#subtract 2 to resolve the repetition
count = count -2
if key > max_key: #special case - search is not needed
e = 1
parent = node
else:
_, e, parent = self.searchFrom(key, node)
if parent.key > key:
child = self.hang_child(parent, key, val)
elif parent.key < key:
child = self.hang_child(parent, key, val, 1)
#case 1: parent was not a leaf, no rebalancing needed
if parent.right.is_real_node() and parent.left.is_real_node():
return child, e+count, h
# case 2: parent was a leaf, rebalancing needed
else:
h = self.promote(child,0)
return child, e+count, h
"""deletes node from the dictionary
creator: Nitsan H.
@type node: AVLNode
@pre: node is a real pointer to a node in self
"""
def delete(self, node):
#update max
if node == self.max:
self.max = self.getPredecessor(node)
#if the node has two children, delete its successor and replace node with successor
if node.left.is_real_node() and node.right.is_real_node():
successor = self.getSuccessor(node)
self.delete(successor)
node.key = successor.key
node.value = successor.value
#if we want to delete the root and it only has one child
elif node == self.root:
self.tree_size -= 1
if not node.right.is_real_node():
self.root = node.left
node.left = None
else:
self.root = node.right
node.right = None
self.root.parent = None
#if we want to delete a node with one child or none
else:
self.tree_size -= 1
#replace the node as a child with its non-virtual child
#or with a virtual child if node is leaf
if not node.left.is_real_node():
self.replaceAsChild(node, node.right)
node = node.right
else:
self.replaceAsChild(node, node.left)
node = node.left
#start rotating\demoting
self.fixDeletion(node)
return
"""joins self with item and another AVLTree
creator: Nitsan H.
@type tree2: AVLTree
@param tree2: a dictionary to be joined with self
@type key: int
@param key: the key separting self and tree2
@type val: string
@param val: the value corresponding to key
@pre: all keys in self are smaller than key and all keys in tree2 are larger than key,
or the opposite way
"""
def join(self, tree2, key, val):
if tree2.root.is_real_node() and self.root.is_real_node():
#checking which tree is higher, to see down which to search
if tree2.root.height < self.root.height:
higherTree = self
lowerTree = tree2
else:
higherTree = tree2
lowerTree = self
lowerRoot = lowerTree.root
higherRoot = higherTree.root
#create the connecting node and set it as the lowerTree's new root
joiningRoot = AVLNode(key,val)
joiningRoot.height = lowerRoot.height + 1
lowerRoot.parent = joiningRoot
node = higherRoot
#checking whether the lower tree is smaller or bigger than the bigger tree (key-wise), finding the leftmost\rightmost node
#of the same height as lowerRoot (or one under), accordingly.
#updating the sizes above to be accurate
#finally attaching the node found and lowerRoot as children in their right places.
if lowerRoot.key<higherRoot.key:
biggestMax = higherTree.max
while node.height>lowerRoot.height:
node = node.left
joiningRoot.right = node
joiningRoot.left = lowerRoot
else:
biggestMax = lowerTree.max
while node.height>lowerRoot.height:
node = node.right
joiningRoot.left = node
joiningRoot.right = lowerRoot
#replacing the node we found as a child in self, with joiningRoot
#and finding the other (and necessarily inner) child of the found node's parent
otherChild = self.getOtherSon(node)
if node != higherRoot:
self.replaceAsChild(node, joiningRoot)
node.parent = joiningRoot
#we encounter a problem only if joiningRoot's heigth and its new parent's height are the same
if joiningRoot.parent is not None and joiningRoot.height == joiningRoot.parent.height:
#if joiningRoot's height is k and otherchild's height is k-1
#then this is a problem we've already encounterd when insterting
if otherChild.height+1 == joiningRoot.height:
higherTree.promote(joiningRoot, 0)
#in any other case, if joiningRoot's height is k, then otherchild's height is k-2
#we'll need to rotate the tree, so that now joiningRoot is the original parent's parent
#and from here we've encountered this problem (if any) when inserting
else:
higherTree.rotation(joiningRoot.parent, joiningRoot)
higherTree.promote(joiningRoot, 0)
#updating self's attributes to be correct after joining the trees
if not joiningRoot.parent:
self.root = joiningRoot
elif higherTree != self:
self.root = tree2.root
self.tree_size += tree2.tree_size + 1
self.max = biggestMax
#if one of the trees is empty, insert the joining root to the non empty one
else:
if tree2.root.is_real_node() and not self.root.is_real_node():
self.root = tree2.root
self.tree_size = tree2.tree_size
self.max = tree2.max
self.insert(key, val)
"""splits the dictionary at a given node
creator: Nitzan Z.
@type node: AVLNode
@pre: node is in self
@param node: the node in the dictionary to be used for the split
@rtype: (AVLTree, AVLTree)
@returns: a tuple (left, right), where left is an AVLTree representing the keys in the
dictionary smaller than node.key, and right is an AVLTree representing the keys in the
dictionary larger than node.key.
"""
def split(self, node):
small_tree, large_tree = AVLTree(), AVLTree()
#if the split occurs at the root, create the small keys tree based on node.left,
#and the large keys tree based on node.right
if self.root.key == node.key:
if node.left.is_real_node():
small_tree = self.buildSubtree(node.left)
if node.right.is_real_node():
large_tree = self.buildSubtree(node.right)
self.nullify(node)
return (small_tree, large_tree)
#if the split occurs at the maximum node of the tree (which is not the root), delete the maximum node,
#update the maximum and return self as small keys tree and empty tree as large keys tree
elif self.max.key==node.key:
self.delete(node)
small_tree.root, small_tree.size, small_tree.max = self.root, self.tree_size, self.max
return (small_tree, large_tree)
else: #split occurs at a node who is not the root or the max
current = node
parent = node.parent
small_tree, large_tree = self.buildSubtree(node.left), self.buildSubtree(node.right)
self.nullify(node)
while parent is not None:
if current.key > parent.key: #if node should be the right child of its parent
higher_tree = self.buildSubtree(parent.left)
grandparent = parent.parent
#making sure the original parent is not pointing any other nodes
parent.parent, parent.left, parent.right= None, None, None
small_tree.join(higher_tree, parent.key, parent.value)
parent = grandparent
if parent is not None and current.key < parent.key:
current = parent.left
elif parent is not None:
current = parent.right
current = small_tree.root
elif current.key < parent.key: #if node should be the left child of its parent
higher_tree = self.buildSubtree(parent.right)
grandparent = parent.parent
#making sure the original parent is not pointing any other nodes
parent.parent, parent.left, parent.right= None, None, None
large_tree.join(higher_tree, parent.key, parent.value)
parent = grandparent
if parent is not None and current.key < parent.key:
current = parent.left
elif parent is not None:
current = parent.right
return small_tree, large_tree
"""returns an array representing dictionary
creator: Nitsan H.
@rtype: list
@returns: a sorted list according to key of touples (key, value) representing the data structure
"""
def avl_to_array(self):
#does a recursive in order walk on the tree, which updates an array
sorted_array = []
self.inOrderWalk(self.root, sorted_array)
return sorted_array
"""returns the node with the maximal key in the dictionary
creator: Nitsan H.
@rtype: AVLNode
@returns: the maximal node, None if the dictionary is empty
"""
def max_node(self):
#we keep an updated max field
return self.max
"""returns the number of items in dictionary
creator: Nitsan H.
@rtype: int
@returns: the number of items in dictionary
"""
def size(self):
#we keep an updated size field
return self.tree_size
"""returns the root of the tree representing the dictionary
creator: Nitsan H.
@rtype: AVLNode
@returns: the root, None if the dictionary is empty
"""
def get_root(self):
#root is initialized to be virtual
if not self.root.is_real_node():
return None
return self.root