Questions tagged [balanced-search-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
1answer
118 views

State of the art time complexity for getting (tree) descendants by type/attribute

Let's say I have a tree comprised of nodes where each node is of some type (T), where there is a known/fixed number of types (i.e. similar to attributes in an xml document), and where a node can only ...
3
votes
1answer
469 views

Root Color of a Black Red Tree

It is required that, in a black red tree, the color for the root is always black. However, wikipedia argues that this rule can be omitted as a red root can always be changed to black but not vice ...
1
vote
1answer
127 views

Why not use large $k$ in a $k$-ary tree?

Obviously binary trees are great because of $O(\log_2 n)$ search, inserts, and deletes in best case. To "maximize" occurrence of best case, we can use self-balancing trees like red-black trees, AVLs, ...
6
votes
3answers
7k views

Average depth of a Binary Search Tree and AVL Tree

My professor recently mentioned that the average depth of the nodes in a binary search tree will be $O(log(n))$ where $n$ is the amount of nodes in the tree. I ended up drawing out a bunch of binary ...
5
votes
1answer
2k views

Can a Red Black tree be constructed of only black nodes using RB insert only?

I am trying to construct a red black tree out of only black nodes. I know it is possible getting it after some deletions but I am trying to construct one only via insertion orders. Is it possible? I ...
3
votes
3answers
3k views

Memory usage of a BST or hash table?

I would like to use a data structure allowing fast access, either a balanced binary search tree (BST) for $O(\log n)$ access time or an open hash table for constant access time. 1) What is the exact ...
1
vote
1answer
786 views

Bounds on the number of rotations in the insertion operation of a Red Black Tree

I am having some trouble understanding why people say that contrary to what happens with AVL trees, there is a bound on the number of rotations occurring in an insertion with a Red Black Tree. From ...
1
vote
0answers
16 views

Saving a pointer to the n/4 node in AVL tree [duplicate]

I have an AVL Tree which every node has a filed with a key which is an integer. I need to save a pointer to the Minimum , Maximum and the $\left \lfloor \frac{n}{4} \right \rfloor $ nodes. the first ...
2
votes
1answer
863 views

Traversals from the root in AVL trees and Red Black Trees

We all know that for insertion() operation in AVL tree following can happen: We traverse down the tree from root to appropriate node and there insert the key and then for maintaining height balance ...
5
votes
1answer
484 views

Why aren't tries generally used?

To store say integers (positive), we prefer to use red black BSTs. I have never seen a explicit use of a trie anywhere to store numbers. I believe we can convert numbers to string and store them in ...
2
votes
2answers
410 views

Finding median weights in all paths of an AVL tree with weighted nodes

I need some help with proving the complexity of the following problem (I'm new here, so please excuse my "newbie-ness") Given: an AVL tree with keys: $1,2,..,n$, such that each node $i$ in the tree ...
0
votes
0answers
152 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 ...
6
votes
4answers
381 views

Order-preserving update of a sublist of a list of mutable objects in sublinear time

Description Say I have a source list like: ["a","b","c","d"] and want to run a capitalization filter so if I change, "b" to <...
9
votes
2answers
3k views

Split in AVL tree with complexity $O(\log n)$

Can the split operation be implemented for AVL trees with complexity $O(\log n)$? I'm interested in links to articles or any specific information about this subject. The split operation divides the ...
49
votes
4answers
12k views

Why are Red-Black trees so popular?

It seems that everywhere I look, data structures are being implemented using red-black trees (std::set in C++, SortedDictionary ...
8
votes
2answers
5k views

A median of an AVL. How to take advantage of the AVL?

Here is the source of my question. Given a self-balancing tree (AVL), code a method that returns the median. (Median: the numerical value separating the higher half of a data sample from ...
1
vote
1answer
1k views

Given a Red-Black Tree of n keys, is there a way to quickly determine if a red-node exists?

My best attempt at a specific case of the problem where $n =$ 256: For a specific case that a RB tree has 256 nodes, we can use the RB tree theorem to deduce that the height of the tree $h \leq 2*lg(...
3
votes
2answers
343 views

Balancing a Binary Search Tree

I was reading about binary search trees on it's Wikipedia article. I was a little confused by this image. Why is it that the right branch to the head node does not have a sub-tree? I understand why it ...
6
votes
4answers
4k views

Don't understand one step for AVL tree height log n proof

I came across a proof that the an AVL tree has O(log n) height and there's one step which I do not understand. Let $N_h$ represent minimum number of nodes that can form an AVL tree of height h. Since ...
22
votes
1answer
4k views

AVL trees are not weight-balanced?

In a previous question there was a definition of weight balanced trees and a question regarding red-black trees. This question is to ask the same question, but for AVL trees. The question is, ...

1 2 3