Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [search-trees]

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

Filter by
Sorted by
Tagged with
0 votes
6 answers
59 views

Efficient data structure for multidimensional lookup

I'm doing a search problem over 18-tuples of non-negative integers. Some tuples are GOOD and some tuples are BAD, and I'm trying to list all of the GOOD tuples exactly once. It turns out that if a ...
user326210's user avatar
0 votes
0 answers
63 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 ...
3xhaust's user avatar
4 votes
1 answer
175 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))...
Nisalon's user avatar
  • 143
1 vote
1 answer
70 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 ...
Mason Rashford's user avatar
0 votes
1 answer
32 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 ...
Mate de Vita's user avatar
0 votes
0 answers
48 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 ...
Algo's user avatar
  • 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 (...
dport's user avatar
  • 1
1 vote
0 answers
142 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 ...
Error 404's user avatar
2 votes
1 answer
157 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 ...
Avv's user avatar
  • 505
1 vote
0 answers
205 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 ...
Display Name's user avatar
1 vote
1 answer
164 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 ...
Anters Bear's user avatar
0 votes
1 answer
59 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 ...
prototycoon2's user avatar
2 votes
1 answer
135 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 ...
SOFe's user avatar
  • 133
1 vote
1 answer
156 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 ...
Mike's user avatar
  • 33
0 votes
1 answer
127 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 ...
Denis's user avatar
  • 111
0 votes
1 answer
290 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 ...
New's user avatar
  • 3
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 ...
kerds78's user avatar
2 votes
1 answer
140 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 '...
Othman El Hammouchi's user avatar
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 ...
BrockenDuck's user avatar
0 votes
1 answer
134 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 ...
Liam Kelly's user avatar
2 votes
1 answer
165 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 ...
derteufelqwe's user avatar
2 votes
1 answer
62 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 $\...
EJoshuaS - Stand with Ukraine's user avatar
1 vote
1 answer
457 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?
jojo_Aero_smith_the_dummy's user avatar
0 votes
1 answer
510 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 ...
Vectorizer's user avatar
0 votes
0 answers
105 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 ...
HeavyLifter's user avatar
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 ...
MathCurious's user avatar
1 vote
2 answers
307 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 ...
Arsenius's user avatar
  • 119
0 votes
1 answer
196 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, ...
Rikib1999's user avatar
  • 125
-1 votes
1 answer
26 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 ...
Mikey's user avatar
  • 11
3 votes
2 answers
476 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$ ...
D.W.'s user avatar
  • 161k
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,...
Save's user avatar
  • 101
0 votes
0 answers
87 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 ...
Segmentation fault's user avatar
1 vote
0 answers
45 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 ...
fakedrake's user avatar
  • 131
1 vote
0 answers
147 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 ...
Alemha's user avatar
  • 51
1 vote
0 answers
53 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 ...
Unknown's user avatar
  • 11
1 vote
1 answer
193 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, ...
ilyes hamrouni's user avatar
1 vote
1 answer
19 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-...
MatthiasPichler's user avatar
2 votes
0 answers
31 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 ...
Dr. John A Zoidberg's user avatar
0 votes
2 answers
150 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 ...
Toothpick Anemone's user avatar
0 votes
1 answer
65 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 ...
Gerardo Zinno's user avatar
0 votes
0 answers
14 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 ...
michaelsking1993's user avatar
1 vote
2 answers
837 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 ...
Shyvert's user avatar
  • 73
2 votes
1 answer
82 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)...
DoubtExpert's user avatar
1 vote
3 answers
509 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 ...
Vinay Varahabhotla's user avatar
0 votes
3 answers
81 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 ...
Arkaprava Paul's user avatar
0 votes
1 answer
638 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$...
priortt's user avatar
  • 15
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{...
milck's user avatar
  • 111
3 votes
0 answers
527 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 ...
Martin Thoma's user avatar
  • 2,360
0 votes
3 answers
368 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 ...
EpicNicks's user avatar
2 votes
0 answers
82 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 ...
Robert C. Holland's user avatar

1
2 3 4 5
7