Questions tagged [balanced-search-trees]
The balanced-search-trees tag has no usage guidance.
137
questions
60
votes
4
answers
18k
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 ...
- 837
41
votes
1
answer
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 ...
- 409
22
votes
1
answer
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, ...
- 6,151
10
votes
2
answers
6k
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 ...
- 101
9
votes
2
answers
10k
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 ...
- 399
9
votes
4
answers
5k
views
Don't understand one step for AVL tree height log n proof
I came across a proof that an AVL tree has $O(\log n)$ height and there's one step which I do not understand.
Let $N_h$ represent the minimum number of nodes that can form an AVL tree of height $h$. ...
- 339
8
votes
7
answers
58k
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 any ...
- 359
8
votes
5
answers
20k
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 ...
- 202
6
votes
3
answers
15k
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 ...
- 203
6
votes
3
answers
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$),...
- 543
6
votes
4
answers
431
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 <...
- 173
6
votes
2
answers
5k
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
1
answer
9k
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.
- 157
6
votes
2
answers
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 ...
- 179
6
votes
0
answers
320
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 ...
- 203
6
votes
0
answers
918
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.
...
- 663
5
votes
3
answers
5k
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 ...
- 435
5
votes
2
answers
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:
...
- 283
5
votes
1
answer
564
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 ...
- 51
5
votes
3
answers
937
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 ...
- 1
5
votes
2
answers
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 ...
- 663
5
votes
1
answer
411
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]$
$...
- 61
4
votes
2
answers
6k
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 ...
- 543
4
votes
1
answer
402
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 ...
- 51
4
votes
2
answers
3k
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 ...
- 1,695
4
votes
1
answer
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 ...
- 322
4
votes
1
answer
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 ...
- 45
4
votes
1
answer
230
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)...
- 1,557
3
votes
1
answer
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:
...
- 213
3
votes
2
answers
420
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 ...
- 247
3
votes
1
answer
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 ...
- 33
3
votes
2
answers
3k
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 ...
- 2,920
3
votes
1
answer
2k
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 ...
- 83
3
votes
1
answer
726
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 ...
- 31
3
votes
1
answer
284
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} + ...
- 2,920
3
votes
1
answer
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 ...
- 543
3
votes
1
answer
525
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 ...
- 133
3
votes
1
answer
614
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)
...
- 133
3
votes
1
answer
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 ...
- 31
3
votes
1
answer
160
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 ...
- 133
3
votes
0
answers
334
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 ...
- 131
2
votes
1
answer
129
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, ...
- 143
2
votes
1
answer
595
views
Finding an interval in a binary search tree that contains a point
I have a binary search tree where nodes are non-overlapping intervals. I'm given a point, and I need to determine which interval the point belongs to (if any). This is easy to do because I can compare ...
- 203
2
votes
1
answer
515
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, ...
- 320
2
votes
1
answer
509
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 ...
- 599
2
votes
2
answers
583
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 ...
- 205
2
votes
1
answer
1k
views
Worst Case for AVL Tree Balancing after Deletion
After deleting a node in an AVL tree, self-balancing (zig-zag rotation or the left-right balancing) maintains O(logn) time that is not guaranteed in other unbalanced trees (like BST).
The Balancing ...
2
votes
2
answers
3k
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.
- 364
2
votes
1
answer
1k
views
Red-black tree amortized cost of the rebalancing
I've read in different sources that the amortized cost of a red-black tree rebalancing is constant (at least during the tree creation using only insertions).
How can it be proven?
- 143
2
votes
1
answer
601
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-...
- 131