# Questions tagged [search-trees]

Questions about search trees, a class of data structures used for storing sorted data for efficient access.

272 questions
Filter by
Sorted by
Tagged with
9k views

### Colour a binary tree to be a red-black tree

A common interview question is to give an algorithm to determine if a given binary tree is height balanced (AVL tree definition). I was wondering if we can do something similar with Red-Black trees. ...
466 views

### Are probabilistic search data structures useful?

A SkipList provides the same $O(\log n)$ bounds for search as a balanced tree with the advantage that rebalancing isn't necessary. Since the SkipList is constructed using random coin flips, these ...
1k views

### Uniform-cost Search Problem

Suppose that we take an initial search problem and we add $c > 0$ to the costs on all edges. Will uniform-cost search return the same answer as in the initial search problem? Definitions: Uniform-...
1k views

### B-tree branching factor boundaries

A BTree has a $k$ value that determines that every node has $k$ to $2k$ children. When a node has $2k$ keys it needs to be split into two nodes. Let's say I want to create a $k/(2k-x)$ tree. (like a ...
119 views

### Height of AVL after entries

Problem: Suppose $V$ is an AVL tree (a self-balancing binary search tree) of $n$ elements. After the insertion of $n^2$ elements, what would be its height? My idea: the height of an AVL tree is ...
43k views

### Are degree and order the same thing when referring to a B-Tree

I know the term order of a B-tree. Recently I heard a new term: B tree with minimum degree of 2. We know that the degree is related to a node but what is the degree of a tree? Does degree impose ...
7k views

3k views

### Hashing using search trees instead of lists

I am struggling with hashing and binary search tree material. And I read that instead of using lists for storing entries with the same hash values, it is also possible to use binary search trees. And ...
4k views

### Why does the splay tree rotation algorithm take into account both the parent and grandparent node?

I don't quite understand why the rotation in the splay tree data structure is taking into account not only the parent of the rating node, but also the grandparent (zig-zag and zig-zig operation). Why ...
4k views

### Logarithmic vs double logarithmic time complexity

In real world applications is there a concrete benefit when using $\mathcal{O}(\log(\log(n))$ instead of $\mathcal{O}(\log(n))$ algorithms ? This is the case when one use for instance van Emde Boas ...
779 views

### Creating a Self Ordering Binary Tree

I have an assignment where I need to make use a binary search tree and alter it to self order itself such that items that are accessed the most (have a higher priority) are at the top of the tree, the ...
4k views

### AVL trees are not weight-balanced?

In a previous question there was a definition of weight balanced trees and a question regarding red-black trees. This question is to ask the same question, but for AVL trees. The question is, ...
7k views

### Not all Red-Black trees are balanced?

Intuitively, "balanced trees" should be trees where left and right sub-trees at each node must have "approximately the same" number of nodes. Of course, when we talk about red-black trees*(see ...