Question

write python code to Implement the find-k-end-value in AVL trees algorithm. use trees k least value algorithm, including adding the "size" property of each node in the tree.

1. Maintain the "size" property during insertions, including rotations
2. Create the find_k_end (k) method that finds the k-end minimum value

Answer 1

# AVL Binary search tree implementation in Python

# Author: AlgorithmTutor

# data structure that represents a node in the tree

import sys

class Node:

def __init__(self, data):

self.data = data

self.parent = None

self.left = None

self.right = None

self.bf = 0

class AVLTree:

def __init__(self):

self.root = None

def __printHelper(self, currPtr, indent, last):

# print the tree structure on the screen

if currPtr != None:

sys.stdout.write(indent)

if last:

sys.stdout.write("R----")

indent += " "

else:

sys.stdout.write("L----")

indent += "| "

print currPtr.data

self.__printHelper(currPtr.left, indent, False)

self.__printHelper(currPtr.right, indent, True)

def __searchTreeHelper(self, node, key):

if node == None or key == node.data:

return node

if key < node.data:

return self.__searchTreeHelper(node.left, key)

return self.__searchTreeHelper(node.right, key)

def __deleteNodeHelper(self, node, key):

# search the key

if node == None:

return node

elif key < node.data:

node.left = self.__deleteNodeHelper(node.left, key)

elif key > node.data:

node.right = self.__deleteNodeHelper(node.right, key)

else:

# the key has been found, now delete it

# case 1: node is a leaf node

if node.left == None and node.right == None:

node = None

# case 2: node has only one child

elif node.left == None:

temp = node

node = node.right

elif node.right == None:

temp = node

node = node.left

# case 3: has both children

else:

temp = minimum(node.right)

node.data = temp.data

node.right = self.__deleteNodeHelper(node.right, temp.data)

# Write the update balance logic here

# YOUR CODE HERE

return node

# update the balance factor the node

def __updateBalance(self, node):

if node.bf < -1 or node.bf > 1:

self.__rebalance(node)

return;

if node.parent != None:

if node == node.parent.left:

node.parent.bf -= 1

if node == node.parent.right:

node.parent.bf += 1

if node.parent.bf != 0:

self.__updateBalance(node.parent)

# rebalance the tree

def __rebalance(self, node):

if node.bf > 0:

if node.right.bf < 0:

self.rightRotate(node.right)

self.leftRotate(node)

else:

self.leftRotate(node)

elif node.bf < 0:

if node.left.bf > 0:

self.leftRotate(node.left)

self.rightRotate(node)

else:

rightRotate(node)

def __preOrderHelper(self, node):

if node != None:

sys.stdout.write(node.data + " ")

self.__preOrderHelper(node.left)

self.__preOrderHelper(node.right)

def __inOrderHelper(self, node):

if node != None:

self.__inOrderHelper(node.left)

sys.stdout.write(node.data + " ")

self.__inOrderHelper(node.right)

def __postOrderHelper(self, node):

if node != None:

self.__postOrderHelper(node.left)

self.__postOrderHelper(node.right)

std.out.write(node.data + " ")

# Pre-Order traversal

# Node->Left Subtree->Right Subtree

def preorder(self):

self.__preOrderHelper(self.root)

# In-Order traversal

# Left Subtree -> Node -> Right Subtree

def __inorder(self):

self.__inOrderHelper(self.root)

# Post-Order traversal

# Left Subtree -> Right Subtree -> Node

def __postorder(self):

self.__postOrderHelper(self.root)

# search the tree for the key k

# and return the corresponding node

def searchTree(self, k):

return self.__searchTreeHelper(self.root, k)

# find the node with the minimum key

def minimum(self, node):

while node.left != None:

node = node.left

return node

# find the node with the maximum key

def maximum(self, node):

while node.right != None:

node = node.right

return node

# find the successor of a given node

def successor(self, x):

# if the right subtree is not null,

# the successor is the leftmost node in the

# right subtree

if x.right != None:

return self.minimum(x.right)

# else it is the lowest ancestor of x whose

# left child is also an ancestor of x.

y = x.parent

while y != None and x == y.right:

x = y

y = y.parent

return y

# find the predecessor of a given node

def predecessor(self, x):

# if the left subtree is not null,

# the predecessor is the rightmost node in the

# left subtree

if x.left != None:

return self.maximum(x.left)

y = x.parent

while y != None and x == y.left:

x = y

y = y.parent

return y

# rotate left at node x

def leftRotate(self, x):

y = x.right

x.right = y.left

if y.left != None:

y.left.parent = x

y.parent = x.parent;

if x.parent == None:

self.root = y

elif x == x.parent.left:

x.parent.left = y

else:

x.parent.right = y

y.left = x

x.parent = y

# update the balance factor

x.bf = x.bf - 1 - max(0, y.bf)

y.bf = y.bf - 1 + min(0, x.bf)

# rotate right at node x

def rightRotate(self, x):

y = x.left

x.left = y.right;

if y.right != None:

y.right.parent = x

  

y.parent = x.parent;

if x.parent == None:

self.root = y

elif x == x.parent.right:

x.parent.right = y

else:

x.parent.left = y

  

y.right = x

x.parent = y

# update the balance factor

x.bf = x.bf + 1 - min(0, y.bf)

y.bf = y.bf + 1 + max(0, x.bf)

# insert the key to the tree in its appropriate position

def insert(self, key):

# PART 1: Ordinary BST insert

node = Node(key)

y = None

x = self.root

while x != None:

y = x

if node.data < x.data:

x = x.left

else:

x = x.right

# y is parent of x

node.parent = y

if y == None:

self.root = node

elif node.data < y.data:

y.left = node

else:

y.right = node

# PART 2: re-balance the node if necessary

self.__updateBalance(node)

# delete the node from the tree

def deleteNode(self, data):

return self.__deleteNodeHelper(self.root, data)

# print the tree structure on the screen

def prettyPrint(self):

self.__printHelper(self.root, "", True)

if __name__ == '__main__':

bst = AVLTree()

bst.insert(1)

bst.insert(2)

bst.insert(3)

bst.insert(4)

bst.insert(5)

bst.insert(6)

bst.insert(7)

bst.insert(8)

bst.prettyPrint()