Two-Way Comparison Search Trees AGeneralization of Binary Search Trees and Split Trees Abstract

Ageneralization of binary search trees and binary split trees is developed that takes advantage of two-way key comparisons — the two-way comparison tree. The two-way comparison tree is shown to have little use for dynamic situations, but to be an improvement over the optimal binary search tree and the optimal binary split tree for static data sets. An O(n) time and space algorithm is presented for construction of the optimal two-way comparison tree when access probabilities are equal; the construction of the optimal tree for more general probabilities is shown to be more difficult and unlikely to cost less than O(n 4). 1