All Courses
AI Career Planner
1:1 Coaching/Mentoring
Job Board
SQL
HTML/CSS/JS
Coding
Settings
LogoutA self-balancing Binary Search Tree is the Splay tree (BST). The basic goal of the splay tree is to get the most recently used item to the top of the tree. If the previously searched object is accessed again, it will be available in O (1) time. The concept is to take advantage of the locality of reference (In a typical application: 80 percent of the access are to 20 percent of the items).
Consider a scenario in which we have millions or billions of keys, but only a small percentage of them are used often, as is the case in many real applications.
On average, all splay tree operations take O(log n) time, where n is the number of tree elements. In the worst-case scenario, each one operation can take Theta(n) time.