Questions tagged [balanced-search-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
17 views

In a relaxed radix balanced (RRB) tree, how is the height determined in practice?

In a traditional radix-balanced tree, the height of the tree can be determined quickly by counting the leading zeros of the number of elements of the tree, and indexes to node children can be ...
user avatar
  • 111
2 votes
1 answer
51 views

How did the following derivation of the final weight of a weight-balanced search tree node after rotation to make it balanced occur?

I was reading section 3.2 of Advanced Data Structures by Peter Brass (which is about weight-balanced search trees) for self-study. I got stuck on a proof about rebalancing properties. $\alpha$ and $\...
user avatar
0 votes
1 answer
14 views

Which particular data structure should I use if I want a persistent balanced search tree?

As title, I'm trying to implement a text editor with the rope data structure, which is backed by binary search tree. Since I want it to have persistent undos, the underlaying data structure should ...
user avatar
0 votes
1 answer
55 views

Interval Tree by Augmenting an AVL Tree

According to Wikipedia: An augmented tree can be built from a simple ordered tree, for example a binary search tree or self-balancing binary search tree, ordered by the 'low' values of the intervals. ...
user avatar
0 votes
1 answer
93 views

Height of AVL Tree

I found an AVL tree implementation on the internet and experimented: For a tree with node count of 2^20, the minimal and maximal tree heights are 16 and 24. While these heights are lg(n)-ish, I am ...
user avatar
0 votes
1 answer
32 views

Are AVL&RB Trees without additional storage for balance information in each node feasible?

One advantage claimed for scapegoat trees over other balanced trees like AVL or red-black(RB trees - just mentioning AVL henceforth) is not needing to store additional balance information. But can't ...
user avatar
  • 915
2 votes
1 answer
93 views

How to join two Scapegoat Trees in O(log n) time?

I am working on some binary-search-tree research and was surprised to find no mention of an algorithm to join two Scapegoat Trees. This is where two trees $L$ and $R$ are joined to create a single ...
user avatar
1 vote
1 answer
207 views

For a balanced binary search tree what is the worst case case time complexity for accessing all elements within a range of nodes?

I have this question which is asking for the worst case time complexity for a balanced binary search tree, assume the nodes are labeled as integers and we consider a range of ...
user avatar
2 votes
2 answers
63 views

Self-balancing BST supporting in-order-sequential multi-insertions / multi-deletions in logn+klogk time?

Given a self-balancing binary search tree of size $n$, I want to perform the following operations: InsertInOrderSequentialBatch an ordered sequence of $k$ values (...
user avatar
  • 141
0 votes
0 answers
38 views

Having trouble understanding Red-Black trees

Exam question: Draw the Red Black Tree that results from inserting the following values in the given order: [10, 20, 30, 4, 5, 50] Draw the red connections with a dotted line and the black ones with ...
user avatar
1 vote
2 answers
447 views

is it possible to create an avl tree given any set of numbers?

I am studying balanced trees, especially AVL trees. My question is whether is it possible to create an avl tree given any set of numbers. is it possible to prove the following statement? Let $A$ be ...
user avatar
  • 113
1 vote
0 answers
52 views

efficient DELETE in proto-Van Emde Boas Tree?

TLDR: CLRS is claiming that a certain "pseudo" or "proto" tree structure does not have fast deletion, but I seem to have an algorithm that is efficient, and I would like to know ...
user avatar
  • 810
0 votes
0 answers
224 views

What is the maximal difference between the depths of 2 leaves in AVL tree?

I'm wondering what's the answer of the following question: What is the maximal difference between the depths of 2 leaves in an AVL tree? Intuitively I think that it shouldn't exceed $log n$ but have ...
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
3 votes
1 answer
1k 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
  • 71
1 vote
2 answers
57 views

What is the name of the data structure that is a tree on the backend but has a list like API?

I'm looking for the name of a data structure. It is organized like a balanced tree. The elements need not be comparable. Instead of asking if the tree contains a thing (like you would with a ...
user avatar
  • 486
1 vote
1 answer
567 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, ...
user avatar
  • 113
1 vote
0 answers
119 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-...
user avatar
  • 41
1 vote
1 answer
70 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. ...
user avatar
2 votes
1 answer
51 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 ...
user avatar
2 votes
1 answer
127 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
0 votes
1 answer
299 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 ...
user avatar
1 vote
1 answer
2k 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 ...
user avatar
0 votes
0 answers
80 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 ...
user avatar
0 votes
1 answer
47 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 ...
user avatar
  • 127
1 vote
1 answer
539 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 ...
user avatar
  • 317
2 votes
1 answer
557 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
0 votes
0 answers
431 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 ...
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
3 answers
911 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 ...
user avatar
2 votes
1 answer
244 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$ ...
user avatar
  • 241
1 vote
0 answers
30 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 ...
user avatar
0 votes
0 answers
329 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}$ ...
user avatar
2 votes
0 answers
42 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 ...
user avatar
  • 21
1 vote
0 answers
49 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 (...
user avatar
  • 11
1 vote
1 answer
172 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'...
user avatar
  • 147
2 votes
0 answers
47 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 ...
user avatar
  • 121
-1 votes
1 answer
205 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)?
user avatar
6 votes
1 answer
8k 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
2 votes
1 answer
745 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. ...
user avatar
  • 123
0 votes
1 answer
179 views

AVL tree size in terms of height

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. $...
user avatar
1 vote
1 answer
2k views

Deletion from 2,3,4 tree

Consider a 2,3,4 tree like so, ...
user avatar
  • 262
1 vote
1 answer
1k 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-...
user avatar
  • 175
6 votes
0 answers
317 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
0 votes
0 answers
1k 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) ...
user avatar
  • 1
1 vote
1 answer
433 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?
user avatar
4 votes
1 answer
378 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
0 votes
0 answers
58 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-...
user avatar
  • 159
0 votes
1 answer
575 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 ...
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