Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [balanced-search-trees]

The tag has no usage guidance.

1
vote
0answers
20 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 (...
0
votes
1answer
52 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'...
0
votes
0answers
14 views

AVL Tree:Deletion proof

Show that at most one node in an AVL tree becomes temporarily imbalanced after the immediate deletion of a node as a part of standard remove map operation. How should I start and what should I use to ...
1
vote
0answers
17 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 ...
0
votes
1answer
29 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
vote
1answer
160 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.
2
votes
1answer
124 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. ...
0
votes
1answer
22 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
1answer
32 views

Deletion from 2,3,4 tree

Consider a 2,3,4 tree like so, ...
1
vote
1answer
294 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-...
4
votes
0answers
83 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 ...
0
votes
0answers
187 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
vote
1answer
66 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
1answer
68 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 ...
0
votes
0answers
31 views

Why are red-black trees still preferred over weak AVL trees [duplicate]

Both have a maximum height of 2*logn WAVL trees have a maximum height of 1.44*logn if built using only insertions. If built using both insertions and deletions, then inserts will tend to restore the ...
0
votes
0answers
15 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-...
0
votes
1answer
83 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 ...
3
votes
1answer
305 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 ...
1
vote
1answer
47 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 ...
0
votes
0answers
89 views

Calculate order of Leaf and Non-leaf nodes of B tree

Consider a disk with a block size $B=512$ bytes. A block pointer is $P=6$ bytes and a record pointer is $P_R=7$ bytes. A file has $r=30000$ records of fixed length, with a record size of $r=116$ ...
0
votes
0answers
60 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 ...
0
votes
1answer
105 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 ...
0
votes
1answer
575 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 ...
-1
votes
1answer
151 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 ...
0
votes
1answer
223 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: ...
1
vote
1answer
31 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-...
0
votes
0answers
26 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?
2
votes
0answers
258 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 ...
1
vote
1answer
55 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 ...
0
votes
1answer
383 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.
0
votes
1answer
1k 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_{\...
6
votes
0answers
305 views

Voronoi diagram. Status structure in Fortune's Algorithm

I'm trying to implement the Fortune's Algorithm, however I can't quite figure out how the status structure should be implemented. The following is extrapolated from my Computational Geometry book. ...
3
votes
1answer
231 views

AVL tree partition

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$, ...
0
votes
0answers
736 views

AVL Tree: Proving minimum number of nodes

I'm practicing for my final exam, and I'm a bit confused. Here's the question: Let M(h) be the minimum number of nodes in an AVL tree of height h. In such a tree, it can be shown that $M(h) = M(h-...
1
vote
0answers
68 views

Advantage of bulkloading in a B-Tree

https://en.wikipedia.org/wiki/B-tree#Initial_construction Currently I know of 2 ways for building a B-Tree : bulkloading and just inserting key after key. In the wiki example the keys are sorted, ...
1
vote
0answers
442 views

Day-Stout-Warren algorithm for balancing BST. How does vine to tree work?

I was trying to understand the dsw algorithm for balancing a binary search tree in-place using this virgina tech page. The wikipedia page and vt page are more or less similar. I am having a hard time ...
1
vote
1answer
243 views

BVL Balanced Tree

I have an issue about proving the next problem: Let's define a BVL tree, which is a binary tree, who satisfied the feature that the difference between the heights of the children of a node, is at ...
2
votes
2answers
105 views

Prove that given a number we can find whether there're 2 elements in a red/black tree that their sum equals that number in $\Theta(n)$ time

Prove that given a number we can find whether there're 2 elements in a red/black tree that their sum equals that number in $\Theta(n)$ time and constant space. The original problem appears here, ...
1
vote
0answers
85 views
3
votes
1answer
62 views

Efficient search algorithm for a monotonic boolean array wherein the probability of target's location is available apriori

A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$. $$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in ...
3
votes
1answer
233 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 ...
0
votes
1answer
138 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: ...
0
votes
1answer
279 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 ...
4
votes
1answer
278 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,...
0
votes
1answer
142 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 ...
2
votes
1answer
175 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, ...
4
votes
0answers
176 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 ...
1
vote
0answers
281 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 ...
1
vote
1answer
487 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 ...
3
votes
1answer
455 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 ...