# Binary Search Trees:

# A tree is an instance (object) of one of two classes, Nil or Node

class Nil:
    def __init__(self):
      pass  # do nothing
    # init
    def empty(self):
        return True
    def getheight(self):
        return 0
    def search(self,x): # search for x
        return False
    def insert(self,x):
        return Node(x,self,self)  # reuse self
    def delete(self,x):
        return self
    def print(self):
        pass
#Nil class for empty node

class Node:
    def __init__(self,x,lf,rt):
       self.info = x
       self.left = lf # pointer to left subtree
       self.right = rt # pointer to right subtree
       self.setheight()
    # constructor
    
    def setheight(self):
       hl = self.left.getheight()
       hr = self.right.getheight()
       self.height = max(hl,hr)+1
       return self.height
    # sets and returns height

    def getheight(self):
       return self.height

    def empty(self):
        return False

    def print(self):  # inorder print
        self.left.print()
        print(self.info,end=" ")
        self.right.print()
    
    def search(self,x):
       if x==self.info: return True
       elif x<self.info: return self.left.search(x)
       else: return self.right.search(x)
    # search

    def insert(self,x):  # returns new tree inserted, no duplicates allowed
       if x<self.info: self.left=self.left.insert(x)
       elif x>self.info: self.right=self.right.insert(x)
       #else: do not insert duplicates
       self.balance()
       return self  # self doesn't change, children may have changed
    #insert

    def delete(self,x):
       if x<self.info: self.left=self.left.delete(x)  # find it first
       elif x>self.info: self.right=self.right.delete(x)
       else:  # x==self.info, found node to delete
           if self.left.empty(): # special case
               return self.right
           else:
               self.left = self.left.delmax(self)
       self.balance()
       return self
    #delete

    # following methods only defined for Node, not for Nil:
    def delmax(self,modself):
       if self.right.empty():  # found largest node
           modself.info = self.info # transter info to upper node
           return self.left
       else:
           self.right=self.right.delmax(modself)
           self.balance()
           return self
    #delmax

    def LL(self):
      if self.left.empty(): return
      x = self.info
      y = self.left.info
      ll = self.left.left
      lr = self.left.right
      r = self.right
      self.info = y
      self.right = self.left  # reuse mem for node
      self.right.info = x
      self.right.left = lr
      self.right.right = r
      self.left = ll
      self.right.setheight()
      self.setheight()
    #LL

    def RR(self):
      if self.right.empty(): return
      x = self.info
      y = self.right.info
      l = self.left
      rl = self.right.left
      rr = self.right.right
      self.info = y
      self.left = self.right
      self.left.info = x
      self.left.left = l
      self.left.right = rl
      self.right = rr
      self.left.setheight()
      self.setheight()
    # RR

    def balance(self):
      self.setheight()
      hl = self.left.getheight()
      hr = self.right.getheight()
      if hl>hr+1:  # left side more than 1 level higher, LL or LR
         hll = self.left.left.getheight()
         hlr = self.left.right.getheight()
         if hlr>hll: self.left.RR()
         self.LL()
      elif hr>hl+1: #RR or RL
         hrl = self.right.left.getheight()
         hrr = self.right.right.getheight()
         if hrl>hrr: self.right.LL()
         self.RR()
      #if -elif
    #balance
# Node class for info nodes
    
#### tests
"""
tree = Nil()  # start with empty node
tree = tree.insert(8)
for x in [8,14,12,4,2,6,1,16,2,5]: tree=tree.insert(x)
print("height after insert:",tree.getheight())
print("search 12:",tree.search(1))
print("search 3:",tree.search(3))
tree=tree.delete(8);  tree=tree.delete(2);
print("search 8 after delete:",tree.search(8))
print("height after delete:",tree.getheight())
"""

n = 500000
tree = Nil()
for x in range(0,n): tree = tree.insert(x)
for x in range(0,n//2): tree = tree.delete(x*2)
print("height after delete:",tree.getheight())