Question

attention!!!!!!! I need python method!!!!!!!!!

the part which need to edit is below: i need python one!!!!!!!!!

the part below is interface for the range search tree which don’t need to modify it.

Week 3: Working with a BST TODO: Implement a Binary Search Tree (Class Name: RangesizeTree) Choose one language fromJava or Python. Iin both languages,there is an empty main function in the Range Size Tree file. The main function is not tested, however, it is provided for you to run your own testing. NOTE: Please uncomment the language you are using in the LANGUAGE file. The Range Size Tree supports this functionality put (k) -put the key K into the tree (duplicate keys are allowed). remove (k) remove the lowest occurrence of the key K get(k) - return the nodes that have the key K size (a, b count the number of nodes between a and b. o NOTE: a and b may not be in order; may not be a key etc o If a lowest tree node, you should still count from this. o Similarly if b > highest tree node, still count between this. Important notes about implementation!!! Descendants to the LEFT are LESS THAN OR EQUAL TO ( 7 param a: A key to search between :param b: A key to search between. return: Number of nodes between the two keys pass a +Node java ф range-size,tree.py · 쇼 RangesizeTreejava LANGUA.GE ф node.py 2 Simple Binary Tree Node to be used in the Binary Tree. 6 class Node 8 Simple node in the binary tree 10 11 def init.. (self, key) 12 13 14 15 16 17 18 def get,key (self) 19 20 21 self..key key self. subtree size 1 self"-left = None self..right None self._parent None Returns the value of the node's key return: the node key return self._key 23 24 25 a+Node java ф range-size-tree.py 4. RangeSizeTree.java LANGUAGE node.py 34 def increment subtree (self): 35 36 37 38 39 40 def decrement subtree (self): 41 42 43 Increments the size of the subtree self.-subtree-size ++ Decrement the size of the subtree if self._subtree size1: 45 46 47 48 49 50 def getleft (self) 51 52 53 54 return self. subtree size1 Get the left child :return: Left child node return self._left 56 + Node.java ф range-size-tree.py RangesizeTree.java LANGUAGE ф node.py 57 58 def get_right (self): 59 60 61 62 63 64 65 66 def get parent (self): 67 68 69 70 71 72 73 Get the right child return: Right child node return self..right Get the parent of the node return: The parent return self._parent 74 def set left(self, ): 75 76 Set the left child of the node. self..left 1 78 79 86 80 81 def set_right (self, r): 82 83 84 85 86 87 88 def set parent (self, p): 89 90 91 92 93 Set the right child of the node. self..right r Set the parent. self._parent p

Answer 1

class Node:

    def __init__(self):

        self.left = None

        self.right = None

        self.val = 0

  

# A utility function to insert a new node with the given key

def put(self,key):

    if self is None:

        self = key

    else:

        if self.val < key.val:

            if self.right is None:

                self.right = key

            else:

                insert(self.right, key)

        else:

            if self.left is None:

                self.left = key

            else:

                insert(self.left, key)

# A utility function to search a given key in BST

def get(self,key):

      

    # Base Cases: self is null or key is present at self

    if self is None or self.val == key:

        return self

  

    # Key is greater than self's key

    if self.val < key:

        return search(self.right,key)

    

    # Key is smaller than self's key

    return search(self.left,key)

# A utility function to remove a given key in BST

def remove(self, key):

  

    # Base Case

    if self is None:

        return self

  

    # If the key to be deleted is smaller than the self's

    # key then it lies in left subtree

    if key < self.key:

        self.left = deleteKey(self.left, key)

  

    # If the kye to be delete is greater than the self's key

    # then it lies in right subtree

    elif(key > self.key):

        self.right = deleteKey(self.right, key)

  

    # If key is same as self's key, then this is the key

    # to be deleted

    else:

          

        # Key with only one child or no child

        if self.left is None :

            temp = self.right

            self = None

            return temp

              

        elif self.right is None :

            temp = self.left

            self = None

            return temp

  

        # Key with two children: Get the inorder successor

        # (smallest in the right subtree)

        temp = minValueKey(self.right)

  

        # Copy the inorder successor's content to this key

        self.key = temp.key

  

        # Delete the inorder successor

        self.right = deleteKey(self.right , temp.key)

return self

# The function prints all the keys in the given range

def range_size(self, a, b):

      

    # Base Case

    if self is None:

        return

  

    # Since the desired o/p is sorted, recurse for left

    # subtree first. If self.data is greater than a, then

    # only we can get o/p keys in left subtree

    if a < self.data :

        Print(self.left, a, b)

  

    # If self's data lies in range, then prints self's data

    if a <= self.data and b >= self.data:

        print self.data,

  

    # If self.data is smaller than b, then only we can get

    # o/p keys in right subtree

    if b > self.data:

        Print(self.right, a, b)