# Questions tagged [search-trees]

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

302 questions
Filter by
Sorted by
Tagged with
55 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 ...
53 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 '...
34 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
79 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 ...
• 101
56 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 ...
51 views

• 121
284 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 ...
• 2,300
245 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 ...
36 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 ...
1 vote
388 views

### Efficiently finding the min-cost path of an AVL tree

It seems that in a full AVL tree, the left edge is always the minimum-cost path. For example, take the following full AVL tree: The min-cost path would be 8-6-5. ...
• 111
1 vote
275 views

### Is the internal structure of a red-black-tree dependent on the insertion order?

Is the internal structure of a red-black tree (which nodes are red or black, the disposition of the branches, the location of each value...) dependent on the order in which the elements were inserted? ...
107 views

### Node depth in randomly built binary search tree

It can be proved that randomly built binary search trees of size $n$ are of depth $O(\log n)$ and it is clear that level $k$ has at most $2^{k}$ nodes (root's level is 0). I have an algorithm that ...
• 131
586 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)$ ...
1k 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 ...
• 103
1 vote
124 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-...
• 41
280 views

### Finding the shortest time to go from one stop to another stop in a train system with many train lines with connection stations

So I was thinking after discussing with my friend the other day, how would I use something like breadth-first or depth-first search to find the fastest time to go from one station to another station ...
87 views

### Range Query with conditions

Suppose I have an $N$ length integer array of pairs of the type $[value, key]$. Now, I need to query for range sum. Query is of the type : $l, N, x$ meaning I have to sum up all the $value$ in the ...
• 11
110 views

• 317
1 vote