# Questions tagged [balanced-search-trees]

The tag has no usage guidance.

121 questions
Filter by
Sorted by
Tagged with
26 views

### Splitting a node in B+ tree with odd number of keys

This and several other resources suggest to "Always a node that gets the middle key from bottom splits, should drop one item for a new middle key". To illustrate with an example. For 5-way B+-tree, ...
40 views

### Modifying insert and remove functions of an AVL tree so that nodes that don't need to be rebalanced are not checked for balance

Trying to modify an insert and remove function for an AVL Tree so that no nodes are checked for balance that do not need to be. The suggested way to do was was to change the return types of insert, ...
18 views

### Scapegoat Trees: Why are they only loosely a-height-balanced?

From Wikipedia: Even a degenerate tree (linked list) satisfies this condition if α=1, whereas an α=0.5 would only match almost complete binary trees. A binary search tree that is α-weight-...
23 views

### Treap union unrandomizes priorities?

The algorithm for the union of two sets represented by treaps is defined in this paper and on Wikipedia, but the algorithm seems flawed. Take for example the following loop. ...
43 views

### What would happen if we added this rule to red-black trees?

So, I know that a normal r-b tree has a height of O(logn). What would happen is we let a red node have a red child if its parent is black? Would the height still be O(logn)? Would you have to have a ...
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, ...
32 views

### Is the tree shown a valid red-black tree?

I have made a red-black tree and I think that it is not valid. Could someone please verify? As far as I know, in red-black tree we also consider the leaf nodes at the NULLS of the visible leaf nodes ...
69 views

### How to prove that in an AVL tree with height h, the depth of every leaf node is at least $\lceil h/2 \rceil$

I have an AVL tree with height h. I understand how to get h $\thickapprox$ 1.440 log N. However, I can't figure out how to calculate the minimum depth of a leaf node from root. I tried constructing a ...
30 views

### Linked lists with auxiliary data

I'm trying to design a data structure that supports the following operations in $O(1)$ time: $\operatorname{query}(\ell)$: Yield some auxiliary datum associated with list $\ell$ (just a single ...
19 views

### AVL tree balance property states for the two subtrees of a node, their height can differ at most one. Why can't it be zero?

I was thinking that if they were equal, say they are required to be zero this would be enforce the balance property more effectively. Can anyone explain why 1 is a satisfactory rather than just them ...
11 views

### Depth of an R-tree, given $m$, $M$ and number of elements

Simply: what is the theoretical maximum, minimum or expected depth of an R-tree given $m$ minimum $M$ maximum elements in a node, with $N$ amount of nodes?
65 views

### How to find the number of intervals containing a point when given a static set of intervals?

I've seen similar questions around here but I'm trying to address this problem with a slight change and maybe it makes it easier to solve. I'm given a set of intervals $\{s_1,s_2,...,s_n\}$ where ...
83 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 ...
93 views

### How to create an AVL tree, given it's pre-order traversal?

Given the pre-order traversal, we can easily obtain the necessary Binary Search Tree(BST- not necessarily balanced). However, the problem arises when we have to decide the balancing manually(this was ...
472 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.
184 views

### How do I know which direction I should rotate a node in an AVL Tree?

I'm studying AVL Trees in my programming class and we got this exercise dealing with right, left, left-right and right-left rotations as a way to check if we understand the theoretical concept of AVL ...
112 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$ ...
19 views

### Does keeping underflowed nodes unbalance the R-tree?

When deleting nodes from an R-tree, if a branch underflows, then it's meant to be dissolved and its children are meant to be reinserted into the tree. But most R-tree implementations that I've seen ...
109 views

### Counting chords intersections in a circle

The problem is: Given 2n distinct endpoints of n chords on the unit circle, count the number of intersections between chords (if k chords intersect at one point, that point counts as $\binom{n}{2}$ ...
35 views

### Documentation of “bin number” trees

TL;DR: I implemented a special (?) binary tree and can't find any further details on the method I used on the internet. I would like to know if there are any scientific papers discussing my ...
38 views

### Efficient data structure for multidimensional searching on intervals and keys

I am searching for a data structure that can capture a database, which is consisted of one column of intervals (like [0, 2], [4, 6]) and one/two columns of keys (...
60 views

### Minimum finger search tree complexity

Suppose I have an AVL tree with a pointer to the minimal element. I'd like to conduct a search for some key x, which is the $k$-smallest key in the entire tree. I can do this by "climbing" up the tree'...
21 views

### B/B+ trees without leftmost pointers

In both B-trees and B+trees, a node (a.k.a page) contains K keys and K+1 pointers: node = [ ptr_1, key_1, ... , ptr_K , key_K , ptr_(K+1) ] Now suppose that I ...
111 views

### All the possible inputs for a given AVL tree

Given an AVL tree,what are the possible inputs so that the same given tree is formed(please dont mention brute force technique)?
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.
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. ...
66 views

For AVL trees, which one of the following is possible as the tree size (expressed in term of the tree height h)? Recall that the size of a tree is the number of nodes in the tree. A. $Θ(h^{2.1})$ B. $... 1answer 702 views ### Deletion from 2,3,4 tree Consider a 2,3,4 tree like so, ... 1answer 454 views ### Is every AVL tree a BST or just BT? I was going through the concepts of AVL tree and came across the definition of AVL tree from the wiki. In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-... 0answers 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 ... 0answers 353 views ### Find the median in two AVL BSTs in O(log(n)) So theres the classic problem of finding the median in an AVL BST in O(log(n))* However given two AVLs, each having N different values (all values in both trees combined would be 2N different values) ... 1answer 212 views ### Number of leaf nodes in n-element red-black trees Why the number of (NIL) leaf nodes in n-element red-black trees is n+1? 1answer 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 ... 0answers 31 views ### Understanding of recurrence relation for number of 2-nodes in 2-3 tree $$A_N = A_{N-1} - \frac{2A_{N-1}}{N} + 2\left(1- \frac{2A_{N-1}}{N}\right),\quad \text{for}\ N > 0, A_0 = 0.$$ Probability for 2-node to become 3-node is$\frac{2}{N}$and for 3-node to become 2-... 1answer 233 views ### All possible Red Black Trees with this set {1,2,3,4,5} I have to write all possible Red Black Trees which can represent these 5 numbers {1,2,3,4,5}. Now we have 120 ways to write 1,2,3,4,5 ... 1answer 647 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 ... 1answer 145 views ### how does rotation works in AVL trees and what is a good way to understand it? If we consider this tree with T1 and T2 as subtrees, and we want to rotate on x (rotating the edge between T1 and x), what is the result? how does it work then? Does the x stay in its place and T1 ... 0answers 93 views ### Insert-Max and Delete-Min in WAVL tree Given a WAVL tree with pointers to its' minimum and maximum, we will add two operations: Insert-Max: given an element, which is bigger than all other elements in the tree, add it as the right child ... 1answer 152 views ### Avarage height of Red-Black tree [closed] I wrote a program to discover how height of the tree is relative to the number of elements in the tree (nodes). On first test I filled array with 10-50-100-200...-1000 elements of random numbers from ... 1answer 2k views ### How many node does the final B-tree have? I'm currently studying the B-Trees chapter of Introduction to Algorithms. One of the question from the chapter is: Suppose that we insert the keys$\{1,2,...,n\}$into an empty B-tree with minimum ... 1answer 264 views ### Simulating AVL Tree Right, then Left rotation I have the following AVL tree and want to AVL-INSERT a node 5 into the tree. Since the middle branch will be unbalanced, I'm guessing that it will require a right rotation, then a left rotation to ... 1answer 314 views ### return a key of a node with maximum value within a range of keys in B+ tree I've been asked a question about B+ Tree. The question is: Suppose we have object of the following type: ... 1answer 43 views ### rebalance red-black tree with many violations Every red-black tree implementation I've come across use a strategy that considers re-balancing the tree after each mutation (e.g. insert, delete, ...). I have a situation where I graft several sub-... 0answers 39 views ### AVL Tree Inner Nodes If k is the height of an AVL Tree, the minimal number of inner nodes is: N(k) = N(k-1) + N(k-2) +1. Why is this formula true? 0answers 433 views ### Tight upper bound on height of a red-black tree "Introduction to Algorithms" by Cormen et al., 3rd edition, Lemma 13.1 states that A red-black tree with$n$internal nodes has height at most$2\log(n+1)$, i.e.$h \le 2\log(n+1)$. Can equality ... 1answer 73 views ### How to retrieve reset bit in constant time in a bit array In a game application there is a session id assigned to each player every time they start a new session. Session id's are always unique and there can be billion users of this game. Whenever a user ... 1answer 676 views ### How is the data stored in AVL tree in a memory? [duplicate] I have been struggling to visualize how is the AVL tree is stored in memory? Does it store data in array or list, If so how is it connected with its child and parents. 1answer 4k views ### Maximum depth of a B+ tree Given$K$...# key values,$n$...# pointers in a node. I read somewhere, that the maximum depth is defined as$\lceil\log_{\...
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$, ...