Questions tagged [binary-search-trees]
The binary-search-trees tag has no summary.
170 questions
0 votes
0 answers
37 views
What is the name and theoretical basis for a Treap/RBST variant with a probabilistic, size-based merge?
I'm exploring data structures suitable for persistent applications. A key use case I have is splitting a subsegment from a tree, copying it, and then merging these copies into other data structures. ...
- 1
0 votes
1 answer
58 views
Can red-black tree augmentations depend on other augmentations and still be maintainable in O(logn)?
by "augmentation" i mean adding an additional field to each node. All sources i found say something that falls into one of two categories: "A field f in a red-black tree can be ...
- 3
1 vote
1 answer
116 views
Explain why the condition "NIL need to be black" exists in RED-BLACK tree definition
I know there's another question asking the same in this website, but answers to that question was not clear; it did not help me. In this wikipedia page, the 2nd property says "All NIL nodes are ...
- 113
2 votes
2 answers
123 views
which rotation to perform in a AVL BST when the tree is quite crowded?
When I'm faced with a simple tree like the one in the picture, it's very easy to decide whether to do a single rotation or a double rotation. However when the tree is very crowded, like this picture, ...
- 165
3 votes
1 answer
741 views
Binary search tree with height of max 1.44 * log(n) is AVL tree or it's not an iff
Assume I have a binary search tree, and I managed to prove that its height is upper bounded by $1.44 \log(n)$. Now, can I say with confidence that it is, for sure, an AVL tree? or is this condition ...
- 33
-1 votes
1 answer
67 views
What formula was used here to calculate the average search time of the binary tree?
My teacher showed me the following slide on the PowerPoint with two binary search trees and their corresponding "average search times". The PPT did not mention what formula was used to ...
- 119
0 votes
0 answers
132 views
Closed-form for exact number of iterations of binary search
Consider a sorted list of $n$ elements $x_1, \ldots, x_n$. Using binary search to find $x_k$ in this list takes $f(n, k)$ iterations, where $f : \mathbb{N}^2 \to \mathbb{N}$ is a function such that, ...
- 103
0 votes
1 answer
101 views
Can this Binary Search Tree be optimal with $x$ expected comparisons?
I was given this Binary Search Tree. The question asks whether this tree can ever be optimal with $2.1$ expected comparisons, and I am completely lost on how to even approach this problem. Trying to ...
- 1
2 votes
2 answers
239 views
Prove that balanced binary search tree has lowest expected cost
Take numbers from 1 to 100. Put all of them in a binary search tree. Now, one of those 100 numbers is picked uniformly at random and given to us. We'd like to find it in the binary search tree. The ...
- 397
0 votes
2 answers
199 views
Recursive formula for height of BST
Let $H(n)$ be the average height of a BST with nodes from ${1,...,n}$. I think that $$H(n) = \frac{1}{n}\sum_{i = 0}^{n-1}\left[\text{max}(H(i), H(n-1 -i)) + 1\right]$$ But I don't know how to prove ...
0 votes
1 answer
114 views
Time Complexity: Determining if a binary tree is balanced
I found an algorithm for determining if a binary tree is height-balanced. It Gets the height of left and right subtrees using dfs traversal. Return true if the difference between heights is not more ...
1 vote
1 answer
214 views
Does a sorted sequence from in-order traversal imply a binary tree is a BST?
An in-order traversal of a binary search tree (BST) produces a sorted sequence. I wonder, if we perform an in-order traversal of a binary tree and obtain a sorted sequence, does that imply that the ...
- 187
0 votes
0 answers
54 views
Create a class or structure like union of ranges
How to create a structure which acts as union of ranges. In that structure new ranges can be inserted beforehand and then some queries are asked to find out if the given point is covered by any of the ...
0 votes
1 answer
92 views
Is binary tree balanced if and only if the morris traversal of the tree produces ordered list?
I'm trying to check if the binary tree is binary search tree. My idea is to use Morris traversal. Intuitively a binary tree is balanced iff Morris traversal produces a sorted threaded linked list. The ...
- 105
0 votes
1 answer
98 views
Splay Trees - Sequential Access Theorem & lower bound for comparison-based sorting
The following theorem was proven by R.E. Tarjan in 1984: Theorem (Sequential Access Theorem). If we access each of the nodes of an arbitrary initial tree once, in symmetric order, the total time ...
