Answer Happy

BST Operations As you already know, binary trees are ubiquitous in computer science and in programming. Same holds for binary search trees (BSTs), which enable us to apply them in a number of important practical settings.

Although being arguably one of the simplest and yet powerful data structures, binary search trees are susceptible to becoming unbalanced, after a number of insertion and deletion operations. To overcome this issue, computer scientists proposed various modifications and extensions to BSTs that made them self-balancing. The basic idea is that whenever an insertion or deletion operation is performed, the balance of the tree is checked and rebalancing is done if needed. Examples of self-balancing BSTs include red-black trees B-trees and B+-trees AVL trees . Clearly, the advantage of self-balancing trees is that they guarantee that insertion, deletion, lookup operations can be performed in logarithmic time (on the number of nodes in the tree), which is in clear contrast with the simple binary search trees. Moreover, since they are valid BSTs, they provide us with a simple and efficient way to traverse our data in order. In this set of tasks, we are going to implement self-balancing AVL trees by extending the functionality of class BinarySearch Tree of file bst.py partially provided to you in the scaffold. Although the implementation of self-balancing is to be done in the next section of the assignment, here you need to prepare the foundation for that. In the following tasks, you need to update the implementation of BSTs provided to you by adding the following missing functionality. Your concrete task is to update the class BinarySearchtree in file bst.py by adding implementations for the following methods: get_successor (self, current: TreeNode) -> TreeNode, which returns the successor of current (the smallest node greater than current) in the sub-tree. It should return None if there is no element greater in the subtree. get minimal (self, current: TreeNode) -> TreeNode, which returns the smallest node in the current sub-tree.

Self-balancing AVL Trees Invented in 1962 by Georgy Adelson-Velsky and Evgenii Landis, AVL trees serve as a simple extension of the standard binary search trees and represent one of the first examples of self-balancing BSTS.

AVL trees build on the concept of balance factor of a subtree defined by the root of the subtree: Balance Factor(root) = Height(root. right) – Height(root. left) A tree T is called balanced, if the balance factor of every node in the tree T is in {-1, 0, 1}. Hence, if for some of the nodes of T the balance factor is above these limits, the height of the corresponding left and right branches of the node-rooted subtree differ a lot thus breaking the worst-case logarithmic guarantees on the complexity of the main tree operations. AVL trees only add a way to rebalance the tree if it is necessary. Besides that, the trees perform exactly the same way as the standard binary search trees. Example of a balanced AVL tree with balance factors shown green: +1 F +1 G L +1 -1 0 N s X 0 0

Assume that after an insertion or deletion operation we end up having an unbalanced subtree with the root node having the balance factor from {-2, 2}. In this case, we can perform a rotation operation to return the balance factor of the subtree back to normal. Note that the balance factor cannot get larger than 2 or less than -2 if each insertion and deletion operation is followed by rebalancing. Below is an animated illustration of how the process works in practice (original GIF animation is taken from Wikipedia). Here the nodes in the tree are additionally labeled by the values of their balance factors. There are two basic types of rotation: left rotation right rotation . Your task is to update avl.py to add implementations for the following methods: left_rotate (self, current: AVLTreeNode) -> AVLTreeNode, which perform the left rotation of the current subtree, as shown below, and then updates the heights of all the modified nodes. Note that it returns the new root (r-child in this case) current r-child r-child left_rotate (current) current 1-tree C-tree r-tree l-tree C-tree r-tree

. right_rotate (self, current: AVLTreeNode) -> AVLTreeNode, which perform the right rotation of the current subtree, as shown below, and then updates the heights of all the modified nodes. Note that it returns the new root (I-child in this case) current l-child l-child current right_rotate (current) l-tree c-tree r-tree l-tree c-tree r-tree Putting it all together Once the above functionality of AVL trees is prepared, you can start making them self-balancing. The code for rebalancing is given, and should complete the rotations correctly. Now that you're done with subtree rebalancing, the final bit left is to apply it whenever the tree becomes unbalanced. When does this happen? Well, after you add or delete nodes. As a result, in class AVLTree redefine the following methods provided in the base class BinarySearchTree such that they apply subtree rebalancing after performing the corresponding operations: insert_aux (self, current: AVLTreeNode, key: K, item: I) -> AVLTreeNode delete_aux (self, current: AVLTreeNode, key: K) -> AVLTreeNode . Note that both methods should . update the height of the current node, and rebalance the subtree rooted by the current node.

Kth Largest Your task is to update bst.py, to add implementations for the following methods: kth_largest(self, k: int) -> AVLTreeNode Returns the kth largest node in the tree, using recursion. Here k=1 should give the largest node in the subtree. (Hint: You may need to add some extra code to other AVL operations, and create other attributes in order to achieve the intended complexity). Complexity Requirements: O(log(N)) Where N is the total number of nodes in the tree. A solution which does not achieve this complexity bound, but does achieve O(k), will achieve at most 75% of the marks for this task.