# Questions tagged [balanced-search-trees]

The tag has no usage guidance.

121 questions
Filter by
Sorted by
Tagged with
12k 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 ...
1k 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 ...
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, ...
3k 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 ...
5k 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 ...
7k 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 ...
377 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 <...
4k 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 ...
509 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. ...
2k 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: ...
475 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 ...
4k 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$),...
2k 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 ...
2k 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 ...
331 views

237 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 ...
2k 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 ...
333 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 ...
186 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 ...
658 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 ...
768 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 ...
662 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 ...
788 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 ...
453 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 ...
486 views

### AVL tree partition

The statement sais the following Design a function to partition an AVL tree such that, given an AVL tree and a key $x$, it returns two AVL trees, one containing the keys lower or equal than $x$, ...
434 views

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,...
855 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 ...
427 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 ...
117 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 ...
253 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 ...
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 ...
3k 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 ...
99 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, ...
2k 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.
371 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, ...
420 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 ...
6k 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: ...
397 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 ...
515 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-...
393 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. ...
74 views

1k 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 ...