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

learn more… | top users | synonyms

1
vote
0answers
25 views

How to find number of occurences of specific distances in binary (search) trees?

I want to calculate the amount of tree structures that have a given maximal distance between two nodes given an amount n of nodes (or keys). E.g. with ...
0
votes
0answers
25 views

Graph Traversal: Upper and Lower Bounds

In my Artificial Intelligence class we are going over upper and lower bounds in regards to searching a tree, given a state space. From my understanding, a lower bound is also known as a depth-bound ...
1
vote
1answer
41 views

Random Binary search tree

What is the difference between a randomly built binary search tree (using n keys )and choosing a binary search tree (of n key) from a random distribution
1
vote
1answer
40 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
35 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. ...
-1
votes
0answers
13 views

AVL Tree Augment [duplicate]

Minimum_(K): Return element of k with smallest key. If I were to describe, how do i augment the AVL tree so that it supports this minimum_(k) operation in constant (1) time?
-2
votes
0answers
15 views

Number of nodes in a B-Tree

How many nodes does a resulting B-Tree(min degree 2) have if I insert numbers from 1 to n in order? I tried inserting nodes from 1 to 20 there was a series for the number of nodes coming but i could ...
1
vote
1answer
31 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
82 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
16 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, ...
0
votes
0answers
39 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 ...
2
votes
2answers
148 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, ...
0
votes
2answers
121 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
39 views
1
vote
2answers
72 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 ...
-4
votes
1answer
43 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 ...
-1
votes
2answers
56 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
82 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 ...
2
votes
1answer
168 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
48 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
25 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?
1
vote
2answers
57 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
83 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
22 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 ...
1
vote
1answer
89 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 ...
2
votes
2answers
86 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
38 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
33 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
304 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
41 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
31 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
55 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. ...
1
vote
1answer
44 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 ...
2
votes
2answers
301 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
367 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?
0
votes
0answers
135 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 ...
1
vote
1answer
160 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
109 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
133 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 ...
6
votes
3answers
582 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 ...
4
votes
2answers
694 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 ...
2
votes
1answer
216 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, ...
5
votes
2answers
100 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
121 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 ...
5
votes
2answers
126 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
100 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
289 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 ...
4
votes
1answer
167 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
132 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
87 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 ...