Questions tagged [balanced-search-trees]
The balanced-search-trees tag has no usage guidance.
140
questions
-3
votes
1
answer
93
views
Can you simulate the following process in $O(N.log N)$
Given an array $A[]$ of N integers.
pseudocode:
Traverse from left to right of this array.
Let's say you are standing at index $j$.
For each index i=1 to i=j-1, increment all $A[i]$ by $1$ if and ...
- 113
1
vote
0
answers
49
views
Merge two red black trees with the same black height
Consider two red-black trees T1 and T2, each with black-height h, with all values in T1 less than all values in T2. How to merge these two trees to obtain a red-black tree in O(h). The root is always ...
- 143
2
votes
1
answer
124
views
Approximating the median of the complement of a set
Given an integer $n$ and a tree set $S$, I would like to find the approximate median $x$ of the integer set $T := \{i \in \mathbb N : i < n \wedge i \notin S\}$. There are no constraints to the ...
- 133
0
votes
1
answer
41
views
maximum length of the sequence (a[i],b[i]) such that if $b[i]='<'$ then $a[i+1]<a[i]$ and if $b[i]='>'$ then $a[i+1]>a[i]$
Let $N$ be a number and consider the sequence of $a[i]$, $b[i]$ with $i=1,n$ where $a[i]$ are positive integers and $b[i]$ is the sign '$<$' or '$>$'. Find the maximum length of the subsequence(...
- 101
2
votes
0
answers
131
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 ...
- 121
2
votes
1
answer
54
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
27
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 ...
- 3
1
vote
1
answer
201
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. ...
- 135
0
votes
1
answer
362
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 ...
- 135
-1
votes
1
answer
66
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 ...
- 965
2
votes
1
answer
119
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 ...
- 203
1
vote
1
answer
656
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 ...
- 219
2
votes
2
answers
77
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
47
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
558
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
68
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 ...
- 838
0
votes
0
answers
405
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 ...
- 131
3
votes
1
answer
2k
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
70
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 ...
- 516
1
vote
1
answer
877
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
153
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
85
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.
...
- 11
2
votes
1
answer
55
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
145
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
526
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
3k
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 ...
- 83
0
votes
0
answers
119
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 ...
- 227
0
votes
1
answer
73
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
921
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
823
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 ...
- 203
0
votes
0
answers
564
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 ...
- 1
3
votes
2
answers
4k
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.
- 394
2
votes
3
answers
1k
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 ...
- 125
3
votes
1
answer
392
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$ ...
- 249
1
vote
0
answers
34
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 ...
- 121
0
votes
0
answers
384
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}$ ...
- 1
2
votes
0
answers
46
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
58
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
211
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
50
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
260
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)?
- 1
8
votes
1
answer
10k
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.
- 187
2
votes
1
answer
900
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
310
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. $...
2
votes
1
answer
2k
views
1
vote
2
answers
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
332
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
2k
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
493
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?