#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