Questions tagged [search-trees]
Questions about search trees, a class of data structures used for storing sorted data for efficient access.
286
questions
2
votes
0answers
22 views
Data Structures for BST where size uniquely determines shape
There are several data structures in which the number of elements uniquely determines the shape.
Examples would be binary heaps, arrays, lists, Braun trees, and Merkle mountain ranges.
Are there any ...
0
votes
2answers
82 views
If we want to map abbreviations of full-English words (e.g. map “Jan” to “January”), how can we identify abbreviations which map to multiple words?
Short Version:
How can we construct a trie which maps abbreviations of names-of-the-month to full-month (we map the abbreviation "mar" to "march")?
The set of all abbreviations is ...
0
votes
1answer
34 views
Building Suffix Array from Suffix Tree. Inorder visit when node has more than two children
From the notes:
It is not difficult to observe that the suffix array $\texttt{SA}$ of
the text $\texttt{T}$ can be obtained from its suffix tree
$\texttt{ST}$ by performing an in-order visit: each ...
0
votes
0answers
12 views
Parsing text, then searching it: one entry per position, vs. 1 JSON column per text
I have a Rails application using Postgresql.
Texts get added to the application (ranging in size -- as short as a few words, to as long as, say, 5,000 words?).
The text gets parsed, both ...
0
votes
0answers
8 views
Minimal t needed in B tree for the lowest reading time
I've got an assignment, which I was asked to calculate the minimal t needed in a B tree, to have the optimal searching time.
So here it is:
We've been told that in a specific B tree, with unknown t, ...
1
vote
2answers
58 views
Deletion in a Binary search Tree
The teacher explained to us this algorithm for deleting a node in a binary search tree, but I can't understand how it works when the node to be deleted has only one child (I already know how it works ...
1
vote
1answer
30 views
Why does a range query on a segment tree return at most $\lceil \log_2{N} \rceil$ nodes?
If an array $A[1 \ldots N]$ is represented using a segment tree having sets in each interval, why does a range query $[L\ldots R]$ returns at most $\lceil \log_2{N} \rceil$ sets (or disjoint intervals)...
0
votes
1answer
23 views
Finding the number of children of the predecessor node of a given node in a Binary Search Tree(BST)
I have some propositions regarding BSTs , please can someone confirm whether they are true or false:
Question :
1.Suppose we have a node $n_1$ with a value $val_1$ i.e $n_1(val_1)$
2.We wish ...
0
votes
3answers
47 views
Finding the point with minimum x-ordinate, lying between two y-ordinates
Given a set of points $P=p_1,p_2,..p_n$ in $R^2$ in where $p_i=(x_i,y_i)$,finding the point with smallest x-ordinate having y-ordinates between $y_1$ and $y_2$, where $y_1$ and $y_2$ are given as ...
0
votes
1answer
123 views
Average number of inspections
Consider a set of n elements whose key values are $$0, 1, ..., nā1.$$ Let $p(i) (0 ā¤ i ā¤ nā1) $ be the probability that the element with key i is searched. Assume the following distribution of $p(i)ās$...
1
vote
1answer
22 views
Constructing a data structure supporting prioritized key lookup
so this is more or less a shot in the dark as I am feeling stuck. Maybe some of you have an idea which helps.
Here is the problem description (pseudo formal):
I want to have a structure $T = \{ \hat{...
0
votes
0answers
17 views
Why do b*trees partition 2 nodes into 3?
I'm writing a b*tree library in Rust. I'm thinking it might be better to make the purposeful decision to only implement half of the b* optimizations. (And not because it is easier, although it is.)
...
1
vote
0answers
81 views
Should a prefix tree (trie) node store only a single character or a string?
I've just implemented a Trie and I thought it would be a good idea to store strings in the Trie nodes in contrast to storing single characters.
Storing strings is for sure more space-efficient and ...
2
votes
0answers
25 views
What's a minimum-window alpha beta search algorithm?
I was skimming the Deep Blue overview paper and on page 242 it says: "The search control does not really implement the regular Ī±Ī² search algorithm. Rather it implements a minimum-window Ī±Ī² search ...
1
vote
1answer
126 views
Efficiently finding the min-cost path of an AVL tree
It seems that in a full AVL tree, the left edge is always the minimum-cost path. For example, take the following full AVL tree:
The min-cost path would be 8-6-5. ...
0
votes
0answers
24 views
Runtime of tree sort algorithm confusion
Can anyone explain to me why the average runtime complexity of the program here - https://www.geeksforgeeks.org/tree-sort/ - is nlogn and not n^2logn? Similarly, why is the worst case time complexity ...
1
vote
0answers
89 views
Is the internal structure of a red-black-tree dependent on the insertion order?
Is the internal structure of a red-black tree (which nodes are red or black, the disposition of the branches, the location of each value...) dependent on the order in which the elements were inserted? ...
3
votes
0answers
48 views
Node depth in randomly built binary search tree
It can be proved that randomly built binary search trees of size $n$ are of depth $O(\log n)$ and it is clear that level $k$ has at most $2^{k}$ nodes (root's level is 0).
I have an algorithm that ...
0
votes
0answers
71 views
What is the time and space complexity for radix search tree
What is the time and space complexity for radix search tree
in this research
https://www.researchgate.net/publication/314799182_Novel_Approach_for_Arabic_Spell-Checker_Based_on_Radix_Search_Tree
3
votes
0answers
234 views
What's the number of leaves in AVL tree
How can I prove that the number of leaves in a balanced BST is $\Omega (N)$ where $N$ is the number of nodes in the tree?
I tried somehow to prove that an AVL/Fibonacci tree should have $\Omega (N)$ ...
0
votes
1answer
314 views
How to delete a node from BST tree with 2 chidren?
I googled, read several tutorials and watched several BST node deletion algorithm explanations before posting this question. For some reason, I cannot find a complete explanation of BST node deletion ...
1
vote
0answers
32 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-...
2
votes
1answer
66 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
54 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
38 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
129 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
57 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
88 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
24 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
36 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
132 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. ...
1
vote
1answer
386 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
61 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
147 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
5k 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
192 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
33 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
1k 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
115 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
738 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
23 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
163 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
122 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
418 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
150 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
208 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
279 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
47 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
58 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
...
