Question 1

Do some Internet research to find out which kind of self-balancing binary search tree (e.g. AA tree, AVL tree, etc.) is used in the C++ standard template library (STL) map and set . As far as you can tell, why is that kind of tree used over the alternatives listed in Section 4.7.

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

4.7 Self-Balancing Binary Search Tree A binary search tree is a data structure that stores entries (as described in Section 4.6) in a kind of sorted order. A binary search tree is comprised of nodes; each node contains one entry, a pointer to a left subtree, and a pointer to a right subtree. Each subtree pointer may be either a pointer to another node; or an empty subtree called a leaf which is represented in code by None. The topmost node is called the root, and the length of the longest path from the root to a leaf is called the height of a tree A binary search tree enforces the binary search tree invariant which dictates that, for any node p 84 containing entry key x, every key w in the left subtree of p obeys w x, we continue searching in the node's right subtree. If we ever reach a leaf (None) in this process, then we can safely conclude that k does not exist in the tree Inserting a new entry involves searching for that entry according to the process above, then replacing the leaf node that is reached with a new node. Removing an entry involves searching for the node containing that entry, and removing that node. If the node has any children, its removal may leave a "hole" in the tree, which must be "patched" by finding a different node to take its place. The details of this process is beyond the scope of this text, but suffice it to say that a patch node may always be found in one of the removed node's subtrees Each of the search, insertion, and removal algorithms involves traversing the tree from the root to a leaf, and spending O(1) time at each node along the way. So if a binary search tree has height h, than these operations take O(h) time each. Unfortunately it is possible for a binary search tree to become extremely unbalanced. When every right pointer is a leaf, so that every node is a left child (except the root), the tree has height h-n. A tree with all right children has the same height h -n, and more generally, any tree with the property that each node has at least one leaf child, has height h- n. In any of these degenerate cases the search, insertion, and removal operations take O(n) worst-case time 4.7 Self-Balancing Binary Search Tree A binary search tree is a data structure that stores entries (as described in Section 4.6) in a kind of sorted order. A binary search tree is comprised of nodes; each node contains one entry, a pointer to a left subtree, and a pointer to a right subtree. Each subtree pointer may be either a pointer to another node; or an empty subtree called a leaf which is represented in code by None. The topmost node is called the root, and the length of the longest path from the root to a leaf is called the height of a tree A binary search tree enforces the binary search tree invariant which dictates that, for any node p 84 containing entry key x, every key w in the left subtree of p obeys w x, we continue searching in the node's right subtree. If we ever reach a leaf (None) in this process, then we can safely conclude that k does not exist in the tree Inserting a new entry involves searching for that entry according to the process above, then replacing the leaf node that is reached with a new node. Removing an entry involves searching for the node containing that entry, and removing that node. If the node has any children, its removal may leave a "hole" in the tree, which must be "patched" by finding a different node to take its place. The details of this process is beyond the scope of this text, but suffice it to say that a patch node may always be found in one of the removed node's subtrees Each of the search, insertion, and removal algorithms involves traversing the tree from the root to a leaf, and spending O(1) time at each node along the way. So if a binary search tree has height h, than these operations take O(h) time each. Unfortunately it is possible for a binary search tree to become extremely unbalanced. When every right pointer is a leaf, so that every node is a left child (except the root), the tree has height h-n. A tree with all right children has the same height h -n, and more generally, any tree with the property that each node has at least one leaf child, has height h- n. In any of these degenerate cases the search, insertion, and removal operations take O(n) worst-case time