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
1
vote
1answer
429 views

Data structure for range-value-sum

I have to be able to perform insert, delete, range-value-sum, and range-2-max-values with a data structure. Range-value-sum(xl,xr): with a range [xl,xr] (for a range query), it reports the sum of ...
0
votes
2answers
427 views

Elements in a less than a value in a subarray

Let A be an fixed array of size n. Q(i,j,k) is number of elements from A[i] to A[j] which are less than k. Currently I am using segment tree with each node containing sorted array of leaf elements. ...
2
votes
1answer
2k views

Smallest(k) in red-black tree. How is it O(logn)?

Is it the same as find minimum for a binary search tree? I know recoloring runs in O(logn) and rotations are O(1). Even if we are wanting it to find the 'k-th' smallest key in the red-black tree. ...
1
vote
1answer
146 views

How can one search in O(log n) time in a red-black tree?

How does the search operation for a red-black tree work and how does it take $O(\log n)$ time, where $n$ is the number of items? I know a red-black tree takes $O(\log n)$ recolorings and $O(1)$ ...
0
votes
1answer
53 views

Searching for an item over a non-uniform query distribution

If I have a static set of $n$ items in a database that are all queried with uniform probability it makes sense to put them in a binary search tree. This way any given search will take, on average, $O(\...
0
votes
0answers
186 views

Implementing BTrees without pointers

I am trying to implement a BTree in a pointer-free language as a proof-of-concept. However, a question came to my mind: every time I need to split a node, I need to do a deep copy of all the nodes in ...
3
votes
2answers
393 views

Term for binary search tree using hashes?

I was looking for a way to easily store and access a symbol table using the least memory and code as possible and I went with a BST. Symbols, however, tend to be defined in order as in foo0, foo1, ...
3
votes
2answers
6k views

B-Tree and how it is used in practice

I understand what a B-Tree is (I already implemented a B-Tree in Java with insert and delete methods that preserve the invariant). However I do not understand exactly how it is used for example for ...
1
vote
1answer
126 views

Algorithm for creating a directed graph using flat data input [closed]

Given flat data like this: ...
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 ...
-3
votes
1answer
164 views

Implement “from” function for AVL Tree java

I posted this same question on stackoverflow but I think it might be better suited here as I am having trouble with coming up with an algorithm with O(log(n)) running time. Question: I am completely ...
-1
votes
2answers
172 views

Is there only one optimal BST?

as i read some material about Optimal BST, i ran into a trouble. for following key i find two optimal BST with Average Cost = 30. 1 optimal BST using Dynamic programming Algorithm and 1 by hand ! ...
-3
votes
1answer
1k views

Building a Red Black tree out of a sorted array [closed]

If I have a sorted array of size $n$, can I build a Red Black tree out of it in $O(n)$ time in a different algorithm rather than splitting the tree in half every time or the straightforward way that ...
6
votes
1answer
8k views

(AVL Trees) What is the maximum possible difference between the number of nodes in the root node's subtrees? [duplicate]

Question: If an AVL tree has height h (assume h ≥ 2), what is the maximum possible difference between the number of nodes in its two subtrees? Prove your answer. Your answer should not use big-Oh or ...
0
votes
1answer
621 views

Top Down Insertion in a B Tree

I have a B-Tree of order 5. So the keys are between $\lceil n/2 \rceil- 1 \leq keys \leq n - 1$ and children are between $\lceil n/2 \rceil \leq children \leq n $. Am I doing it right? So a full node ...
0
votes
1answer
169 views

red black tree and 2-3-4 tree isomorphism

Are all cases of addition and removal in 2-3-4 trees isomorphic to cases of addition and removal in red black trees?
2
votes
2answers
1k views

Minimising height of a 2-3-4 tree

I'm wondering how a set of keys could be assigned to nodes in a 2-3-4 tree in order to minimize the height of the tree? Does the sequence of insertion matter with 2-3-4 trees?
3
votes
0answers
484 views

Finding a successor in a binary search tree in $O(1)$ [closed]

In my algorithms course I have learned about the binary search tree and its functions add, find and remove. I have also learned about how to find the successor and the predecessor in a balanced binary ...
1
vote
1answer
191 views

Inserting a sentence into search trees

Let's say you have the following sentence: "This is my first cs question posted here". How would I go about inserting the sentence into a search tree. Do I assign each word a number value and perform ...
2
votes
1answer
704 views

kd-tree stores points in inner nodes? If yes, how to search for NN?

The link in wikipedia about kd-trees store points in the inner nodes. I have to perform NN queries and I think (newbie here), I am understanding the concept. However, I was said to study Kd-trees ...
3
votes
2answers
369 views

Why should leaf nodes in a red-black tree be black?

From the property of Red-Black Trees we know that: All leaves (NIL) are black. (All leaves are same color as the root.)(Comren et al "Introduction to Algorithms") But what is the reason that we ...
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
0answers
47 views

Binary search tree with $n$ internal vertices [closed]

How can we prove a binary search tree with $n$ internal vertices has height $h = \lceil \log(n+1) \rceil$?
-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 ...
1
vote
0answers
159 views

LLRB Tree How to prove if left and left of left node are black, then this node must be a red node?

Im learning the delete operation on Left-leaning Red Black Tree invented by Prof. Sedgewick. In delete operation, a node could be only deleted from a 3-node or a 4-node but 2-node. In order to ensure ...
1
vote
1answer
47 views

Understanding expected time bound for unsuccessful search in R-way tries

As per Tries slides (page 17) from Algorithm 4th edition book by Robert Sedgewick, the asymptotic expected runtime for an unsuccessful search in $R$-way tries miss is $O(\log_R N)$. Can someone please ...
-1
votes
1answer
302 views

Case distinction in B-tree deletion

Here is how deletion in B-trees is described: If the key k is in node x and x is a leaf, delete the key k from x. If the key k is in node x and x is an internal node, do the following. a) ...
1
vote
1answer
64 views

Doesn't post-order traversal require subtrees to be evaluated separately?

Consider this tree: If I traverse it using post-order, I'd start at B (as it is the leftmost leaf) and that's where my misunderstanding begins. I know B is the first and A will be the last node in ...
5
votes
3answers
15k views

Artificial Intelligence: Condition for BFS being optimal

It is said in the book Artificial Intelligence: A Modern Approach for finding a solution on a tree using BFS that: breadth-first search is optimal if the path cost is a nondecreasing function of ...
1
vote
1answer
3k views

Why is Iterative-deepening A* optimal, even without monotonicity?

Why is it that Iterative-deepening A* is optimal, even without monotonicity? How can I be sure that the first goal reached is the optimal one?
3
votes
1answer
5k views

Updating an AVL Tree Based On Balance Factors

I'm looking at the lecture review for one of my computer science classes and I'm having trouble coming up with an answer. Could someone help me work through it? Background: Let the balance factor ...
2
votes
2answers
3k views

Does inserting and immediately removing a node change a red-black tree?

I have the following problem: Does inserting a node into a red-black tree and then immediately deleting it always result in the original tree? Prove that it does or give a counter-example if it ...
3
votes
0answers
371 views

Expected depth of modified kind of treap

If we have $n$ elements $s_1, \dots, s_n$ and build a kind of treap (tree-heap) out of it. Each $s_k$ has a priority, which is an integer in $\{ 1, 2, 3 \dots, \lceil \log n \rceil\}$. Since the ...
1
vote
1answer
372 views

finger search on a red black tree

I'm having trouble finding materials on what 'finger search' is, in the context of a red black tree. Even Wikipedia has a very short page about that, could you refer me or explain what kind of search ...
10
votes
3answers
4k views

What data structure would efficiently store integer ranges?

I need to keep a collection on integers in the range 0 to 65535 so that I can quickly do the following: Insert a new integer Insert a range of contiguous integers Remove an integer Remove all ...
5
votes
2answers
7k views

Joining two red-black trees

I have two red-black trees $T_1$ of black height $H_1$ and $T_2$ of black height $H_2$ such that all the nodes $N$ belonging to $T_1$ are less than (in value) all the nodes $N$ of $T_2$ and a key $K$...
2
votes
1answer
528 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 ...
4
votes
2answers
118 views

Where are M-Trees applied in practice?

My similarity search seminar topic are M-trees. I would like to give some examples about where they are practically applied, but I can't find anything googling. Does someone know if M-trees are ...
4
votes
3answers
155 views

“Last Come => More Relevant” data structures

As I think of data structures I studied and dealt with, they are all optimized to retrieve/put a random element, to perform optimally based on unspoken assumption that each element has equal odds of ...
6
votes
2answers
153 views

Binary Search Tree: Replace $k$ min elements with their average

Given a valid binary search tree whose keys are unique real numbers, and a set of $k$ pointers to the $k$ minimum elements in the tree, will the BST property be maintained if I replace all $k$ ...
-1
votes
1answer
156 views

Find node with key of at least n in a binary search tree

Working on a project for my Data Structures class. I've implemented a Red/Black tree in Java. One of the operations required of the data structure is "find a node which has a key of at least n". The ...
0
votes
2answers
1k views

Worst case scenario in binary search tree retrieval

Well, i have a binary search tree $T$ that is equilibrated by height witch has $2^d+c$ nodes ($c<2^d$). What is the number of comparisons that will occur in the worst case scenario, if we ask ...
5
votes
1answer
421 views

van Emde Boas tree: why store max recursively?

In both CLRS (third edition) and Erik Demaine's lecture, the van Emde Boas tree is defined to store max but not min recursively. ...
1
vote
1answer
322 views

Sequential hash tree traversal

A lot of articles say that hash tree traversal cost to any randomly chosen leaf is $\mathcal{O}(\log_2 N)$ ($N$ is a number of leafs) and that is right. If we have a tree of 8 leafs it will take us at ...
2
votes
1answer
187 views

Prove that inserting $n$ sorted values in to an AVL using AVL insertion is $\Theta\left (n \log \left ( n \right ) \right )$

We're asked to prove the above mentioned lemma but I having a hard time proving this rigorously. We did prove that given $n$ values AVL's height is $\Theta\left (\log \left ( n \right ) \right )$ So ...
7
votes
4answers
1k views

Is there a binary tree structure with fast access to recently accessed elements and worst $O \left( \log n \right )$ complexity?

The idea of splay trees is very nice as they move frequently accessed elements to the top, which can gain a considerable speed up in many applications. The drawback is that in the worst case an ...
7
votes
1answer
470 views

Is there a binary search tree datastructure which can avoid becoming badly weight-balanced?

This is a follow-up question of "Not all Red-Black trees are balanced?" and "AVL trees are not weight-balanced?".$\def\le{\leqslant}\def\ge{\geqslant}$ Definition: For a rooted tree $T$ and a ...
0
votes
2answers
744 views

Did I correctly prune this min-max search tree using alpha-beta pruning?

I am studying some old past test questions. Is this search tree correctly pruned?
3
votes
2answers
1k views

Finding no. of leaf nodes for each node in a BST

A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is $\qquad \min(\#\text{...
5
votes
2answers
2k views

AVL tree with fixed height and as few elements as possible

I have been reading about AVL trees, at the moment I'm trying to figure out how to determine the height of a tree and how to draw an AVL tree of some height with minimum number of elements. In a ...