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

## Question

Show transcribed text

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

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)...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

\$60.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

### Find A Tutor

View available Python Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.