Questions tagged [search-trees]
Questions about search trees, a class of data structures used for storing sorted data for efficient access.
268
questions
1
vote
0answers
18 views
Scapegoat Trees: Why are they only loosely a-height-balanced?
From Wikipedia:
Even a degenerate tree (linked list) satisfies this condition if α=1,
whereas an α=0.5 would only match almost complete binary trees.
A binary search tree that is α-weight-...
5
votes
0answers
125 views
Time Complexity for Nearest Neighbor Searches in kd-trees
Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof.
In order to calculate the average number of ...
2
votes
1answer
44 views
Finding the shortest time to go from one stop to another stop in a train system with many train lines with connection stations
So I was thinking after discussing with my friend the other day, how would I use something like breadth-first or depth-first search to find the fastest time to go from one station to another station ...
0
votes
2answers
48 views
Range Query with conditions
Suppose I have an $N$ length integer array of pairs of the type $[value, key]$. Now, I need to query for range sum. Query is of the type : $l, N, x$ meaning I have to sum up all the $value$ in the ...
3
votes
1answer
22 views
Given a set of intervals $(I_n)_n$ contained in $[0, L]$, compute the longest interval in $[0, L]$ which has empty intersection with all $(I_n)_n$
Let be $(I_n)_n$ a set of $p$ intervals each contained in $[0, L]$ for $L \geq 1$.
I define $(J_n = [a_n, b_n])_n$ the set of intervals which have empty intersection with $I_n$ for all $n \in [[1, p]]...
0
votes
0answers
46 views
How Segment trees are used to answer interval stabbing query?
Can anybody explain to me how segment trees are used to answer interval stabbing queries? I have searched and searched and only come with the beginning of the line.
From my understanding I need to ...
0
votes
0answers
23 views
AVL Tree confusion
I have some confusion with regards to AVL trees and the heights of various subtrees.
When initially reading the overview of the algorithms purpose(to keep the tree balanced) I thought it put limits ...
1
vote
1answer
26 views
What is the minimal degree $d$ required for a B tree with $44*10^6 $ keys so that it's height is less than or equal to $5$
What is the minimal degree $d$ required so a B - tree with $44*10^6$ keys will have a height $h$, such that $h\leq 5$
My attempt was to build the tallest tree possible with minimum degree $d$ and $n =...
1
vote
1answer
15 views
Searching a hierarchy for progressive node criteria
In our organization we have various business units that organize their data in different ways. The folder structure can vary, but they abide by business unit practices when making backups etc.
I am ...
0
votes
0answers
24 views
Breadth-first traversal: difference between generation and expansion
The question here is to find a path from A(rad) to B(ucharest). I'll be using the initials of the cities in the picture instead of their full names.
Some ground-rules: we're traversing in ...
2
votes
0answers
45 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. ...
0
votes
0answers
11 views
Depth of an R-tree, given $m$, $M$ and number of elements
Simply: what is the theoretical maximum, minimum or expected depth of an R-tree given $m$ minimum $M$ maximum elements in a node, with $N$ amount of nodes?
0
votes
1answer
127 views
UCT (Upper Confidence bounds applied to Trees)
For UCT (Upper Confidence bounds applied to Trees), why If given infinite time and memory, UCT theoretically converges to Minimax. ?
Besides, I do not quite understand how UCT deals with the flaw of ...
4
votes
1answer
51 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 ...
2
votes
1answer
63 views
How to merge a lot of trees into one single graph?
I have a few different trees, which resemble what the AST that compilers often deal with.
For example:
tree 1
( (a, b), (c, d) )
Imagine that each tree split represents the function "add", then ...
11
votes
4answers
4k views
Can the pre-order traversal of two different trees be the same even though they are different?
This question pretty much explains that they can, but does not show any examples of there being two different trees with the same pre-order traversal.
It is also mentioned that the in-order ...
1
vote
1answer
98 views
Space complexity of breadth-first search
I read that breadth-first search has to store (at most) $1+b+b^2+···+b^d$
nodes in memory ---more than depth-first search---, where $d$ is the depth of a solution, and $b$ is the branching factor.
...
1
vote
1answer
31 views
R-tree insertion procedure when leaf is full
I am implementing an R-tree with the quadratic splitting method.
However in most articles I have read there a piece of information that is missing or misleading (or the most probably case, I ...
4
votes
2answers
941 views
How to find sum of maximum K elements in range in array
Recently, I came up to the following problem:
Given array $A$ of size $n$ and integer $k$, We should answer $Q$ questions of the type:
for given range $[l, r]$ we should find sum of the $k$ maximum ...
2
votes
0answers
82 views
Red-black tree trinode restructuring after insertion and deletion
When performing an insertion/deletion on a red-black tree, how can be argued or proved that it requires at most one/two trinode restructuring(s) respectively?
My thoughts so far were: after inserting ...
8
votes
3answers
603 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 ...
1
vote
0answers
17 views
Probabilistic switching between breath-first and depth-first
I am reading Artificial Intelligence: Making Machines "Think" by Neill Graham. He gives an overview of graph search using either the breadth-first (BF) or depth-first (DF) search algorithms, and ...
1
vote
1answer
77 views
Two Minimax AIs playing against each other
I am trying to have my Minimax AI chess players play against each other.
I was a bit confused about an implementation detail.
Let's call black my first minimax AI ...
0
votes
0answers
31 views
How does a binary tree waste memory when stored as nodes and references?
I'm researching binary trees and came across this section describing storage methods.
It states that:
In a language with records and references, binary trees are typically constructed by having a ...
0
votes
0answers
115 views
How many maximum height AVL trees given height?
I am having some trouble finding a recursive formula for finding the number of maximum height AVL trees of height h. Height 0 has 1, height 1 has 2, height 2 has 4, height 3 has 8, etc. is that ...
2
votes
0answers
14 views
Best asymptotic randomized multidimensional index?
What data structure has the best asymptotic running time for nearest-neighbor search on multidimensional data? I am interested in both preprocessing time and query time, but let's restrict attention ...
2
votes
2answers
186 views
How do I know which direction I should rotate a node in an AVL Tree?
I'm studying AVL Trees in my programming class and we got this exercise dealing with right, left, left-right and right-left rotations as a way to check if we understand the theoretical concept of AVL ...
1
vote
1answer
86 views
Search on Conformant Problem: solution for subset of a belief state
I am having trouble understanding the following statement.
I have understood why in a sensorless/conformant problem, if there exists a solution (a sequence of actions) for a belief state $b$, then it ...
1
vote
0answers
94 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 ...
0
votes
2answers
109 views
Efficient way to find matching date ranges?
We have a set of problems involving date ranges - a pair of dates representing a start date and an end date. In some places, we have say 1000 of these and need to find the ones that overlap a separate ...
1
vote
0answers
38 views
Efficient data structure for multidimensional searching on intervals and keys
I am searching for a data structure that can capture a database, which is consisted of one column of intervals (like [0, 2], [4, 6]) and one/two columns of keys (...
2
votes
1answer
50 views
Data Structures - Segment Trees
I was learning about segment trees and came across this:
We have an array arr[0 . . . n-1]. We should be able to
1 Find the sum of elements from index l to r where 0 <= l <= r <= n-1
...
2
votes
0answers
21 views
B/B+ trees without leftmost pointers
In both B-trees and B+trees, a node (a.k.a page) contains K keys and K+1 pointers:
node = [ ptr_1, key_1, ... , ptr_K , key_K , ptr_(K+1) ]
Now suppose that I ...
2
votes
1answer
2k views
How many rotations after AVL insertion and deletion
Is it true that inserting an element to an AVL tree requires $O(1)$ rotations?
How many rotations, does deletion from AVL require?
I've searched for these two questions with no luck so far.
1
vote
1answer
52 views
Searching and inserting in $O(n)$ when $n$ is the size of the key
Edit: The solution to my problem is called a trie ; according to Section 8.1 of Peter Brass book "Advanced Data Structures", for a given alphabet $A$ and a word $w$ of length $n$ on this alphabet, a ...
1
vote
1answer
712 views
5
votes
1answer
3k views
Time Complexity to find height of a BST
Below is a question I was asked in an Interview
What is the best case time complexity to find the height of a Binary Search Tree?
I answered it explaining using the below algorithm
$\mathrm{...
1
vote
0answers
53 views
Example of binary trees with maximum rotation distance
In the 1988 paper Rotation Distance, Triangulations, and Hyperbolic Geometry, Sleator, Tarjan and Thurston show that for any pair of $n$-node binary trees, the maximum rotation distance between them ...
2
votes
0answers
216 views
Analysis expected depth of a binary search tree given random values?
I have a guess about the problem above. Suppose I have a binary search tree $T$ initially empty. Suppose I drawn $x_1,\ldots,x_k$ (from some real interval $[a,b]$) keys and I want to insert the keys ...
0
votes
0answers
95 views
How many roots are there in an undirected root
Given an undirected tree with 7 nodes how many roots would this tree have. My intuition tells me that because the tree is undirected it would either be 7 or 0. How would I solve this?
1
vote
0answers
20 views
Search tree with associative union and worst case insert/delete better than O(n)? [duplicate]
Is there a search tree where union is associative, so $a \cup (b \cup c) = (a \cup b) \cup c$ gives a tree with the same structure?
A complete binary tree would be such a tree, but for example a red-...
2
votes
0answers
17 views
Segment-tree construction: do we recurse into both children?
This question is about segment-tree as described in this Wikipedia article.
When constructing the tree (inserting the new input-interval), if the input-interval doesn't contain the node-interval we ...
0
votes
1answer
1k views
Optimal data structure for sorted list
Most of the resources on the web I have encountered say that "sorted arrays and other sorted data structures are implemented with binary search trees (BSTs)".
Even though B-trees are a generalization ...
3
votes
1answer
130 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
2answers
424 views
Infix search in millions of strings
Let's say we have millions of strings (each of them < 100 characters):
alpha
allo
blah
hello world
orlando
...
I know how a binary search tree or a trie can ...
0
votes
1answer
238 views
All possible Red Black Trees with this set {1,2,3,4,5}
I have to write all possible Red Black Trees which can represent these 5 numbers {1,2,3,4,5}.
Now we have 120 ways to write 1,2,3,4,5
...
1
vote
1answer
148 views
how does rotation works in AVL trees and what is a good way to understand it?
If we consider this tree with T1 and T2 as subtrees, and we want to rotate on x (rotating the edge between T1 and x), what is the result? how does it work then? Does the x stay in its place and T1 ...
0
votes
1answer
657 views
How to calculate number of nodes opened by BFS?
In the below diagram, each node takes up a space of 2KB. I need to find the total memory consumed to reach the goal : I
I know that the equation for BFS is
b1 + b2 + ...... + (bd+1 - b)
Where b is ...
1
vote
1answer
39 views
data structure admitting top items with prefix
A trie can answer a query for all items with a certain prefix in $O(m + \log n)$ time, where $m$ is the number of matches and $n$ is the number of items. A trie also supports $O(\log n)$ insertion and ...
0
votes
0answers
206 views
Time complexity of inorder run on B+ tree (without leavesa link)
I quite sure that it should be $O(n)$, but I didn't found any information about it and I'm not sure how to prove it. Maybe in 2-3 tree the max number of node (include the leaves) is $2n$ and in each ...
