Questions tagged [balanced-search-trees]

The tag has no usage guidance.

28 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
452 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. ...
4
votes
0answers
214 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 ...
3
votes
0answers
234 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 ...
2
votes
0answers
34 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 ...
2
votes
0answers
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 ...
2
votes
0answers
363 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 ...
2
votes
0answers
408 views

Time complexity of the operations on a b-tree if deletion is performed by marking nodes inactive

I'm given a B-tree where the delete-operation is not implemented, but instead keys are deleted using tombstones (so they stay in the tree, but are marked as deleted). Now when at least 90% of all keys ...
2
votes
0answers
81 views

Can the right childs of a node in an AVL tree be both balanced after an insert and need rebalancing?

I was trying to come up with a case where one would need rebalance the following case in an AVL tree: I think that case impossible to happen during an insert. It seems to me that its impossible to ...
1
vote
1answer
45 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 ...
1
vote
1answer
254 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.
1
vote
0answers
17 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 ...
1
vote
0answers
36 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 (...
1
vote
0answers
104 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
690 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
0answers
130 views
1
vote
0answers
402 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
0answers
1k views

Red Black Tree deletion algorithm (CLRS, 3rd edition) : Deleting the root

I have been following the third edition of Introduction to Algorithms (by Cormen, Rivest et al), and have been studying the deletion algorithm for red black trees. However, I am confounded at the ...
0
votes
0answers
10 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?
0
votes
0answers
40 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 ...
0
votes
0answers
60 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}$ ...
0
votes
0answers
305 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) ...
0
votes
0answers
22 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
0answers
81 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
0answers
32 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?
0
votes
0answers
127 views

Augment B+ Tree to support given search query

Given a B+ tree with M=3. We assume that the tree is static and it is not necessary to update the B+ tree. Also we know that all key-value pairs are stored in the leaves of the B+ tree. Internal nodes ...
-1
votes
1answer
85 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
votes
1answer
397 views

Priority Queue using an AVL tree, run time question

This is a question I want to answer in pseudocode: This is regarding a sort of priority queue using an AVL tree. I initialize a global variable (named GLOB) with 0. I receive from the user an input ...
-1
votes
1answer
95 views

Lookup complexity in B-trees [Database]

Given that: B = n/R blocks in the file 2d index records per block (blocking factor): 2d > R an extra block access from the index to the datafile I am not able ...