Questions tagged [search-trees]
Questions about search trees, a class of data structures used for storing sorted data for efficient access.
315
questions
2
votes
2
answers
3k
views
Interval tree: find all intervals containing a given interval
Given an interval tree $T$ and an interval $I$, I need to find an algorithm that returns all intervals in $T$ that contain $I$. The asymptotic running time should be $O(\min(n,(k + 1) \log n))$ where $...
CommunityBot
- 1
3
votes
1
answer
763
views
How to efficiently create balanced KD-Trees from a static set of points
From Wikipedia, KD-Trees:
Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
CommunityBot
- 1
4
votes
2
answers
1k
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 ...
- 931
1
vote
1
answer
246
views
Lookup complexity in B-trees [Database]
Given that:
B = n/R blocks in the file
2d index records per block (blocking factor): 2d > R
an extra block access from the index to the datafile
I am not able ...
CommunityBot
- 1
1
vote
3
answers
491
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 ...
CommunityBot
- 1
4
votes
1
answer
173
views
Improving a ranking system with "best rank"
I've implemented a ranking system (based on a score), using a Map<Player,Score> and an improved BST<Score, Set<Player>>.
So now I can compute "rank of a player" in O(log(n))...
- 2,348
0
votes
0
answers
59
views
Sub-Grouping AVL tree based on nodes amount in O(log(n))
I need to find a way to split an AVL tree based on the amount of nodes in the tree, lets assume you get a number $k$ and if the number of nodes in the tree is multiplication of $k$ you need to find ...
- 9
1
vote
1
answer
48
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 ...
CommunityBot
- 1
1
vote
1
answer
65
views
Does a sorted sequence from in-order traversal imply a binary tree is a BST?
An in-order traversal of a binary search tree (BST) produces a sorted sequence. I wonder, if we perform an in-order traversal of a binary tree and obtain a sorted sequence, does that imply that the ...
- 30.6k
0
votes
1
answer
55
views
BSTs with repeating keys
The problem is to count number of unique binary search trees with keys $a_1,a_2,...,a_n$, given that some of the keys are not unique. For example, $a$ could be 2, 1, 1, 4, 3, 4.
We could try an ...
CommunityBot
- 1
5
votes
3
answers
3k
views
Uniform-cost Search Problem
Suppose that we take an initial search problem and we add $c > 0$ to the costs on all edges. Will uniform-cost search return the same answer as in the initial search problem?
Definitions: Uniform-...
0
votes
1
answer
31
views
Combining chunks on an infinite grid into regions
I am working on an floorplan application where I save elements on an infinite grid in a sparse manner. Specifically, I have the following Python class representing a sparse grid (basically a ...
D.W.♦
- 159k
2
votes
1
answer
150
views
Visualizing How of KD-tree Data Structure Splits Space
I am trying to understand how KD-tree works when we insert a node and how it splits the xy plane, please. Below $[5, 4]$ splits the xy-plane into left and right parts while $[2,6]$ splits it into top ...
- 837
2
votes
1
answer
129
views
Approximating the median of the complement of a set
Given an integer $n$ and a tree set $S$, I would like to find the approximate median $x$ of the integer set $T := \{i \in \mathbb N : i < n \wedge i \notin S\}$. There are no constraints to the ...
- 133
0
votes
0
answers
28
views
Expectimax Pruning
I found the following question in my book:
For probabilistic games like backgammon, where there is a resource
limit, the RB-Expectimax algorithm is used.
Assume that it is known that the heuristic ...
- 11
0
votes
0
answers
37
views
Monte Carlo Tree Search for Robo Rally AI
I want to implement an AI capable of playing the game RoboRally (https://en.wikipedia.org/wiki/RoboRally) using Monte Carlo Tree Search (MCTS). In RoboRally, there are 2-8 characters controlled by (...
- 1
1
vote
0
answers
139
views
Simplified Memory Bounded A*
I have been studying the SMA* algorithm and I am having trouble understanding the backup operation. Specifically, I don't understand why the f value of a child node should be the maximum of its own f ...
- 11
10
votes
5
answers
10k
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 ...
CommunityBot
- 1
1
vote
2
answers
298
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
...
CommunityBot
- 1
1
vote
0
answers
197
views
Is there a faster alternative to Aho-Corasick when searching for any occurrence rather than all occurrences of each of the substrings?
Aho-Corasick can result in a quadratic number of matches because it finds all occurrences of each searched-for substring. What is a faster algorithm or modification to this one to simply determine if ...
- 111
1
vote
1
answer
162
views
Finding Optimal Configuration of Formula without trying every Permutation
I have a math problem I need to solve so I can complete an optimisation in a computer program. My initial approach was just to brute force all the possible permutations but it got out of hand quite ...
- 529
8
votes
1
answer
11k
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.
- 30.6k
1
vote
1
answer
149
views
Randomly generated binary search trees case comparison
Although not an assignment, just out of curiosity; I am trying to compare a two cases
A scenario where I pick a tree out of the set of possible binary search trees on the keys $1,2,\ldots,n$, with ...
- 15.6k
0
votes
1
answer
115
views
Confusion about B-Tree
In a B-Tree, one of the rules is:
Every node (except the root) is at least half full
But then, in a 4-way B-Tree, we have the following case. Suppose we want to insert $10,20,30,40$ to the tree.
After ...
- 15.6k
0
votes
1
answer
273
views
Representing graph as a search tree
How do I convert a graph to a search tree? Here's the question-
The problem is that I don't know how to represent interconnections in a graph on a tree. In the diagram A is connected to D, and same ...
- 15.6k
3
votes
1
answer
6k
views
Segment trees with insertion/deletion
I have a range-query problem to solve. This problem requires not only range queries and update, but also insert or delete an element of the array. There is a series of operations that must be done in ...
- 39k
2
votes
1
answer
4k
views
Estimating size of state space search problem
Im currently enrolled in an AI course and we are starting with state space search problems. My professor always seems to ask, given a certain problem, what is the estimate size of the state space? It'...
CommunityBot
- 1
0
votes
4
answers
82
views
Would someone be able to explain why the Time Complexity here is O(b^d) instead of O(d(b^d))?
So I'm doing an AI course that is talking about time complexities of different tree search algorithms. On this slide it talks about the time complexity of the algorithm, and I'm confused as to why we ...
- 261
2
votes
1
answer
133
views
Rigorous distinction between search and optimization
I'm working my way through parts of Russell and Norvig's AIMA book for a class, and there's something I've never quite managed to wrap my head around. Chapters 3 and 4 contrast 'search' methods with '...
D.W.♦
- 159k
2
votes
0
answers
54
views
Efficient Implementation of join and split operations on semisplaying tree
Splaying trees are a heavily researched of theoretical computer science as they are conjectured to be optimal binary trees. They were first presented by Sleator & Tarjan in Self-Adjusting Binary ...
- 121
10
votes
4
answers
6k
views
Don't understand one step for AVL tree height log n proof
I came across a proof that an AVL tree has $O(\log n)$ height and there's one step which I do not understand.
Let $N_h$ represent the minimum number of nodes that can form an AVL tree of height $h$. ...
- 39k
0
votes
1
answer
133
views
Is there a hash-map implementation optimized to favor key lookups based on frequency (if key is referenced the most then it is searched first)?
I have started to play around with HTTP3 which relies on QUIC for transport. I have noticed that I very often have a finite number of Web Transport sessions stream data continuously along side burst-y ...
- 30k
0
votes
3
answers
365
views
How to convert a Complete Binary Tree to a Priority Search Tree in O(n)?
I would like to know if there is a linear-time algorithm ($\mathcal{O(n)}$ time) to convert a
Complete Binary Tree with data left-to-right increasing stored in
external nodes, to a Priority Search
...
D.W.♦
- 159k
8
votes
7
answers
62k
views
Are degree and order the same thing when referring to a B-Tree?
I know the term order of a B-tree. Recently I heard a new term: B tree with minimum degree of 2.
We know that the degree is related to a node but what is the degree of a tree?
Does degree impose any ...
- 39k
2
votes
1
answer
157
views
(Algorithm required) How to determine if a point is in one of many rectangles
What I want to achive ist the following: I have a 2D plane and on this plane I will have a potentially large amount of rectangles (these are specified with 2 coordinates spanning it)
Whats the most ...
D.W.♦
- 159k
2
votes
1
answer
60
views
How did the following derivation of the final weight of a weight-balanced search tree node after rotation to make it balanced occur?
I was reading section 3.2 of Advanced Data Structures by Peter Brass (which is about weight-balanced search trees) for self-study. I got stuck on a proof about rebalancing properties.
$\alpha$ and $\...
- 39k
1
vote
1
answer
438
views
what are good data structure algorithm for fast 3D coordinates search?
I want to form data structure for nearby neighbor search for 3D coordinates. What is the best way to do so?
- 22.1k
0
votes
1
answer
497
views
Height of AVL Tree
I found an AVL tree implementation on the internet and experimented:
For a tree with node count of 2^20, the minimal and maximal tree heights are 16 and 24.
While these heights are lg(n)-ish, I am ...
- 14.6k
0
votes
0
answers
103
views
2D segment tree query time complexity
These sources cp-algorithms and geeksforgeeks
state that query complexity (for example, submatrix sum) of 2-D segment tree is O(logN * logM), because
it first descends the tree in the first ...
2
votes
3
answers
1k
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 ...
0
votes
0
answers
54
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 ...
- 231
6
votes
2
answers
4k
views
Can a Red Black tree be constructed of only black nodes using RB insert only?
I am trying to construct a red black tree out of only black nodes.
I know it is possible getting it after some deletions but I am trying to construct one only via insertion orders.
Is it possible?
I ...
1
vote
1
answer
637
views
Understanding B tree key deletion step from CLRS algorithm
CLRS explains B tree key deletion as follows:
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 ...
CommunityBot
- 1
1
vote
1
answer
357
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 =...
CommunityBot
- 1
1
vote
1
answer
52
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{...
CommunityBot
- 1
0
votes
1
answer
177
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, ...
- 29.5k
-1
votes
1
answer
25
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 ...
- 11.6k
3
votes
2
answers
464
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$ ...
- 39k
0
votes
0
answers
37
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,...
- 101
0
votes
0
answers
76
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 ...
