Questions tagged [binary-search-trees]
The binary-search-trees tag has no usage guidance.
168 questions
2
votes
1
answer
423
views
Proof that a subtree of a red-black tree has no more than $\frac{3n}{4}$ nodes
I have a red-black tree with $n$ nodes, rooted at $x$. How can I prove or disprove that the number of nodes in any subtree of $x$ (including the root of the subtree) will never be greater than $\frac{...
- 203
1
vote
1
answer
148
views
avl trees rotations question
As you can see in this tree its unbalanced at the root with a balanced factor of $-2$. You can also perform a Right left rotation or a Right Right rotation. Which do you have to pick in this case?
- 139
1
vote
1
answer
280
views
fixing a slightly broken BST tree
I'm stuck on this question, a BST is slightly broken only if there is a node with value x in which :
there is at least one value less than x on its right branch or atleast one value greater than x on ...
user99038
1
vote
1
answer
2k
views
Binary Search Tree – Number of comparisons when element is not found
I am confused regarding Binary Search Trees (BST) when an element does not exist in the tree.
For example, to search for element "6", would it take 5 comparisons to search for this element?
My ...
- 35
1
vote
1
answer
2k
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 ...
1
vote
1
answer
190
views
Searching in a Binary Search Tree
I'm studying Binary Search Trees (BST) and I would like to verify that my understanding of BSTs is correct.
For example, let S = [17, -10, 7, 19, 21, 23, -13, 31, 59].
Binary Search Tree for S, with ...
- 37
2
votes
2
answers
214
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 ...
- 21
2
votes
1
answer
598
views
How to find the number of Binary Search Trees with given number of nodes and leaves?
With 7 nodes of distinct values (unique), how many Binary search trees (BST) can be formed such that:
Exactly $1$ leaf node(s) present?
Exactly $2$ leaf nodes present?
I was able to solve the first ...
- 205
1
vote
2
answers
677
views
Deriving the average depth for a randomly generated binary search tree
If $D(n)$ is the internal path length (sum of the depths of all nodes) for some tree $T$ with $n$ nodes then we have the following recurrence relation: $$D(n)=D(i)+D(n-i-1)+N-1$$ where I simply taken ...
- 131
0
votes
3
answers
21k
views
Calculation of Inorder Traversal Complexity
I want to analyze complexity of traversing a BST. I directly thought that its complexity as $O(2^n)$ because there are two recursive cases. I mean $T(n) = constants + 2T(n-1)$. However, AFAI research ...
-1
votes
1
answer
298
views
All the possible inputs for a given AVL tree
Given an AVL tree,what are the possible inputs so that the same given tree is formed(please dont mention brute force technique)?
- 1
0
votes
1
answer
216
views
The validity of the potential function for splay tree
The paper "Self-Adjusting Binary Search Trees" defines (Page 658) the potential function for analyzing the amortized cost of a sequence of $m$ splay operations as the sum of the ranks of all nodes in ...
- 9,641
4
votes
1
answer
4k
views
BST representation of Hash Tables
I'm reading this book Cracking Coding Interview. In this book author is speaking about BST representation of Hash Tables.
I googled a lot for BST Representation of Hash Table. Code in C++ but didn't ...
- 209
3
votes
1
answer
7k
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 ...
- 43
1
vote
0
answers
102
views
Upper bound on the average path length in binary search tree
I have been reading the chapter 6.2.2 in Knuth's book about lower and upper bound on the average path length in binary search tree.
And I have problems with understanding small details of Theorem M (...
- 275
1
vote
1
answer
93
views
Example of binary trees with maximum rotation distance
In the 1988 paper Rotation Distance, Triangulations, and Hyperbolic Geometry, Sleator, Tarjan and Thurston show that for any pair of $n$-node binary trees, the maximum rotation distance between them ...
- 1,158
2
votes
1
answer
81
views
What is the average size of a jump in a binary tree?
Assume that a full binary tree is layed out in memory recursively in the following way.
First the Root followed by Tree representation of left subtree followed by tree representation of right subtree. ...
- 118
7
votes
3
answers
5k
views
If inorder traversal of a tree is in ascending order will the tree definitely be a BST?
For a binary search tree (BST) the inorder traversal is always in ascending order. Is the converse also true?
- 139
1
vote
0
answers
137
views
Splay Tree - Insert Permutation
Let $T$ be a Splay Tree. For a given permutation $\sigma$ on a set $S = \{1,2,3,...n \}$ we defined the following function:
...
- 111
0
votes
1
answer
138
views
Binary Tree Node Insertion
I was trying to implement a Binary Search Tree using this article as a reference: Binary Search Tree in JavaScript.
I was thinking especially about the node insertion method. Here's my ...
- 101
0
votes
1
answer
1k
views
All possible Red Black Trees with this set {1,2,3,4,5}
I have to write all possible Red Black Trees which can represent these 5 numbers {1,2,3,4,5}.
Now we have 120 ways to write 1,2,3,4,5
...
1
vote
1
answer
399
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 ...
user82869
5
votes
4
answers
4k
views
Why use binary search trees when hash tables exist?
Hash tables perform lookup, insertion, and deletion in O(1) time (expected and amortized) while the different variants of binary search tree (BST) - treap, splay, AVL, red-black - offer at best O(log ...
- 581
1
vote
1
answer
4k
views
Number of binary search trees with maximum possible height for n nodes
I'm using the definition of the height of a tree as the longest possible path from the root to a leaf by its number of edges, e.g. a tree of 2 nodes has a height of 1. With that in mind, what would ...
- 320
0
votes
1
answer
94
views
Complexity for find pairs with sum - BST
I have written an algorithm for find all the pairs in a BST which have a given sum.
...
- 271
1
vote
0
answers
34
views
Looped binary sorting tree
I want to add a points one by one into sorting tree. I have less then function to order them by angle from absciss: for points $\mathbf p_i = (x_i,y_i)$ and $\mathbf p_j = (x_j,y_j)$ it just sign of ...
- 165
-1
votes
1
answer
418
views
Simulating AVL Tree Right, then Left rotation
I have the following AVL tree and want to AVL-INSERT a node 5 into the tree. Since the middle branch will be unbalanced, I'm guessing that it will require a right rotation, then a left rotation to ...
- 320
0
votes
1
answer
46
views
k-means clustering with efficient point lookup?
What's an algorithm for $k$-means clustering, in particular an online algorithm (you can stream new points to it), such that once the size of the set of clusters $k$ becomes large, we can still ...
- 548
0
votes
1
answer
1k
views
Time complexity of creating the unique binary tree from given inorder and preorder (or postorder) traversal sequences
Given inorder and preorder (or postorder) traversal sequences of a
binary tree
balanced binary tree
binary search tree
of n nodes, what is the time complexity of creating the respective unique tree.
2
votes
0
answers
359
views
How many similar binary search trees are made from different permutations?
If I have numbers ranging from 1 to n, and I generate all the permutations of these numbers. Now, I create Binary search tree from these permutations. For a value n i want to know how many BSTs would ...
1
vote
1
answer
314
views
Generate a unique number for a set of sequences of letters
A sequence of English letters are given, every sequence forms a word and we know that the size of each word is at most $15$ and the number of words is at most $50000$. For a given input word $w$ I ...
- 1,529
0
votes
0
answers
61
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?
- 101
4
votes
2
answers
27k
views
Which of the following sequences could not be the sequences of nodes examined in a binary search tree?
Suppose that we have numbers between $1$ and $1000$ in a binary search tree and want to search for the number $363$. Which of the following sequences could not be the sequences of nodes examined
<...
- 143
-1
votes
2
answers
4k
views
Time complexity of searching an element in Binary Search Tree [closed]
I want to know what will be the time complexity to search, insert and delete an element in
a) balanced binary search tree.
b) unbalanced binary search tree.
- 5
1
vote
1
answer
672
views
Rooted Binary Tree - Chain Nodes Algorithm
The question is that I have to give a recursive algorithm in pseudocode, that counts the number of chain node in a rooted binary tree. Chain node is defined as a node that has only one child and that ...
- 23
0
votes
0
answers
137
views
An AVL tree is a BST, but AVL tree can be not complete, then why do we define AVL tree a BST?
An AVL tree is a BST, and a BST is a complete tree, but AVL tree doesn't necessarily have to be complete. Thus, why do we define AVL tree a BST?
- 335
0
votes
1
answer
546
views
Is there an example of an AVL tree that is taller than a binary heap?
I am curious because I took a quiz and answered false to the question:
"The height of an AVL tree may be greater than the height of a binary heap with the same elements."
I have been trying to think ...
- 113
0
votes
1
answer
943
views
When to rebalance the AVL tree?
Consider we have an AVL tree.
Its left subtree A has disbalance coefficient has value +1 (meaning the right subtree has greater depth). Its right son has disbalance coefficient -1 (meaning left ...
- 1
1
vote
0
answers
36
views
Read nodes of a BST in blocks of size $k$ and traverse it in $\mathcal{O}(log_kn)$
This describes how one can neatly store a binary search tree as an array. I'm looking for a way to store a BST that will allow me to traverse any root to leaf path by loading $\mathcal{O}(log_kn)$ ...
- 427
2
votes
1
answer
138
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 ...
- 21
1
vote
0
answers
1k
views
Day-Stout-Warren algorithm for balancing BST. How does vine to tree work?
I was trying to understand the dsw algorithm for balancing a binary search tree in-place using this virgina tech page.
The wikipedia page and vt page are more or less similar. I am having a hard time ...
- 111
6
votes
2
answers
557
views
Balanced Binary Search Tree Two-Sum with Constraints
My question spawns from this question. The question is straightforward:
Can we find whether there exist 2 values in a balanced binary search tree where their sum equals a given target value?
Now ...
- 4,523
0
votes
0
answers
516
views
How to find point of maximum overlap in both X and Y Axis?
I was given a array R of n rectangles [each element in the array is a bottom left point(x1,y1) and a top right point (x2,y2)] , parallel to the axis, and an array P of n points [each element is a ...
- 1
2
votes
0
answers
120
views
What would be the probabilty of a randomly generated tree to be a Red-Black Tree
The question is not related to the homework
I was working on a homework, and the specification was to generate a random tree with n elements(n being in the thousands for the assignment) and asked me ...
- 171
10
votes
1
answer
2k
views
Data structure for handling intervals
I am trying to create a data structure for handling the subsets of the real line of the form $[x,y)$. That is, suppose $X \subseteq \mathbb{R}$ and the data structure supports two types of operations: ...
- 101
0
votes
0
answers
41
views
Binary Search Tree: If two different traversals are given, will there be a unique tree that satisfies the traversals? [duplicate]
I have come across algorithms that can create a BST if any two of the 3 traversals are given (there would be three different algorithms for the 3 combinations)
This is an example
I was wondering, is ...
- 113
1
vote
1
answer
87
views
A data structure for holding numbers in 2 sets, using BST?
Design a data structure for holding numbers in two sets:
Init - initiate the DS with two empty sets. O(1)
Insert(a,S) - insert number ...
- 51
1
vote
1
answer
2k
views
Rotations in a treap
I have a treap like the first image and I want to reach the second image to restore min heap order property. I can't understand which kinds of rotations have been done.
Image 1
Image 2
- 131
2
votes
1
answer
92
views
Efficient search algorithm for a monotonic boolean array wherein the probability of target's location is available apriori
A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$.
$$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in ...
-1
votes
1
answer
700
views
Binary search trees: multiple `Successor()` calls
Show that, given a tree node a, the time complexity of calling k times to Successor() is $O(k+h)$, where $h$ is the tree height.
...
- 327