✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-216

Order Statistic Trees

An Order Statistic Tree is an augmented search tree that supports finding the element at a particular sorted position and determining the rank of an element efficiently.

Explanation

Overview

An Order Statistic Tree is a balanced binary search tree that stores additional information, usually the size of each subtree. This information allows the structure to answer order-related queries, such as finding the kth smallest element or calculating how many elements are smaller than a given value.

How it works

Each node stores a key and the size of its subtree.; The left subtree contains keys smaller than the current node in a standard binary search tree.; The size of the left subtree determines the current node's sorted position relative to its subtree.; A kth-smallest query compares k with the size of the left subtree.; The algorithm moves left, returns the current node, or moves right with an adjusted rank.; After insertion or deletion, subtree sizes must be updated.

Key concepts

Balanced binary search trees; Subtree sizes; Order statistics; Rank queries; Kth-smallest selection; Tree augmentation

Time complexity

operation: Select kth element; complexity: O(log n) in a balanced tree; operation: Rank query; complexity: O(log n) in a balanced tree; operation: Insertion; complexity: O(log n) in a balanced tree; operation: Deletion; complexity: O(log n) in a balanced tree

Space complexity

O(n), with additional subtree-size information stored in each node.

Example

sortedElements: 10; 20; query: Find the 4th smallest element.; result: 40; rankQuery: Find the number of elements smaller than 50.; rankResult: 4

Applications

Finding kth smallest or largest elements; Dynamic ranking systems; Median maintenance; Order-based database queries; Counting values smaller than a given key; Competitive programming

Example or application

Sorted Elements

  • 10

  • 20

  • 30

  • 40

  • 50

  • 60

  • 70

Query

Find the 4th smallest element.

Result

40

Rank Query

Find the number of elements smaller than 50.

Rank Result

4

Definition

An Order Statistic Tree is a balanced binary search tree that stores additional information, usually the size of each subtree. This information allows the structure to answer order-related queries, such as finding the kth smallest element or calculating how many elements are smaller than a given value.

How It Works

  • Each node stores a key and the size of its subtree.

  • The left subtree contains keys smaller than the current node in a standard binary search tree.

  • The size of the left subtree determines the current node's sorted position relative to its subtree.

  • A kth-smallest query compares k with the size of the left subtree.

  • The algorithm moves left, returns the current node, or moves right with an adjusted rank.

  • After insertion or deletion, subtree sizes must be updated.

Supported Operations

OperationDescription

Select(k)

Returns the kth smallest element.

Rank(x)

Returns the number of stored elements smaller than x, depending on the chosen rank convention.

Insert(x)

Inserts an element while maintaining search-tree order and subtree sizes.

Delete(x)

Removes an element and updates the relevant subtree sizes.

Implementation

Description

An order-statistic tree can be implemented by augmenting a balanced search tree, such as a Red-Black Tree, with subtree-size information.

Pseudocode

  • function select(node, k):

  • leftSize = size(node.left)

  • if k == leftSize + 1:

  • return node

  • else if k <= leftSize:

  • return select(node.left, k)

  • else:

  • return select(node.right, k - leftSize - 1)

  • function size(node):

  • if node is null:

  • return 0

  • return node.subtreeSize

Time Complexity

OperationComplexity

Select kth element

O(log n) in a balanced tree

Rank query

O(log n) in a balanced tree

Insertion

O(log n) in a balanced tree

Deletion

O(log n) in a balanced tree

Space Complexity

O(n), with additional subtree-size information stored in each node.

Key Concepts

  • Balanced binary search trees

  • Subtree sizes

  • Order statistics

  • Rank queries

  • Kth-smallest selection

  • Tree augmentation

Advantages

  • Supports dynamic rank and selection queries.

  • Maintains sorted information without repeatedly sorting the entire collection.

  • Supports insertions and deletions efficiently when balanced.

  • Can be extended with other subtree aggregates.

Limitations

  • Requires a balanced search tree to guarantee logarithmic performance.

  • Subtree metadata must be maintained correctly after rotations and updates.

  • Duplicate values require a consistent representation and ranking convention.

  • Implementation is more complex than a standard binary search tree.

Applications

  • Finding kth smallest or largest elements

  • Dynamic ranking systems

  • Median maintenance

  • Order-based database queries

  • Counting values smaller than a given key

  • Competitive programming

Related Topics

  • Binary Search Trees

  • Red-Black Trees

  • AVL Trees

  • Balanced Search Trees

  • Order Statistics

Practice Questions

QuestionAnswer

What extra information does an Order Statistic Tree commonly store?

The size of each node's subtree.

What does Select(k) return?

The kth smallest element in the stored collection.

What is the typical time complexity of a selection query in a balanced Order Statistic Tree?

O(log n).

Learning Objectives

  • Explain the central idea and purpose of order statistic trees.

  • Identify the assumptions, inputs, and conditions relevant to order statistic trees.

  • Evaluate an application of order statistic trees for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Advanced Data Structures

Suggest a correction or source · More in Algorithms & Data Structures