Questions tagged [search-trees]

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

Filter by
Sorted by
Tagged with
16
votes
2answers
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. ...
9
votes
2answers
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 ...
4
votes
2answers
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-...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
8
votes
7answers
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 ...
3
votes
1answer
7k views

What is the time complexity of calling successor $n$ times during tree traversal?

According to some sources, the time complexity of finding the successor of a node in a tree is $O(h)$. So, if the tree is well balanced, the height $h=\log n$, and the successor function takes time $O(...
1
vote
1answer
316 views

Can you have a binary search tree with O(logn + M) property for the following case

Let $n$ be the number of strings which are sorted in lexicographical order and stored in a balanced binary search tree. You are provided with a prefix $x$ of which $M$ strings have the prefix $x$. I ...
2
votes
2answers
13k views

Nim game tree + minimax

Problem : Two players have in front of them a single pile of objects, say a stack of 7 pennies. The first player divides the original stack into two stacks that must be unequal. Each player ...
1
vote
1answer
268 views

Can you have three consecutive black nodes in red-black search tree?

Suppose I am making a red-black search tree, and in my right subtree, I have a black node, then a red node, and it has two black children, the black children further black childrens. As such a lemma ...
10
votes
1answer
14k views

Proof that a randomly built binary search tree has logarithmic height

How do you prove that the expected height of a randomly built binary search tree with $n$ nodes is $O(\log n)$? There is a proof in CLRS Introduction to Algorithms (chapter 12.4), but I don't ...
5
votes
1answer
1k views

Explanation of recursive structure of Van Emde Boas Tree

From Van Emde Boas trees lecture: We will use the idea of superimposing a tree of degree ${u^{1/2}}$ on top of a bit vector, but shrink the universe size recursively by a square root at each ...
3
votes
3answers
16k views

Average number of comparisons to locate item in BST

This is a GRE practice question. If a node in the binary search tree above is to be located by binary tree search, what is the expected number of comparisons required to locate one of the items (...
3
votes
2answers
464 views

Binary Search Tree Property

In the book 'Introduction to Algorithms 3/e', I have found the following definition of Binary Search Tree property: Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree ...
20
votes
1answer
989 views

Lock-free, constant update-time concurrent tree data-structures?

I've been reading a bit of the literature lately, and have found some rather interesting data-structures. I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
5
votes
1answer
455 views

Prove that for a general data structure - operations Extract_min() and Insert(x) cost $\Omega(\log n)$?

I've been given the following problem: Given a data structure $M$ that is based on comparisons and supports the following methods on a group of numbers $S$: $\text{Insert}(x)$ – add $x$ to $S$ $\...
11
votes
2answers
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 ...
25
votes
1answer
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 ...
9
votes
3answers
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 ...
20
votes
2answers
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 ...
22
votes
1answer
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, ...
30
votes
2answers
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 ...