# Questions tagged [search-trees]

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

316 questions
Filter by
Sorted by
Tagged with
20 views

### What formula was used here to calculate the average search time of the binary tree?

My teacher showed me the following slide on the PowerPoint with two binary search trees and their corresponding "average search times". The PPT did not mention what formula was used to ...
• 119
28 views

1 vote
489 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?
524 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 ...
• 135
109 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 ...
54 views

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
1 vote
319 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 ...
• 119
203 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, ...
• 125
26 views

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
487 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$ ...
• 163k
38 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
92 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 ...
1 vote
47 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 ...
• 131
1 vote
154 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 ...
• 51
1 vote
60 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 ...
• 11
1 vote
206 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
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-...
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 ...
156 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 ...
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 ...
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 ...
1 vote
858 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 ...
• 73
83 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)...
1 vote
525 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 ...
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 ...
641 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$...
• 15
1 vote