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

learn more… | top users | synonyms

0
votes
0answers
4 views

Detecting junctions algorithmically

With route finding algorithms, we get the children of each node. So for example, an A* search on google maps at each point in the search would know which roads can be the successor to the current ...
0
votes
1answer
22 views

A BST can be broken by accessing one of its nodes, how can I always make sure this happens? [on hold]

I have an assignment that asks for this. So I am not looking for the answer itself but a hint on how to find a value that will always break the BST condition by myself. If I have access to any node N ...
0
votes
3answers
32 views

Complexity of BST

I have the following pseudo-code for printing all nodes of a BST : ...
0
votes
0answers
29 views

Finding and Grouping like children

I'm working on a dependency managemen solution for a JavaScript. I'm trying to find the best pattern for grouping similar items in a graph into their own 'modules'. Given a dependency tree like ...
1
vote
1answer
32 views

How to do high performance string matching when comparing unordered sets of tokens

This is the problem: I have some strings stored in the database. Each of the strings can be seen as a set of tokens separated by comma with no repetition (I mean a token cannot appear more than one ...
1
vote
1answer
38 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 ...
4
votes
1answer
49 views

How can I calculate tree sizes to “stretch up” a finger tree?

I've been working on implementing an efficient Cartesian product operation (actually the <*> operation, but it amounts to about the same thing) for sequences ...
1
vote
1answer
30 views

Supporting queries for finding how many intervals in a dynamic set of 1D intervals contain a given point

You want to create a data structure that can store 1 dimensional intervals and also support the query for finding the total amount of intervals intersecting a given point. One solution would be for ...
2
votes
1answer
51 views

Use AVL trees instead of Chord algorithm for Distributed Peer to peer Hash tables

In distributed systems we use the Chord algorithm to create a p2p distributed hash table. While this algorithm is very useful and efficient wouldn't it be better if we used an AVL tree? Chord ...
0
votes
1answer
36 views

Why is the orthogonal line segment intersection algorithm $O(n\log n+R)$ instead of $O(n\log n + Rn)$?

In the same lecture notes without providing many details it says that the complexity of the algorithm which uses a balanced search tree is $O(n\log n+R)$ where $R$ is the total amount of ...
1
vote
2answers
39 views

Implementing an interval tree using arrays?

Is it possible to create an interval tree using an array instead of the traditional pointer method? I know that for segment trees this is commonly done where the children of any element with index i ...
1
vote
0answers
75 views

Running time analysis of a segment tree

Can someone provide an analysis of the update and query operations of a segment tree? I thought of a way which goes like this - At every node, we make at most two recursive calls on the left and ...
0
votes
1answer
26 views

Asymptotic runtime for querying an interval tree

Suppose that we have an array of size n and we want to build an interval tree for all possible ranges that can be created inside this array. So in our leafs we have ...
4
votes
1answer
154 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: ...
2
votes
2answers
55 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 ...
2
votes
1answer
31 views

Proof that a node N balanced binary search tree has $2^i - 1$ children where $i$ is the position of the first 1-bit in N, starting from 0

I was binary indexed trees and I came across this article. One part of the justification was the following: Given that the (binary search tree) tree is perfectly balanced, a node N will have ...
1
vote
1answer
38 views

Wouldn't a Red-Black tree fix up after insertion mess up the BST ordering?

I've been reading about fixing up after an insertion into a red black tree. (http://web.cse.ohio-state.edu/~lai/2331/0.Red-Black%20Trees.pdf) The most surprising part is not that there are 6 things ...
2
votes
0answers
31 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
37 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 ...
0
votes
2answers
93 views

Is randomly building a BST different from random sampling whole trees?

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
58 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
43 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
vote
1answer
46 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
85 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
18 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
42 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
155 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
223 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
47 views
1
vote
2answers
80 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
61 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
62 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
140 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
721 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
53 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
26 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
61 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
87 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
25 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
108 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
93 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
343 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
51 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
57 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
45 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
418 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
427 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?