SHARE
TWEET

Untitled

a guest Nov 18th, 2019 101 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Binary_Search_Tree:
  2.  
  3.     class __BST_Node:
  4.  
  5.         def __init__(self, value):
  6.             self.value = value
  7.             self.left=None
  8.             self.right=None
  9.             self.height=0
  10.  
  11.     def __init__(self):
  12.         self.__root = None
  13.  
  14.     def insert_element(self, value):
  15.         self.__root=self.__recursive_insert(value,self.__root)
  16.  
  17.     def __recursive_insert(self,value,node):
  18.         if node!=None:
  19.             if value<node.value:
  20.                 node.left=self.__recursive_insert(value,node.left)
  21.             elif value>node.value:
  22.                 node.right=self.__recursive_insert(value,node.right)
  23.             else:
  24.                 raise ValueError
  25.         else:
  26.             node=self.__BST_Node(value)
  27.         self.__update_node_height(node)
  28.         return node
  29.  
  30.     def remove_element(self, value):
  31.         self.__root=self.__recursive_remove(value,self.__root)
  32.  
  33.     def __recursive_remove(self,value,node):
  34.         if node!=None:
  35.             if value<node.value:
  36.                 node.left = self.__recursive_remove(value,node.left)
  37.                 self.__update_node_height(node)
  38.             elif value>node.value:
  39.                 node.right = self.__recursive_remove(value,node.right)
  40.                 self.__update_node_height(node)
  41.             else:
  42.                 if node.left==None:
  43.                     node=node.right
  44.                 elif node.right==None:
  45.                     node=node.left
  46.                 else:
  47.                     min_right_value=self.__recursive_find_right_subtree_min(node.right)
  48.                     self.__recursive_remove(min_right_value,node)
  49.                     node.value=min_right_value
  50.             return node
  51.         else:
  52.             raise ValueError
  53.  
  54.     def __recursive_find_right_subtree_min(self,node):
  55.         if node.left==None:
  56.             return_value=node.value
  57.             return return_value
  58.         else:
  59.             self.__recursive_find_right_subtree_min(node.right)
  60.  
  61.     def in_order(self):
  62.         if self.__root==None:
  63.             return "[ ]"
  64.         init_string=self.__recursive_inorder(self.__root)
  65.         init_string=init_string[:-2]
  66.         return_string= "[ "+init_string+" ]"
  67.         return return_string
  68.  
  69.     def __recursive_inorder(self,node):
  70.         if node==None:
  71.             return ""
  72.         elif node.left==None and node.right==None:
  73.             return str(node.value) +", "
  74.         else:
  75.             return self.__recursive_inorder(node.left)+str(node.value)+", "+self.__recursive_inorder(node.right)
  76.  
  77.     def pre_order(self):
  78.         if self.__root==None:
  79.             return "[ ]"
  80.         init_string=self.__recursive_preorder(self.__root)
  81.         init_string=init_string[:-2]
  82.         return_string= "[ "+init_string+" ]"
  83.         return return_string
  84.  
  85.     def __recursive_preorder(self,node):
  86.         if node==None:
  87.             return ""
  88.         elif node.left==None and node.right==None:
  89.             return str(node.value) + ", "
  90.         else:
  91.             return str(node.value)+", "+self.__recursive_preorder(node.left)+self.__recursive_preorder(node.right)
  92.  
  93.     def post_order(self):
  94.         if self.__root==None:
  95.             return "[ ]"
  96.         init_string=self.__recursive_postorder(self.__root)
  97.         init_string=init_string[1:]
  98.         return_string= "["+init_string+" ]"
  99.         return return_string
  100.  
  101.     def __recursive_postorder(self,node):
  102.         if node==None:
  103.             return ""
  104.         elif node.left==None and node.right==None:
  105.             return ", "+str(node.value)
  106.         else:
  107.             return self.__recursive_postorder(node.left)+self.__recursive_postorder(node.right)+", "+str(node.value)
  108.  
  109.     def get_height(self):
  110.         if self.__root==None:
  111.             return 0
  112.         return self.__root.height
  113.  
  114.     def __update_node_height(self,node):
  115.         if node.left!=None and node.right!=None:
  116.             if node.right.height>=node.left.height:
  117.                 node.height=node.right.height+1
  118.             else:
  119.                 node.height=node.left.height+1
  120.         elif node.left==None and node.right!=None:
  121.             node.height=node.right.height+1
  122.         elif node.right==None and node.left!=None:
  123.             node.height=node.left.height+1
  124.         else:
  125.             node.height=1
  126.  
  127.     def __str__(self):
  128.         return self.in_order()
  129.  
  130. # if __name__ == '__main__':
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top