Questions tagged [search-trees]

Questions about search trees, a class of data structures used for storing sorted data for efficient access.

Filter by
Sorted by
Tagged with
30
votes
2answers
7k views

Not all Red-Black trees are balanced?

Intuitively, "balanced trees" should be trees where left and right sub-trees at each node must have "approximately the same" number of nodes. Of course, when we talk about red-black trees*(see ...
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, ...
10
votes
1answer
15k views

Proof that a randomly built binary search tree has logarithmic height

How do you prove that the expected height of a randomly built binary search tree with $n$ nodes is $O(\log n)$? There is a proof in CLRS Introduction to Algorithms (chapter 12.4), but I don't ...
9
votes
1answer
5k views

Range update + range query with binary indexed trees

I am trying to understand how binary indexed trees (fenwick trees) can be modified to handle both range queries and range updates. I found the following sources: http://kartikkukreja.wordpress.com/...
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 ...
8
votes
3answers
646 views

How to count in linear time worst-case?

This question and this question got me thinking a little bit. For sorting an array of length $n$ with $k$ unique elements in $O(n + k \log k)$, we need to be able to store counts of values in the ...
16
votes
2answers
9k views

Colour a binary tree to be a red-black tree

A common interview question is to give an algorithm to determine if a given binary tree is height balanced (AVL tree definition). I was wondering if we can do something similar with Red-Black trees. ...
14
votes
3answers
1k views

Memoization without array

In Cormen et al.'s Introduction to algorithms, section 15.3 Elements of dynamic programming explains memoization as follow: A memoized recursive algorithm maintains an entry in a table for the ...
9
votes
1answer
6k views

Time Complexity proof for Segment Tree implementation of the ranged sum problem

I understand that segment trees can be used to find the sum of sub array of $A$. And that this can done in $\mathcal{O}(\log n)$ time according to the tutorial here. However I'm not able to prove ...
9
votes
3answers
4k views

Logarithmic vs double logarithmic time complexity

In real world applications is there a concrete benefit when using $\mathcal{O}(\log(\log(n))$ instead of $\mathcal{O}(\log(n))$ algorithms ? This is the case when one use for instance van Emde Boas ...
5
votes
2answers
2k views

Balance factor changes after local rotations in AVL tree

I try to understand balance factors change after local rotations in AVL trees. Given the rotate_left operation: ...
3
votes
1answer
7k views

What is the time complexity of calling successor $n$ times during tree traversal?

According to some sources, the time complexity of finding the successor of a node in a tree is $O(h)$. So, if the tree is well balanced, the height $h=\log n$, and the successor function takes time $O(...
2
votes
2answers
13k views

Nim game tree + minimax

Problem : Two players have in front of them a single pile of objects, say a stack of 7 pennies. The first player divides the original stack into two stacks that must be unequal. Each player ...
7
votes
2answers
1k views

Can we do better than $O(n\log n)$ building a balanced binary tree?

I'm (foolishly it turns out) confident that the answer to this question is no. So why am I asking? Because Dr. Aleksandar Prokopec at EPFL in his parallel programming course introduces a data-...
5
votes
3answers
4k views

Compute height of AVL tree as efficiently as possible

Given an AVL tree, I want to compute its height as efficiently as possible. $\newcommand{\bf}{\text{bf}}\newcommand{\height}{\text{height}}$ Each node of an AVL tree stores its balance factor ($\bf$),...
3
votes
1answer
886 views

Binary tree To Red-Black tree

I have a question regarding the solution provided by Karolis Juodelė. Given in this question; Colour a binary tree to be a red-black tree Black = black nodes, white = red nodes So for this tree when ...
2
votes
1answer
866 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 ...
2
votes
2answers
1k views

Does the rebalancing propagate upwards only to update the height of the nodes in an AVL tree?

I was studying AVL trees and was wondering if the only reason one propagates upwards to the node in an insert is to change the height. It seems to me that rebalancing does not recursively propagate ...
2
votes
2answers
2k views

Why do we need double-rotations to rebalance AVL trees?

I was reading about AVL tree rebalancing from Behrouz Forouzan's book. The book first defines Left High and Right High tree: Left High (LH) tree is a tree tree with the height of the left ...
1
vote
1answer
647 views

Reb-black tree amortized cost of the rebalancing

I've read in different sources that the amortized cost of a red-black tree rebalancing is constant (at least during the tree creation using only insertions). How can it be proved?
1
vote
1answer
2k views

Every AVL tree may be red black tree

I proved by induction that every AVL tree may be colored such that it will be red black tree. The problem is that I can't see an error in my proof. Look at my proof. Induction for height. Let's ...
0
votes
1answer
285 views

Can I speed up Insertion Sort by using a tree for finding insertion positions?

I want to implement an insertionSort-algorithm. Let's say I have these pseudocode. ...
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 ...
4
votes
1answer
53 views

Nodes in a binary search tree that span a range

I have a binary search tree of height $h$ with an integer in each leaf. I also have a range $[\ell,u]$. I want to find a set of nodes that span the range $[\ell,u]$, i.e., a set $S$ of nodes such ...
3
votes
1answer
140 views

Can ropes (AVL trees) be interned?

Can AVL trees be interned for fast equality comparison? Is there work on interning data-structures or can you show that this cannot be done in better than $O(n)$ time? I recently implemented a rope ...
2
votes
0answers
70 views

Data structure & algorithms for super-interval queries on intervals with small integer ends

I would like to have an online data structure that supports inserting an interval, and given a query interval $I_q=[l_q,h_q]$ answer if some interval of the data structure is contained in $I_q$, i.e. ...
2
votes
1answer
527 views

How does insertion work in an AVL tree?

From the above image, while trying to maintain an AVL tree data structure, how would the tree look after inserting the value 10? Also, if anyone has any suggestions or simple method of rotating, feel ...
2
votes
1answer
136 views

Searching for multiple partial phrases so that one original phrase can not match multiple search phrases

Given a predefined set of phrases, I'd like to perform a search based on user's query. For example, consider the following set of phrases: ...
1
vote
0answers
113 views

Calculating maximum number of splits that can occur during insertion of $n$ keys in B Tree of order $m$

I can calculate this by trying out manually inserting $n$ keys in $m$ order B Tree as follows: Assume median to be selected for split be left biased. That is $m/2$. For example, if $m=4$, then a ...
1
vote
1answer
51 views

Help in geometrically understanding “Linear Decision Trees”

In the words of (http://www.cs.utah.edu/~suresh/5962/lectures/17.pdf, section 17.2), "Each $f(x)$ can be interpreted as defining a hyperplane in $R^n$. Thus, tracing a path through the tree computes ...
1
vote
1answer
275 views

Can you have three consecutive black nodes in red-black search tree?

Suppose I am making a red-black search tree, and in my right subtree, I have a black node, then a red node, and it has two black children, the black children further black childrens. As such a lemma ...
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, ...
0
votes
0answers
54 views

Can't reach a balance in a DFS search?

Below is a question based on CLRS, about using an algorithm to reach a balance between a group of friends. I figured the best way to do this, is through the use of a DFS algorithm. Below the question ...
-1
votes
1answer
985 views

AVL Trees - Maintaining Closest Pair information on a Delete [duplicate]

In the accepted answer to my question Data Structure For Closest Pair Problem, I do not see why deletion works. Let's say (x, y) are the closest pair before the delete. If the node to be deleted is ...