Frequently Accessed Binary Search Tree (Fast)

Abstract

In recent days, many search tree based data structures, such as Splay Trees, AVL trees and red-black trees aid in efficient admittance to the stored items by keeping the tree in a balanced state. The art of choosing the right kind of tree can impact greatly the performance of the application. In this paper, we propose a data structure named FAST (Frequently Accessed Binary Search Tree), a variant of Splay Tree performing searching and ranking in O(log n) average time. The tree is basically a kind of Binary Search Tree (BST) with splay and max-heap property. Nodes in the tree will be arranged from root to bottom according to their frequency of accesses. The proposed tree is useful in applications involving more searching and ranking. The experiments revealed the optimal access time can be guaranteed for the applications that need to access keep most referred items nearer to the root.

Keywords: Algorithm, AVL Tree, Binary Search Tree, Heap, Non-linear Tree, Splay Tree.