Questions tagged [binary-search-trees]
The binary-search-trees tag has no summary.
170 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
0
votes
0
answers
35
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.
...
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 ...
1
vote
1
answer
114
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 ...
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, ...
3
votes
1
answer
740
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 ...
-1
votes
1
answer
66
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 ...
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, ...
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 ...
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 ...
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
113
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
210
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 ...
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 ...
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 ...