A Study of Balanced Search Trees: Brainstorming a New Balanced Search Tree

This project investigates four different balanced search trees for their advantages and
disadvantages, thus ultimately their efficiency. Runtime and memory space management are two main aspects under the study. Statistical analysis is provided to distinguish subtle
difference if there is any. A new balanced search tree is suggested and compared with the
four balanced search trees. Balanced search trees are implemented in C++ extensively using pointers and structs.

Abstract
Results with Graphs
Anthony Kim, 2005
The order of data input is important to the structure of a binary search tree (or general search tree). In a optimal binary tree, the data are input so that insertion occurs just
right which makes the tree “balanced,” the size of left subtree is approximately equal to the size of right subtree at each node in the tree. In an optimal binary tree, the insertion,
deletion, and search function occur in O(log N) with N as the number of data in the tree. This follows from that whenever data comparison occurs and subsequent traversal
(to the left or to the right) the number of possible subset divides in half at each turn. However that's only when the input is nicely ordered and the search tree is balanced. It's
also possible that the data are input so that only right nodes are added. (Root -> right -> right -> right ...) It's obvious that the search tree now looks like just a linear array. And it is.
And this give O(N) to do insertion, deletion and search operation. This is not efficient. Thus balanced search trees are developed to perform its functions efficiently regardless
of data input. 

Background Procedure & methodology
Four balanced search trees are implemented in C++ in addition to my balanced search tree. A large test data of numbers is put into the balanced search tree and the efficiency of
insert, delete, search functions is investigated. The key idea of behind the procedure is
benchmarking.