A Textbook of Data Structures and Algorithms, Volume 3

15k-d Trees and Treaps

15.1. Introduction

k-d trees and Treaps are binary trees that are built on the principle of binary search trees, which was elaborated in Chapter 10 (Volume 2). While k-d trees are adept in handling multi-dimensional keys, Treaps are randomized binary search trees and are good at handling data sets in which each of the data elements has priorities attached to them.

The structure, operations and applications of the two data structures are detailed in the ensuing sections.

15.2.k-d trees: structure and operations

k-dimensional trees or k-d trees invented by Jon Louis Bentley in 1975 (Bentley 1975) are multi-dimensional binary search trees, which can undertake query-based searches such as range search, nearest-neighbor search and fast retrieval of a key, efficiently.

k-d trees handle multi-dimensional keys, K_i = (a_i,1, a_i,2, …a_i,k), i = 1, 2, … N (dimensionality k), organize them in k-dimensional space as points and partition them into non-overlapping regions. Therefore, the regions partitioning the k-dimensional space hold disjoint subsets of the set of keys K_i, i = 1, 2, …N. On account of this property, k-d trees are termed as space-partitioning data structures. It is this space-partitioning principle that is responsible for the efficient behavior of k-d trees. However, despite handling k-dimensional keys using the space-partitioning principle, k-d trees in structure, look only like binary trees.

So, who partitions them in k-dimensional space?

The non-leaf ...