Questions tagged [balanced-search-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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$. ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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$),...
user avatar
  • 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 <...
user avatar
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 ...
user avatar
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.
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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]$ $...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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)...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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} + ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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) ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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.
user avatar
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?
user avatar
  • 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-...
user avatar
  • 131