# Questions tagged [search-trees]

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

272 questions
Filter by
Sorted by
Tagged with
236 views

### Starting BFS at s and t

INPUT: undirected graph, s, t OUTPUT: connectivity of s and t I perform BFS on s AND t, each taking turns to make one traversal. When a vertex exists in both s and t's BFS tree, we can assume it is ...
540 views

### Optimal Binary Search Trees Knuth

Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica 1 (1): 14–25,doi:10.1007/BF00264289 Please have a look at this paper, specifically page 18 in which he tries to prove his ...
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, ...
50 views

47 views

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

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 ...
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 ...
78 views

### Complexity of BST [duplicate]

I have the following pseudo-code for printing all nodes of a BST : ...
49 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 ...
984 views

### How to do high performance string matching when comparing unordered sets of tokens [closed]

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 ...
1k views

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(... 1answer 70 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 ... 1answer 567 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 ... 1answer 327 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 ... 1answer 759 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 intersections.... 1answer 510 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 ... 1answer 727 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 ... 1answer 294 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 ... 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/... 2answers 341 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 ... 1answer 120 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 ...
97 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 ...
40 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 ...
147 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 ...