import sys

class Node:
def __init__(self, key,color = 'black'):
   self.left=None
   self.right=None
   self.key = key
   self.parent = None
   self.color = color
   self.subtree_size=None

class RBTree:

class EmptyTree(Exception):
   def __init__(self, data=None):
         super().__init__(data)

class NotFound(Exception):
   def __init__(self, data=None):
         super().__init__(data)

def __init__(self):
   self.nil = Node('nil')
   self.nil.left = self.nil.right = self.nil.parent = self.nil
   self.root =self.nil
   self.nil.color = 'black'

   '''
   pseudocode from text book
   '''

def left_rotate(self,x):
   y = x.right
   x.right = y.left
   if y.left != self.nil:
         y.left.parent = x
   y.parent = x.parent
   if x.parent== self.nil:
         self.root = y
   elif x== x.parent.left:
         x.parent.left = y
   else:
         x.parent.right = y
   y.left = x
   x.parent = y

def right_rotate(self,y):
   x = y.left
   y.left = x.right
   if x.right != self.nil:
         x.right.parent = y
   x.parent = y.parent
   if y.parent ==self.nil:
         self.root = x
   elif y== y.parent.right:
         y.parent.right = x
   else:
         y.parent.left = x
   x.right = y
   y.parent = x

def RB_insert(self, z):
   y = self.nil
   x = self.root

   while x != self.nil:
         y = x
         if z.key < x.key:
            x = x.left
         else:
            x = x.right

   z.parent = y
   if y == self.nil:
         self.root = z

   elif z.key < y.key:
         y.left = z

   else:
         y.right = z

   z.left = z.right = self.nil
   z.color = 'red'
   self.RB_insert_fixup(z)

def RB_insert_fixup(self, z):
   while z.parent.color == 'red':
         if z.parent == z.parent.parent.left:
            y = z.parent.parent.right

            if y.color == "red":
               z.parent.color = "black"
               y.color = "black"
               z.parent.parent.color = "red"
               z = z.parent.parent

            else:
               if z == z.parent.right:
                     z = z.parent
                     self.left_rotate(z)
               z.parent.color = "black"
               z.parent.parent.color = "red"
               self.right_rotate(z.parent.parent)
         else:
            y = z.parent.parent.left
            if y.color == "red":
               z.parent.color = "black"
               y.color = "black"
               z.parent.parent.color = "red"
               z = z.parent.parent

            else:
               if z == z.parent.left:
                     z = z.parent
                     self.right_rotate(z)

               z.parent.color = "black"
               z.parent.parent.color = "red"
               self.left_rotate(z.parent.parent)

1 Applications Problem 1. Efficient Order Statistic In this probl...