Binary Search Tree and Its Applications: A Survey

Abstract

Binary search trees used as a data structure for rapid access to stored data. Arrays, vectors and linked lists data structures are limited by the trade-off between ability to perform fast search and resize easily. Complete and nearly complete binary search trees are of particularly significance. New version of insert-delete pair maintains random binary tree in a manner where all grandparents in tree always have both sub-trees full. In worst case binary search tree reduce to a linear link list, so reducing such search to sequential. In particular, we obtain a BST data structure that is O(log log n) competitive, satisfies the working set bound, dynamic ?nger bound and unified bound with an additive O(log log n) factor, and performs each access in worst-case O(log n) time.