Premium
Untangling the balancing and searching of balanced binary search trees
Author(s) -
Austern Matthew H.,
Stroustrup Bjarne,
Thorup Mikkel,
Wilkinson John
Publication year - 2003
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.564
Subject(s) - binary search tree , computer science , ternary search tree , optimal binary search tree , binary search algorithm , self balancing binary search tree , correctness , binary tree , tree (set theory) , key (lock) , search tree , implementation , search algorithm , theoretical computer science , weight balanced tree , binary number , tree traversal , beam search , algorithm , interval tree , mathematics , programming language , combinatorics , arithmetic , operating system
A balanced binary search tree can be characterized by two orthogonal issues: its search strategy and its balancing strategy. In this paper, we show how to decouple search and balancing strategies so that they can be expressed independently of each other, communicating only by basic operations such as rotations. Different balancing strategies, such as red–black trees and splay trees, and different search applications, such as key search and rank search, can be combined arbitrarily. As a new result, we show how optimal string search can be expressed as a search application on any balanced binary tree. We implement our framework in C++, with the heavy use of templates and inlining. It keeps balancing and searching separate, while still delivering a performance that compares favorably to widely used binary tree implementations. Common services, such as correctness checks and timing measurements, do not have to be rewritten for each tree implementation. The common framework simplifies experimentation with trees and search algorithms; as a demonstration, we present some simple comparisons of red–black trees, splay trees and treaps. Copyright © 2003 John Wiley & Sons, Ltd.