Questions tagged [binary-search-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
1k views

What is the advantage of leaf trees vs. node trees?

In the book "Advanced Data Structures", Chapter 2 ("Search Trees"), the author, Peter Braß, mentions two versions of binary trees (emphases in the quoted text are mine): "...two different models ...
3
votes
3answers
94 views

BST - Sufficient condition for connecting a node to a parent

Let's assume that we have a binary search tree with node Y that hasn't a right child and for whom a successor exists in the tree. I want to prove that if I insert a node X into the tree and node X is ...
2
votes
1answer
69 views

Randomized BST height analysis : How $Z_{n,i}$ and $Y_{k-1}$ are independent?

I am referring to this video https://www.youtube.com/watch?v=vgELyZ9LXX4 at 1:08:39 . $n$ : number of nodes in the tree $Z_{n,k}$ : Indicator random variable that activates when rank of the root ...
2
votes
1answer
1k views

Average height of a BST with n Nodes

I have to find the maximum, minimum, and average height of a BST with n nodes. After doing some researching I found that the maximum height is $n-1$ and the minimum height is $\log_2(n+1)-1$. My ...
1
vote
1answer
466 views

AVL Tree rotations : How to balance below AVL Tree with imbalance at root node

How to balance this AVL tree after inserting node 5, using left/right rotations as indicated in the AVL tree tutorial. I have tried applying both double rotations but with no luck. Either of the ...