# Questions tagged [search-trees]

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

272 questions
Filter by
Sorted by
Tagged with
177 views

### Is “promoting a key” a part of deleting internal node key in B+ Tree?

I was trying to learn B+ tree deletion operation and trying to contrast it with B tree deletion operation. However barely any book provided detailed step by step B+ tree deletion operation. So I was ...
6 views

### What is the difference between backtracking and forward checking / lookahead?

What is the difference between backtracking and forward checking / lookahead? Can you please give me explanation and simple example in programming language C, NETLOGO... I am trying to solve N-QUEENS ...
38 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
167 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 ...
592 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 ...
57 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)$ ...
33 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 ...
2k 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 $k$...
20 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-...
142 views

### Time Complexity for Nearest Neighbor Searches in kd-trees

Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof. In order to calculate the average number of ...
3k views

25 views

210 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 ...
31 views

### How does a binary tree waste memory when stored as nodes and references?

I'm researching binary trees and came across this section describing storage methods. It states that: In a language with records and references, binary trees are typically constructed by having a ...
115 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 ...
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 ...
103 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 ...
89 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 ...
50 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 ...
119 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 ...
41 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 (...