# 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
3answers
1k views

### Memoization without array

In Cormen et al.'s Introduction to algorithms, section 15.3 Elements of dynamic programming explains memoization as follow: A memoized recursive algorithm maintains an entry in a table for the ...
1answer
40 views

### Logarithmic guarantees for randomized search trees

In this paper [1], "treaps" and "randomized search trees" are introduced. The idea is to guarantee logarithmic update and query operations by assigning uniform random priorities to the keys being ...
0answers
254 views

1answer
118 views

### Can minimum or maximum height of the binary search tree be constrained by the position of some elements

I came across one problem, which read as follows: We want to place the 13 letters A, B, C, D, E, F, G, H, I, J, K, L, M in a binary search tree with the minimum number of levels: 4. Because there ...
2answers
2k views

### Why do we need double-rotations to rebalance AVL trees?

I was reading about AVL tree rebalancing from Behrouz Forouzan's book. The book first defines Left High and Right High tree: Left High (LH) tree is a tree tree with the height of the left ...
1answer
127 views

### Data structure for efficient searching, when insertions and removals are only one-sided

I need a data structure for storing a number $n$ of elements, each of whom is associated with some different time $t_i$. $n$ varies and while it has a theoretical upper limit, this is many orders of ...
1answer
676 views

### Keeping a binary search tree by splitting nodes (like a B-Tree)

A B-tree is kept balanced (i.e. all leaves at same depth) by splitting a node when adding a child that won't fit, and propagating this splitting up to the root. Can the same technique be used to keep ...
1answer
422 views

### Question on the properties of red black trees

Problem statement Let $T$ be a red black tree and $u$ some internal node of $T$. Suppose that in the left subtree of $u$ we have $n$ nodes. What is the maximum number of nodes that we can have in the ...
2answers
166 views

### UCT1 Algorithm: What does “total number of simulations” mean?

When reading up on the UCT1 algorithm (I'm writing a Monte Carlo tree search), I'm having trouble with the formula. $$\frac{w_i}{n_i} + \sqrt{\frac{\ln t}{n_i}}$$ Wikipedia, this guy, and this guy all ...
1answer
335 views

I need a queue $[x_0, ..., x_n]$ that supports the following operations: $\operatorname{enqueue}([x_0, ..., x_n], x) = [x_0, ..., x_n, x]$ $\operatorname{dequeue}([x_0, ..., x_n]) = [x_1, ..., x_n]$ $... 1answer 151 views ### Validate that a threaded binary tree works as intended I am attempting to validate that my threaded binary tree’s insertion and deletion works as intended. Would it be safe to assume that the following procedure would have tested all corner cases at ... 1answer 153 views ### Why do you reason about the minimum number of nodes of an AVL tree of height h to argue the height is$\log n$of an AVL tree? Recall the standard argument for showing an AVL free is of size$\log n$: Let$n_h = $be the minimum number of nodes of an AVL tree of height$h$. Then we have:$$n_{h} \geq 1 + n_{h-1} + ... 2answers 1k views ### Does the rebalancing propagate upwards only to update the height of the nodes in an AVL tree? I was studying AVL trees and was wondering if the only reason one propagates upwards to the node in an insert is to change the height. It seems to me that rebalancing does not recursively propagate ... 0answers 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 ... 1answer 723 views ### Why Is KD-Tree-based Nearest Neighbor Exponential in K? I've read in many papers on higher-dimensional nearest neighbor search that KD-Trees are exponential in K, but I can't seem to determine why. What I'm looking for is a solid runtime-complexity ... 1answer 626 views ### Reb-black tree amortized cost of the rebalancing I've read in different sources that the amortized cost of a red-black tree rebalancing is constant (at least during the tree creation using only insertions). How can it be proved? 1answer 753 views ### Difference between heuristic-based searching and optimal path searching I'm currently studying for an AI computer-science course. One thing is difficult for me to grasp and somewhat vaguely explained in my course-material: I understand that with search-methods like e.g. ... 1answer 279 views ### Can I speed up Insertion Sort by using a tree for finding insertion positions? I want to implement an insertionSort-algorithm. Let's say I have these pseudocode. ... 1answer 786 views ### Is it possible to use a copy-on-write strategy to modify a B+ tree? Alright, I'm not sure if this is more of a stack overflow question, but I'm going to try here because you folks seem more suited. CouchDB makes an interesting claim about using an "append only" B+ ... 3answers 786 views ### Depth first or breadth first ordering in binary search trees? Let's say that I make a binary search tree and store it in an array so that I end up with an array that is more cache friendly to binary search compared to a sorted array. The binary tree is full on ... 1answer 2k views ### Every AVL tree may be red black tree I proved by induction that every AVL tree may be colored such that it will be red black tree. The problem is that I can't see an error in my proof. Look at my proof. Induction for height. Let's ... 2answers 852 views ### AVL tree such that each insert causes rotation (single or double) Could you give me an example of an AVL tree for which inserting an element at an arbitrary (i.e. every) position causes a rotation (double or single)? I have tried to come up with an example, but I ... 1answer 338 views ### Two red children in a red-black tree My data structures exam contains the following question: Which of the statements below about red-black trees is true? (select one or more) Every path from the root to a leaf has the same ... 1answer 53 views ### Identify balanced and full binary search tree insert order I'm inserting numbers 1 thru 15 into a binary search tree one by one. I need to come up with an order to insert these elements for it to result in a full and balanced binary tree. I've tried to create ... 3answers 4k views ### Compute height of AVL tree as efficiently as possible Given an AVL tree, I want to compute its height as efficiently as possible.$\newcommand{\bf}{\text{bf}}\newcommand{\height}{\text{height}}$Each node of an AVL tree stores its balance factor ($\bf$),... 1answer 6k views ### How the deletion takes place in B+ Tree My professor was giving a lecture on B+ Trees deletion, and I got very confused. According to him for deleting any key from a B+ Tree: ... 1answer 907 views ### Delete a range of keys in a binary search tree in better than$O(n\lg n)\$?

Obviously, the brute force method of: ...
1answer
519 views

### Example of height-balanced tree that is not weight-balanced

Following this question : Two definitions of balanced binary trees I am having a hard time making sense of the proofs provided and I'm looking for an example of a simple binary tree that is height-...
1answer
1k views

### Imagine a red-black tree. Is there always a sequence of insertions and deletions that creates it?

Let's assume the following definition of a red-black tree: It is a binary search tree. Each node is colored either red or black. The root is black. Two nodes connected by an edge cannot be red at the ...
2answers
2k views

### Balance factor changes after local rotations in AVL tree

I try to understand balance factors change after local rotations in AVL trees. Given the rotate_left operation: ...