On size balanced binary search trees

Abstract

History independent data structures are useful when security and privacy are of primary concern. Even if an adversary gets copy of the data structure, he cannot obtain any additional information beyond its content. Important property of history independent data structure is that it has no trace visible in its memory layout about the history of operations performed on it. Buchbinder and Petrank [7] in their paper provided lower bounds for obtaining the Strong History Independence for large class of data structures. They also proposed complementary upper bounds for comparison based models and gave an implementation of Weakly History Independent Heap Abstract data structure. In the paper “A Short Note on Perfectly Balance Binary Tree” by A. P. Korah and M. R. Kaimal [14] an algorithm for insertion of a node in a perfectly balanced binary search tree is presented in which successive data displacement is performed in an inorder fashion to keep the binary tree size balanced. This algorithm has worst case performance linear with the number of nodes in the tree. Binary search tree is a very useful data structure and is used in many applications such as dictionary, priority queue and supports many operations, such as SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, and DELETE. Balanced binary trees such as height balanced binary trees, weight balanced binary trees, etc. support these operations in O (lg n) time in worst-case. Size balanced binary search tree is a balanced binary tree in which number of nodes in one subtree cannot exceed by one than the number of nodes in the other sub tree at every node in the tree. In this thesis, Characterizing Size Balanced Binary Search Tree (SB-BST), I determine the number of Size Balanced Binary Search Trees of a given size. I also provide algorithms to insert into and to delete a node from an SB-BST. Delete operation is followed by Maintain in order to maintain the size balance of Binary Search Tree. These operations require O (n) worst-case run time.