Balanced Search Trees

These flashcards cover key concepts of balanced search trees, including 2–3 trees, red-black BSTs, and B-trees, along with their properties and functionalities.

What is a characteristic of a 2–3 tree?

A 2–3 tree allows 1 or 2 keys per node, maintaining perfect balance.

What happens during the insertion of a new key into a 3-node in a 2–3 tree?

A new key is added, creating a temporary 4-node, which may require splitting.

What is the maximum height of a 2–3 tree with n keys?

Approximately log3 n.

What is the main purpose of a B-tree?

B-trees support external searches in symbol tables that can contain trillions of items.

How does a left-leaning red–black BST represent a 3-node?

By using 'internal' left-leaning links as 'glue' for nodes.

What do red-black trees ensure about the paths from root to null links?

Every path from root to null link has the same number of black links.

What is the result of splitting a 4-node in a red-black BST?

It leads to a transformation that maintains symmetric order and black balance.

What is the average case performance of a 2-3 tree for search, insert, and delete operations?

Logarithmic performance, i.e., O(log n).

How many key-link pairs are allowed per node in a B-tree of order m?

Up to M - 1 key-link pairs per node.

What is the proposed advantage of using B-trees for large data sets?

B-trees allow for efficient search and insertion operations using minimal memory references.