Questions tagged [balanced-search-trees]
The balanced-search-trees tag has no usage guidance.
130
questions
55
votes
4answers
16k views
Why are Red-Black trees so popular?
It seems that everywhere I look, data structures are being implemented using red-black trees (std::set in C++, SortedDictionary ...
41
votes
1answer
2k views
Imagine a red-black tree. Is there always a sequence of insertions and deletions that creates it?
Let's assume the following definition of a red-black tree:
It is a binary search tree.
Each node is colored either red or black. The root is black.
Two nodes connected by an edge cannot be red at the ...
22
votes
1answer
5k 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, ...
9
votes
4answers
5k views
Don't understand one step for AVL tree height log n proof
I came across a proof that the an AVL tree has O(log n) height and there's one step which I do not understand.
Let $N_h$ represent minimum number of nodes that can form an AVL tree of height h. Since ...
9
votes
2answers
5k views
Split in AVL tree with complexity $O(\log n)$
Can the split operation be implemented for AVL trees with complexity $O(\log n)$? I'm interested in links to articles or any specific information about this subject.
The split operation divides the ...
8
votes
2answers
8k views
A median of an AVL. How to take advantage of the AVL?
Here is the source of my question.
Given a self-balancing tree (AVL), code a method that returns the
median.
(Median: the numerical value separating the higher half of a data
sample from ...
7
votes
5answers
18k views
Why is b-tree search O(log n)?
B-tree is a data structure, which looks like this:
If I want to look for some specific value in this structure, I need to go through several elements in root to find the right child-node. The I need ...
6
votes
3answers
13k views
Average depth of a Binary Search Tree and AVL Tree
My professor recently mentioned that the average depth of the nodes in a binary search tree will be $O(log(n))$ where $n$ is the amount of nodes in the tree. I ended up drawing out a bunch of binary ...
6
votes
3answers
7k views
Compute height of AVL tree as efficiently as possible
Given an AVL tree, I want to compute its height as efficiently as possible. $\newcommand{\bf}{\text{bf}}\newcommand{\height}{\text{height}}$
Each node of an AVL tree stores its balance factor ($\bf$),...
6
votes
4answers
417 views
Order-preserving update of a sublist of a list of mutable objects in sublinear time
Description
Say I have a source list like: ["a","b","c","d"] and want to run a capitalization filter so if I change, "b" to <...
6
votes
2answers
4k views
Why is this not a valid Red-Black tree?
I'm having some difficulty understanding the rules for valid red-black tree.
If my understanding is correct there are 4 rules that a tree has to follow to be a red-black tree.
Every node has a color ...
6
votes
1answer
7k views
How many rotations after AVL insertion and deletion
Is it true that inserting an element to an AVL tree requires $O(1)$ rotations?
How many rotations, does deletion from AVL require?
I've searched for these two questions with no luck so far.
6
votes
2answers
3k views
Can a Red Black tree be constructed of only black nodes using RB insert only?
I am trying to construct a red black tree out of only black nodes.
I know it is possible getting it after some deletions but I am trying to construct one only via insertion orders.
Is it possible?
I ...
6
votes
0answers
303 views
Why most purely functional red-black trees are left-leaning?
Is there any particular reason for picking a left-leaning red-black tree over a regular red-black tree when trying to do a purely functional implementation?
I've not researched very deeply into this ...
6
votes
0answers
814 views
Voronoi diagram. Status structure in Fortune's Algorithm
I'm trying to implement the Fortune's Algorithm, however I can't quite figure out how the status structure should be implemented.
The following is extrapolated from my Computational Geometry book.
...
5
votes
3answers
4k views
Memory usage of a BST or hash table?
I would like to use a data structure allowing fast access, either a balanced binary search tree (BST) for $O(\log n)$ access time or an open hash table for constant access time.
1) What is the exact ...
5
votes
2answers
3k views
Balance factor changes after local rotations in AVL tree
I try to understand balance factors change after local rotations in AVL trees.
Given the rotate_left operation:
...
5
votes
1answer
545 views
Why aren't tries generally used?
To store say integers (positive), we prefer to use red black BSTs. I have never seen a explicit use of a trie anywhere to store numbers.
I believe we can convert numbers to string and store them in ...
5
votes
3answers
766 views
Why do some search trees store all the elements in leaves, while others don't?
Why do some search trees store all elements in the leaves, while other search trees don't?
One difference that makes is whether a successful search may end up in an internal node.
For m-ary search ...
5
votes
1answer
402 views
Persistent random-access queue
I need a queue $[x_0, ..., x_n]$ that supports the following operations:
$\operatorname{enqueue}([x_0, ..., x_n], x) = [x_0, ..., x_n, x]$
$\operatorname{dequeue}([x_0, ..., x_n]) = [x_1, ..., x_n]$
$...
4
votes
2answers
5k views
Maximal difference of height between two leaves in an AVL tree
What is the maximal difference between heights of leaves in an AVL tree? I am interested only in the asymptotic difference.
I am not sure about my answer - I think that it is $O(\log n)$, given the ...
4
votes
1answer
347 views
rope data structure - undo operation
I was reading (wikipedia) about how the rope data structure might be suitable for a text editor. Within the article it mentions "If only nondestructive versions of operations are used, rope is a ...
4
votes
2answers
2k views
Why do we need double-rotations to rebalance AVL trees?
I was reading about AVL tree rebalancing from Behrouz Forouzan's book. The book first defines Left High and Right High tree:
Left High (LH) tree is a tree tree with the height of the left ...
4
votes
1answer
1k views
Traversals from the root in AVL trees and Red Black Trees
We all know that for insertion() operation in AVL tree following can happen:
We traverse down the tree from root to appropriate node and there insert the key and then for maintaining height balance ...
4
votes
1answer
1k views
Should one limit the maximum level of a skip list node?
In Skip Lists: A Probabilistic Alternative to Balanced Trees by Pugh he suggests different strategies for choosing the level of an inserted node. One such strategy, called fix the dice, limits the ...
4
votes
1answer
212 views
What to infer about maximum height of AVL tree from these three different formulae
I have came across following problem:
What is the maximum height of any AVL-tree with 7 nodes?
The recurrence giving number of nodes $n$ in the AVL tree for given height $h$ is as follows:
$n(h)...
3
votes
1answer
7k views
How the deletion takes place in B+ Tree
My professor was giving a lecture on B+ Trees deletion, and I got very confused. According to him for deleting any key from a B+ Tree:
...
3
votes
2answers
395 views
Balancing a Binary Search Tree
I was reading about binary search trees on it's Wikipedia article. I was a little confused by this image. Why is it that the right branch to the head node does not have a sub-tree? I understand why it ...
3
votes
2answers
2k views
Does the rebalancing propagate upwards only to update the height of the nodes in an AVL tree?
I was studying AVL trees and was wondering if the only reason one propagates upwards to the node in an insert is to change the height. It seems to me that rebalancing does not recursively propagate ...
3
votes
1answer
1k views
What is the fastest way to merge two B trees?
Given two B-trees of some order $m$ - $T_1,T_2$, such that $y > x$ for every pair $x \in T_1$ and $y \in T_2$.
What is the fastest way to create a new tree that is the union of both $T_1,T_2$?
My ...
3
votes
1answer
1k views
Difficulty in updating the balance factor of nodes in AVL tree
In this figure x,y,z are the nodes on which rotation is performed and T1, T2, T3, T4 are the subtrees.
I have understood how the rotation is working and have no trouble with that. The problem I am ...
3
votes
1answer
1k views
Red-Black tree height from CLRS
The lemma 13.1 of CLRS proves that the height of a red black tree with $n$ nodes is
$$h(n) \leq 2\log_2(n+1)$$
There's a subtle step I don't understand. The property 4 reported at the beginning of ...
3
votes
1answer
723 views
Keeping a binary search tree by splitting nodes (like a B-Tree)
A B-tree is kept balanced (i.e. all leaves at same depth) by splitting a node when adding a child that won't fit, and propagating this splitting up to the root.
Can the same technique be used to keep ...
3
votes
1answer
254 views
Why do you reason about the minimum number of nodes of an AVL tree of height h to argue the height is $\log n$ of an AVL tree?
Recall the standard argument for showing an AVL free is of size $\log n$:
Let $n_h = $ be the minimum number of nodes of an AVL tree of height
$h$. Then we have:
$$ n_{h} \geq 1 + n_{h-1} + ...
3
votes
1answer
2k views
Maximal number of rotations after deleting a node in an AVL tree
What is the maximal number $c$ of single rotations after deleting a node from an AVL tree? We treat double rotations as two single ones.
I know that it is $O(\log n)$ but I'm trying to find a more ...
3
votes
1answer
510 views
Root Color of a Black Red Tree
It is required that, in a black red tree, the color for the root is always black. However, wikipedia argues that this rule can be omitted as a red root can always be changed to black but not vice ...
3
votes
1answer
574 views
Link-cut trees: using access() and link()
I am having some trouble on understanding link-cut trees, so I need some help.
Suppose that we have nodes $A, B, C, D$ and we want to do the following operations:
Link(A,B)
Link(B,C)
Link(C,D)
...
3
votes
1answer
1k views
Binary tree To Red-Black tree
I have a question regarding the solution provided by Karolis Juodelė.
Given in this question; Colour a binary tree to be a red-black tree
Black = black nodes, white = red nodes
So for this tree when ...
3
votes
1answer
137 views
State of the art time complexity for getting (tree) descendants by type/attribute
Let's say I have a tree comprised of nodes where each node is of some type (T), where there is a known/fixed number of types (i.e. similar to attributes in an xml document), and where a node can only ...
3
votes
0answers
310 views
What is the intuition behind balancing in AVL trees?
I am not sure that my question is clear from the first sight. But I will try to explain what I mean. For now, I am learning balancing the trees on the example of AVL trees. We know that to balance ...
2
votes
1answer
119 views
Height of epsilon-balanced binary search tree
In Balanced Binary Search Trees on the basis of size of left and right child subtrees, Hannes says:
For example, one can say, a BST is balanced, if each subtree has at
most epsilon * n nodes, ...
2
votes
1answer
468 views
Insertions in Red-Black Trees
I studied methods for inserting new nodes into Red-black trees for the first time this month.
In doing so, I read a lot of pages on the internet and found that ( if I'm not mistaken ) there are many, ...
2
votes
1answer
464 views
Question on the properties of red black trees
Problem statement
Let $T$ be a red black tree and $u$ some internal node of $T$. Suppose that in the left subtree of $u$ we have $n$ nodes. What is the maximum number of nodes that we can have in the ...
2
votes
2answers
559 views
Finding median weights in all paths of an AVL tree with weighted nodes
I need some help with proving the complexity of the following problem
(I'm new here, so please excuse my "newbie-ness")
Given: an AVL tree with keys: $1,2,..,n$, such that each node $i$ in the tree ...
2
votes
2answers
2k views
AVL tree worst case height proof
The worst case height of AVL tree is $1.44 \log n$. How do we prove that?
I read somewhere about Fibonacci quicks but did not understand it.
2
votes
1answer
581 views
Example of height-balanced tree that is not weight-balanced
Following this question : Two definitions of balanced binary trees
I am having a hard time making sense of the proofs provided and I'm looking for an example of a simple binary tree that is height-...
2
votes
2answers
55 views
Self-balancing BST supporting in-order-sequential multi-insertions / multi-deletions in logn+klogk time?
Given a self-balancing binary search tree of size $n$, I want to perform the following operations:
InsertInOrderSequentialBatch an ordered sequence of $k$ values (...
2
votes
1answer
211 views
I don't understand the case 4 of red-black tree deletion
I don't know why case 4 will resolve the issue of the double black of $x$ described in Introduction to algorithm p.329. I know case 1 is transformed into one of {2,3,4} case, and case 2 re-point $x$ ...
2
votes
1answer
634 views
Left-Right-Rotation of AVL-Tree
For AVL-Tree there exists the following Rotations for Balancing:
Left Rotation
Right Rotation
Left-Right Rotation
Right-Left Rotation
My Question is about the Naming for the Double-Rotations. ...
2
votes
1answer
81 views
Efficient search algorithm for a monotonic boolean array wherein the probability of target's location is available apriori
A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$.
$$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in ...
