# Questions tagged [search-trees]

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

63 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1k views

### Alpha beta algorithm with Iterative Deepening analysis

I'm implementing a chess engine. Like many engines, the search for the next best move is done with the alpha-beta algorithm. There are many improvements that can be made to make the algorithm faster ...
260 views

### What is the intuition behind balancing in AVL trees?

I am not sure that my question is clear from the first sight. But I will try to explain what I mean. For now, I am learning balancing the trees on the example of AVL trees. We know that to balance ...
397 views

### B+tree implementation using single file on disk

I'm studying B+trees and I'm trying to understand how actual data can be stored in a physical file and still allow fast lookups. None of it would be in memory, all of the pointers would be "seeks" to ...
540 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 ...
476 views

### Why is exact nearest neighbor search hard in high dimensional spaces?

I started research on nearest neighbor search in IR a couple of weeks ago. I am still very new to this field, but what I discovered so far from literature is: 1) For the exact nearest neighbor ...
195 views

### How to apply path compression to Multi-Bit Trie

Reading a bit about the subject of Multi-Bit tries and IP matching in: High Performance Switches and Routers H. Jonathan Chao, Bin Liu. Page 33 Network Routing: Algorithms, Protocols, and ...
369 views

### Expected depth of modified kind of treap

If we have $n$ elements $s_1, \dots, s_n$ and build a kind of treap (tree-heap) out of it. Each $s_k$ has a priority, which is an integer in $\{ 1, 2, 3 \dots, \lceil \log n \rceil\}$. Since the ...
60 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)$ ...
60 views

### Data structure & algorithms for super-interval queries on intervals with small integer ends

I would like to have an online data structure that supports inserting an interval, and given a query interval $I_q=[l_q,h_q]$ answer if some interval of the data structure is contained in $I_q$, i.e. ...
86 views

### Red-black tree trinode restructuring after insertion and deletion

When performing an insertion/deletion on a red-black tree, how can be argued or proved that it requires at most one/two trinode restructuring(s) respectively? My thoughts so far were: after inserting ...
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 ...
23 views

### B/B+ trees without leftmost pointers

In both B-trees and B+trees, a node (a.k.a page) contains K keys and K+1 pointers: node = [ ptr_1, key_1, ... , ptr_K , key_K , ptr_(K+1) ] Now suppose that I ...
244 views

### Analysis expected depth of a binary search tree given random values?

I have a guess about the problem above. Suppose I have a binary search tree $T$ initially empty. Suppose I drawn $x_1,\ldots,x_k$ (from some real interval $[a,b]$) keys and I want to insert the keys ...
17 views

### Segment-tree construction: do we recurse into both children?

This question is about segment-tree as described in this Wikipedia article. When constructing the tree (inserting the new input-interval), if the input-interval doesn't contain the node-interval we ...
448 views

### Tight upper bound on height of a red-black tree

"Introduction to Algorithms" by Cormen et al., 3rd edition, Lemma 13.1 states that A red-black tree with $n$ internal nodes has height at most $2\log(n+1)$, i.e. $h \le 2\log(n+1)$. Can equality ...
35 views

### Dividing a set of goals among two search agents

Say we had two agents and we want them both to traverse a map concurrently. Their goal is to collectively visit a collection of certain points on the map. If there was just one agent, it would be ...
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$...
350 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'...
521 views

### Time complexity of the operations on a b-tree if deletion is performed by marking nodes inactive

I'm given a B-tree where the delete-operation is not implemented, but instead keys are deleted using tombstones (so they stay in the tree, but are marked as deleted). Now when at least 90% of all keys ...
599 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 ...
584 views

### Red black tree - Insert/Delete proof of correctness

From the Cormen book I was studying the chapter focused on the red black tree. I was particularly interested in why the procedures for insert/delete fixup works (namely a formal proof). I report both ...
83 views

### Can the right childs of a node in an AVL tree be both balanced after an insert and need rebalancing?

I was trying to come up with a case where one would need rebalance the following case in an AVL tree: I think that case impossible to happen during an insert. It seems to me that its impossible to ...
40 views

### How to find number of occurences of specific distances in binary (search) trees?

I want to calculate the amount of tree structures that have a given maximal distance between two nodes given an amount n of nodes (or keys). E.g. with ...
21 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-...
31 views

157 views

### LLRB Tree How to prove if left and left of left node are black, then this node must be a red node?

Im learning the delete operation on Left-leaning Red Black Tree invented by Prof. Sedgewick. In delete operation, a node could be only deleted from a 3-node or a 4-node but 2-node. In order to ensure ...
42 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
54 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 ...
26 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 ...
24 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 ...
11 views

### Depth of an R-tree, given $m$, $M$ and number of elements

Simply: what is the theoretical maximum, minimum or expected depth of an R-tree given $m$ minimum $M$ maximum elements in a node, with $N$ amount of nodes?
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 ...
101 views

### How many roots are there in an undirected root

Given an undirected tree with 7 nodes how many roots would this tree have. My intuition tells me that because the tree is undirected it would either be 7 or 0. How would I solve this?
221 views

### Time complexity of inorder run on B+ tree (without leavesa link)

I quite sure that it should be $O(n)$, but I didn't found any information about it and I'm not sure how to prove it. Maybe in 2-3 tree the max number of node (include the leaves) is $2n$ and in each ...
110 views

### Time complexity proof of finding the $i$ object in binary search tree is $O(h+i)$ by inorder

I'm looking for time complexity proof of finding the $i$ object in binary search tree is $O(h+i)$ by inorder run. when $h$ is the height of the tree.
27 views

### Unusual function - operations on lists / sets - possible optimization

I have a problem. Below I present a function in Python. ...