Questions tagged [balanced-search-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
16 views

How can I get the overall winner's leaf node in a loser tournament tree used for k-way merge?

I've read the wikipedia that has some insight on how a loser tournament tree ought to be constructed, but I'm confused as hell by the pseudo-code shown. How are you supposed to get the overall winner'...
  • 113
1 vote
0 answers
32 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 ...
  • 111
2 votes
1 answer
52 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 $\...
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 ...
0 votes
1 answer
102 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. ...
0 votes
1 answer
144 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 ...
0 votes
1 answer
40 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 ...
  • 915
2 votes
1 answer
97 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 ...
1 vote
1 answer
317 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 ...
2 votes
2 answers
65 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 (...
  • 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 ...
1 vote
2 answers
471 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 ...
  • 113
1 vote
0 answers
57 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 ...
  • 818
0 votes
0 answers
272 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 ...
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 ...
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 ...
  • 83
1 vote
2 answers
61 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 ...
  • 486
1 vote
1 answer
620 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, ...
  • 113
1 vote
0 answers
128 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-...
  • 41
1 vote
1 answer
73 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. ...
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 ...
2 votes
1 answer
131 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, ...
  • 143
0 votes
1 answer
367 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? ...
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 ...
0 votes
0 answers
95 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 ...
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 ...
  • 127
1 vote
1 answer
665 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 ...
  • 317
2 votes
1 answer
623 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 ...
0 votes
0 answers
450 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 ...
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.
2 votes
3 answers
957 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 ...
2 votes
1 answer
252 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$ ...
  • 239
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 ...
0 votes
0 answers
361 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}$ ...
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 ...
  • 21
1 vote
0 answers
51 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 (...
  • 11
1 vote
1 answer
176 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'...
  • 147
2 votes
0 answers
48 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 ...
  • 121
-1 votes
1 answer
216 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)?
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.
  • 157
2 votes
1 answer
792 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. ...
  • 123
0 votes
1 answer
219 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. $...
1 vote
1 answer
2k views

Deletion from 2,3,4 tree

Consider a 2,3,4 tree like so, ...
  • 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-...
  • 175
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 ...
  • 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) ...
  • 1
1 vote
1 answer
441 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?
4 votes
1 answer
408 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 ...
  • 51
0 votes
0 answers
59 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-...
  • 169
0 votes
1 answer
588 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 ...