# Questions tagged [balanced-search-trees]

The tag has no usage guidance.

115 questions
Filter by
Sorted by
Tagged with
473 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 ...
230 views

### Link-cut trees: how to code cut(u,v)

In most bibliography, only cut(v) is defined. More properly, only cut(v,v.parent) is defined, where (v,v.parent) is an edge in the represented tree. The pseudo-code and code for this is: ...
444 views

### Forming red-black tree from binary tree conserving in-order traversal

What is the optimal algorithm (in terms of time complexity) that can transform any binary tree to a red-black tree, with the requirement that in-order traversal must yield the same values for the new ...
404 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,...
212 views

### How important is balance of a tree?

I am exploring variations of trees. I know that a quality which is sometimes desired is balance in the tree so that tree depth is reduced. But I am imagining that in situations in which several paths ...
325 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, ...
239 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 ...
409 views

### Using rotate to balance a red-black tree?

You have a Black-Red Tree of height h that has two childs: Left child is a full binary tree of height h-1 Right child ...
683 views

### For AVL trees, how do we know if a RL or a LR rotation is needed?

Suppose I am trying to construct a simple AVL tree: Upon inserting 'B' the tree becomes imbalanced. How do I exactly know that I need a LR or RL rotation without making any guesses? From what I ...
681 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 ...
60 views

### Height of data structures

Why the height complexity of a data structure, generally expressed in terms of $\log n$, do not contain a ceiling or floor ?
418 views

### Time complexity of the operations on a b-tree if deletion is performed by marking nodes inactive

I'm given a B-tree where the delete-operation is not implemented, but instead keys are deleted using tombstones (so they stay in the tree, but are marked as deleted). Now when at least 90% of all keys ...
1k views

### How does the double rotation in AVL tree work?

I am trying to find out from this visualization how does the AVL trees work. But I am not able to find out how is the algorithm choosing which vertex is the right one to use as "partial root". The ...
163 views

### About the definition of a balanced tree

(Note: I couldn't put "balanced tree" in the tags ; this topic isn't about balanced search trees, just balanced trees.) Let $A$ a binary tree. We have the relation: $log(|A|+1) \leq h(A) \leq |A|-1$ ...
868 views

### weight balanced binary tree vs height balanced binary tree [closed]

What are advantages and disadvantages of weight balanced binary tree over the height balanced binary tree?
789 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 ...
391 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 ...
156 views

### Is “promoting a key” a part of deleting internal node key in B+ Tree?

I was trying to learn B+ tree deletion operation and trying to contrast it with B tree deletion operation. However barely any book provided detailed step by step B+ tree deletion operation. So I was ...
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 ...
137 views

### Zero-based array implementation with logarithmic insertion time

Normal zero-based arrays (ie not those with a sort order) have constant lookup time, but linear insertion time. For a specific problem I was musing about a balanced tree that would allow for an zero-...
8k 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 ...
402 views

### Priority Queue using an AVL tree, run time question

This is a question I want to answer in pseudocode: This is regarding a sort of priority queue using an AVL tree. I initialize a global variable (named GLOB) with 0. I receive from the user an input ...
534 views

### Trying to understand a way to split an AVL tree in O(log n)

I'm trying to understand a presentation about AVL trees. It says that the way to split AVL trees in node x is as follows: You search for the node x and mark every left son of every node when you turn ...
96 views

### Lookup complexity in B-trees [Database]

Given that: B = n/R blocks in the file 2d index records per block (blocking factor): 2d > R an extra block access from the index to the datafile I am not able ...
140 views

145 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} + ...
979 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 ...
82 views

### Can the right childs of a node in an AVL tree be both balanced after an insert and need rebalancing?

I was trying to come up with a case where one would need rebalance the following case in an AVL tree: I think that case impossible to happen during an insert. It seems to me that its impossible to ...
878 views

### How do I find the number of inversions using a red black tree?

I'm trying to figure out a way to find the number of inversions in permutation time O(nlogn) using red black trees. Here's how I think it can be done. So if I have an algorithm that inserts a new node ...
565 views

### Reb-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 proved?
754 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 ...
2k 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 ...
1k views

### Every AVL tree may be red black tree

I proved by induction that every AVL tree may be colored such that it will be red black tree. The problem is that I can't see an error in my proof. Look at my proof. Induction for height. Let's ...
809 views

### AVL tree such that each insert causes rotation (single or double)

Could you give me an example of an AVL tree for which inserting an element at an arbitrary (i.e. every) position causes a rotation (double or single)? I have tried to come up with an example, but I ...
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$),...
5k 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: ...
1k views

### non-binary self balancing tree

I'm looking for a tree data structure that allows to keep the tree balanced in high (minimum high as possible). I mean, suppose a tree where: each node has a parameter k that is the maximum number ...
496 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-...
987 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 ...
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: ...
1k views

### Red Black Tree deletion algorithm (CLRS, 3rd edition) : Deleting the root

I have been following the third edition of Introduction to Algorithms (by Cormen, Rivest et al), and have been studying the deletion algorithm for red black trees. However, I am confounded at the ...
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 ...
432 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 ...
122 views

### Why not use large $k$ in a $k$-ary tree?

Obviously binary trees are great because of $O(\log_2 n)$ search, inserts, and deletes in best case. To "maximize" occurrence of best case, we can use self-balancing trees like red-black trees, AVLs, ...
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 ...