Questions tagged [search-trees]
Questions about search trees, a class of data structures used for storing sorted data for efficient access.
298
questions
0
votes
0answers
20 views
Finding matches between an input string and a fixed set of strings
I need to compare an input string to multiple strings which I'll refer to as fixed strings, and you can assume the latter won't change. Comparison disregards letters with special characters, only ...
0
votes
0answers
34 views
How to trasnform search tree into AVL tree with constant memory and in linear time? [closed]
How to transform search tree into AVL tree with constant memory and in linear time ?
0
votes
0answers
30 views
Question about AVL properties
Assume that the oil company saves for each person that works in the
company a record with its name, its salary, its age and its date of
birth. You can assume that no two fields are identical for any ...
1
vote
1answer
49 views
More efficient way to parse array into binary search tree
Let's assume I have array which I need to parse into binary tree
...
0
votes
1answer
27 views
Rank operation in search tree, number of nodes between 2 values
What kind of search tree should I use in which I will have operation Rank[x, y] which will return number of existing nodes/values between x and y in time O(depth of tree) so the operations find, ...
-1
votes
1answer
21 views
A very simple question about Admissible Heurisitcs
Given admissible heuristics f(s), g(s), h(s).
It is true that max(f(s), g(s), h(s)) is still admissible.. but is it still admissible if its max(f(s), g(s) + h(s)). I believe it is not admissible but I ...
2
votes
2answers
77 views
Data structure for interval subset queries
I have a set $S$ of intervals. I'd like to store them in a data structure, so that I can handle the following query efficiently: given a query interval $q$, count the number of intervals $s \in S$ ...
0
votes
0answers
18 views
Search algorithm for multidimensional space with custom topology
First, let's start with the description of the problem in dimension 1:
Let $T_0$ be a space with $n$ nodes organized in a tree structure, with $m$ of those nodes defined as target nodes. In this space,...
0
votes
0answers
29 views
When do insertions and deletions get enacted in a buffer tree?
Buffer trees are $(a, b)$-trees in which each node in the tree gets an associated buffer for storing operations to be conducted on elements in the tree. While I appreciate the idea of amortizing the I/...
0
votes
0answers
38 views
Having trouble understanding Red-Black trees
Exam question:
Draw the Red Black Tree that results from inserting the following
values in the given order:
[10, 20, 30, 4, 5, 50]
Draw the red connections with a dotted line and the black ones with ...
0
votes
0answers
32 views
Some nodes in binary search had broken.how we can fix it in-place by swapping nodes?
Given a binary search tree(can have any height) .Some nodes its value
changed and violate bst property how we can recover binary search
tree property in-place by just swapping a node with its ...
0
votes
0answers
101 views
Find largest $k$ numbers in Max Heap in $O(n\log k)$
I have a data stream with $n$ numbers and I want to find the largest $k$ of them ($k \ll n$). I want to use a priority queue with max heap of size $k$, so I will have space complexity $O(k)$, which is ...
1
vote
0answers
29 views
Simultaneous binary (n-ary) search
I have a balanced $k$-ary B-tree with $N$ leaves (where N is a power of $k$ for simplicity) and I need to simultaneously locate $\ell$ leaves in it. What is the expected number of nodes I will need to ...
1
vote
0answers
74 views
Trapezoidal Map and Search Tree
i am studying on trapezoidal maps. In the last section, "Analysis" of this paper, it says "The expected query time is indeed O(log n). Again the search structure size can be quadratic ...
0
votes
0answers
63 views
Creating Priority Search Tree bottom up from a Complete Binary Search tree in O(n)
I have a Complete Binary Search Tree of points ordered(sorted) on the y-axis (such that the point with the mid y of all the points is the root and its left children have decreasing y from the root and ...
1
vote
0answers
19 views
Greedy Best-First Search Performance for Tree and Graph Space
I am currently reviewing the GBFS algorithm and when looking at its completeness I am confused between the difference of it being
not optimal in Tree Search for Finite and Infinite Spaces
that it is ...
1
vote
1answer
48 views
Should i work with tree representation as an array of nodes and an array of edges
Here is the problem, i have a graphical component that displays a tree. It takes as input an array of nodes and array of edges(eg:an edge has a source and target).
I will be performing complex tasks, ...
1
vote
1answer
13 views
Does n^(1-1/d) always dominate log^d(n)
Hi I am currently learning about orthogonal range search and found two data structures with two different runtimes and wanted to proof that one always dominates the other.
So I found out about k-d-...
0
votes
0answers
28 views
Data structure for a queue of weighted elements
Consider a queue of elements with weights $w_0, w_1 \ldots, w_{n-1}$. The queue supports two operations:
Inserting one element at the back of the queue
Reducing the weight of one element in the ...
2
votes
0answers
26 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
98 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
37 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 ...
1
vote
2answers
145 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 ...
2
votes
1answer
48 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
2answers
84 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
70 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
316 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
30 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{...
2
votes
0answers
203 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
28 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
337 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. ...
1
vote
0answers
201 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
75 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 ...
3
votes
0answers
457 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
1k 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
73 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
173 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
63 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
46 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
237 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
87 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
193 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
30 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
42 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 ...
1
vote
1answer
652 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
154 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
301 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
6k 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
281 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.
...
