- Bst Operations As You Already Know Binary Trees Are Ubiquitous In Computer Science And In Programming Same Holds For B 1 (93.78 KiB) Viewed 30 times
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.