Write a C++ program that implements the following size balancing (not height balanced) binary search tree where the node knows the number of left and right nodes in each subtree in order to achieve runtime.
CODE BASE:
https://ybin.me/p/b8539a35dedd4d59#CCjscmXaEecNhSqbof6/EZPGSYEW1lUpJSboZNpmNc4=
In this part of the assignment you will implement what we will call the "size-balanced: strategy described below As we know, "vanilla" BSTs do not in general guarantee logarithmic height and as a result, basic operations like lookup, insertion and deletion are linear time in the worst case There are ways to fix this weakness - e.g., AVL trees and Red-Black trees. We will not be doing either of those; instead, you will implement the "size-balanced" strategy described below Big picture: size-balanced trees are not quite as "strong" as AVL or Red-Black trees in the sense that insert and delete will have amortized_logarithmic runtime instead of (instead of guaranteed logarithmic runtime for individual_inserts/deletes as with AVL and Red-Black trees). (The amortized property is formalized a bit below.) On the other hand, size-balanced trees are probably easier to implement than AVL or Red-Black trees. Furthermore, as far as I know, a simple google search will not find complete C++ implementations of size-balanced trees) The "size-balanced" property: Definition (size-balance property for a node) Consider a node v in a binary tree with n, nodes in its left subtree and n nodes in its right subtree; we say that v is size-balanced if and only if: max(ni, nR 2 x min(n, np) + 1 (so roughly, an imbalance of up to - is allowed) Definition: (size-balance property for a tree We say that a binary tree t is size-balanced if and only if all nodes v in t are size-balanced In this part of the assignment you will implement what we will call the "size-balanced: strategy described below As we know, "vanilla" BSTs do not in general guarantee logarithmic height and as a result, basic operations like lookup, insertion and deletion are linear time in the worst case There are ways to fix this weakness - e.g., AVL trees and Red-Black trees. We will not be doing either of those; instead, you will implement the "size-balanced" strategy described below Big picture: size-balanced trees are not quite as "strong" as AVL or Red-Black trees in the sense that insert and delete will have amortized_logarithmic runtime instead of (instead of guaranteed logarithmic runtime for individual_inserts/deletes as with AVL and Red-Black trees). (The amortized property is formalized a bit below.) On the other hand, size-balanced trees are probably easier to implement than AVL or Red-Black trees. Furthermore, as far as I know, a simple google search will not find complete C++ implementations of size-balanced trees) The "size-balanced" property: Definition (size-balance property for a node) Consider a node v in a binary tree with n, nodes in its left subtree and n nodes in its right subtree; we say that v is size-balanced if and only if: max(ni, nR 2 x min(n, np) + 1 (so roughly, an imbalance of up to - is allowed) Definition: (size-balance property for a tree We say that a binary tree t is size-balanced if and only if all nodes v in t are size-balanced
