# 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
167 views

### how does rotation works in AVL trees and what is a good way to understand it?

If we consider this tree with T1 and T2 as subtrees, and we want to rotate on x (rotating the edge between T1 and x), what is the result? how does it work then? Does the x stay in its place and T1 ...
680 views

### How to calculate number of nodes opened by BFS?

In the below diagram, each node takes up a space of 2KB. I need to find the total memory consumed to reach the goal : I I know that the equation for BFS is b1 + b2 + ...... + (bd+1 - b) Where b is ...
39 views

### data structure admitting top items with prefix

A trie can answer a query for all items with a certain prefix in $O(m + \log n)$ time, where $m$ is the number of matches and $n$ is the number of items. A trie also supports $O(\log n)$ insertion and ...
215 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. ...
310 views

### Deletion of record from B+ tree

I was going through the B+ tree deletion operation from the book Database System Concepts, 6th Edition by Henry F. Korth. One particular thing caught my attention. A B+ tree is given. We have to ...
158 views

### Avarage height of Red-Black tree [closed]

I wrote a program to discover how height of the tree is relative to the number of elements in the tree (nodes). On first test I filled array with 10-50-100-200...-1000 elements of random numbers from ...
3k views

### How many node does the final B-tree have?

I'm currently studying the B-Trees chapter of Introduction to Algorithms. One of the question from the chapter is: Suppose that we insert the keys $\{1,2,...,n\}$ into an empty B-tree with minimum ...
154 views

### Iterate over two different non-binary tree graph [closed]

I'm working to solve a problem based on two non-binary tree graphs, that they need to be iterated together in order to find a valid combination. I did a basic implementation that works, but it have a ...
201 views

### Understanding B tree key deletion step from CLRS algorithm

CLRS explains B tree key deletion as follows: If the key $k$ is in node $x$ and $x$ is a leaf, delete the key $k$ from $x$. If the key $k$ is in node $x$ and $x$ is an internal node, do the ...
221 views

### How to validate a connect X game (Tick-Tak-Toe,Gomoku,…)?

Currently I am working on a Gomoku AI (or generally Connect-X games). Implementing the search tree was no problem, but then I got to the point where I had to implement the value function and was ...
318 views

### return a key of a node with maximum value within a range of keys in B+ tree

I've been asked a question about B+ Tree. The question is: Suppose we have object of the following type: ...
53 views

### Comparison of Depth First Search Trees

Does anyone know of an algorithm who is able to return how similar a DFS Tree is from another DFS Tree? (Or any kind of tree in general) I'm not looking for a true or false. Instead, I would like it ...
41 views

### AVL Tree Inner Nodes

If k is the height of an AVL Tree, the minimal number of inner nodes is: N(k) = N(k-1) + N(k-2) +1. Why is this formula true?
376 views

### What do we benefit from using ternary search trees rather than binary search trees?

Ternary search trees are very common in the text editing area. They could be used to implement Auto complete feature, spell checking, Partial-Match searching, Near-Neighbor Searching & many many ...
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 ...
36 views

### Is it possible to obtain dynamic tree with two dimensions in big matrix

Let's say we have given matrix of size $n \cdot m$, such that both $n, m$ are big numbers and we cannot keep the whole matrix in memory (up to 10 millions). In some of the coordinates of the matrix ...
84 views

### Average solutions in infinite search tree

I have the following problem: Consider a balanced infinite search tree with branching number $κ$. Consider a search problem with solutions which may be located at any node of the tree. The ...