# Skewed Binary Search Trees

In * Proc. 14th Annual European Symposium on Algorithms*, volume 4168 of * Lecture Notes in Computer Science*, pages 708-719. Springer Verlag, Berlin, 2006.

## Abstract

It is well-known that to minimize the number of
comparisons a binary search tree should be perfectly balanced.
Previous work has shown that a dominating factor over the running time
for a search is the number of cache faults performed, and that an
appropriate memory layout of a binary search tree can reduce the
number of cache faults by several hundred percent.
Motivated by the fact that during a search branching to the left or
right at a node does not necessarily have the same cost, e.g.
because of branch prediction schemes, we in this paper study the
class of skewed binary search trees. For all nodes in a skewed
binary search tree the ratio between the size of the left subtree
and the size of the tree is a fixed constant (a ratio of 1/2
gives perfect balanced trees).
In this paper we present an experimental study of various memory
layouts of static skewed binary search trees, where each element in
the tree is accessed with a uniform probability.
Our results show that for many of the memory layouts we consider
skewed binary search trees can perform better than perfect balanced
search trees. The improvements in the running time are on the order
of 15%.

**Copyright notice**
© Springer-Verlag Berlin Heidelberg 2006. All rights reserved.

**Online version**

esa06skew.pdf (250 Kb)

**DOI**

10.1007/11841036_63

**Slides**
esa06skew.pdf (229 Kb)

**BIBT**_{E}X entry

@incollection{esa06skew,
author = "Gerth St{\o}lting Brodal and Gabriel Moruz",
booktitle = "Proc. 14th Annual European Symposium on Algorithms",
doi = "10.1007/11841036_63",
isbn = "978-3-540-38875-3",
pages = "708-719",
publisher = "Springer {V}erlag, Berlin",
series = "Lecture Notes in Computer Science",
title = "Skewed Binary Search Trees",
volume = "4168",
year = "2006"
}