Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [balanced-search-trees]

The tag has no usage guidance.

116 questions
Filter by
Sorted by
Tagged with
1k views

non-binary self balancing tree

I'm looking for a tree data structure that allows to keep the tree balanced in high (minimum high as possible). I mean, suppose a tree where: each node has a parameter k that is the maximum number ...
29 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 ...
18 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 ...
11 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?
58 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 ...
93 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}$ ...
55 views

89 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 ...
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?
135 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 ...
100 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)?
252 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 ...