# Questions tagged [balanced-search-trees]

The tag has no usage guidance.

140 questions
Filter by
Sorted by
Tagged with
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 ...
1 vote
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
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
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
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
54 views

2k views

### Deletion from 2,3,4 tree

Consider a 2,3,4 tree like so, ...
• 272
1 vote
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
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
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 vote
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?