All Questions
Tagged with binary-search-trees data-structures
56 questions
3
votes
1
answer
671
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
0
votes
2
answers
148
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 ...
1
vote
1
answer
115
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
1
answer
54
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 ...
2
votes
1
answer
193
views
Visualizing How of KD-tree Data Structure Splits Space
I am trying to understand how KD-tree works when we insert a node and how it splits the xy plane, please. Below $[5, 4]$ splits the xy-plane into left and right parts while $[2,6]$ splits it into top ...
- 515
0
votes
0
answers
31
views
How many times is a node rotated towards the root in a weight-balanced tree?
In this paper they prove that the number of rotations after doing $n$ insertions or deletions to a weight-balanced tree is $O(n)$ (when starting from an empty tree).
What isn't clear to me though is ...
- 553
0
votes
1
answer
145
views
Did I invent a new data structure?
I needed to implement a priority queue for a project I'm working on and had this idea. In a priority queue BST implementation wouldn't it be more efficient if the poll node pointed to its parent since ...
2
votes
1
answer
131
views
Solution Verification: How does the postorder traversal of a BST change after rotating left?
Given a BST $T$, $x$ is a random node in it and $y$ is the right child of $x$.
How does the PostOrder traversal of BST $T$ change after we rotate the tree left on node $x$? In which cases does the ...
- 164
0
votes
1
answer
59
views
Which particular data structure should I use if I want a persistent balanced search tree?
As title, I'm trying to implement a text editor with the rope data structure, which is backed by binary search tree.
Since I want it to have persistent undos, the underlaying data structure should ...
- 3
1
vote
1
answer
279
views
Interval Tree by Augmenting an AVL Tree
According to Wikipedia: An augmented tree can be built from a simple ordered tree, for example a binary search tree or self-balancing binary search tree, ordered by the 'low' values of the intervals. ...
- 135
2
votes
1
answer
144
views
How to join two Scapegoat Trees in O(log n) time?
I am working on some binary-search-tree research and was surprised to find no mention of an algorithm to join two Scapegoat Trees. This is where two trees $L$ and $R$ are joined to create a single ...
- 203
1
vote
3
answers
2k
views
The number of ways of insertion in binary search tree
The number of ways in which the numbers $1,2,3,4,5,6,7$ can be inserted in an empty binary search tree, such that the resulting tree has height 5, is _________.
Note: The height of a tree with a ...
3
votes
1
answer
101
views
Observations about the structure of an optimal Binary Search Tree
My question is about part 15.5 in CLRS (third edition)*, on optimal binary search trees.
I am confused about the following sentences:
Consider any subtree of a binary search tree. It must contain ...
- 133
1
vote
1
answer
361
views
Splay Tree: Repeatedly searching for the same key that's not in the Tree
In a splay tree, doing $m$ sequential search operations for the same key that is in the tree has a time complexity in $O(n+m)$ where n is the number of nodes in the tree. Since the first search has a ...
- 13
0
votes
0
answers
99
views
Suggest a Data Structure that support the following operations with time complexity O(log(n))
I’m looking for a data structure that supports that store the salaries of it’s employees.
Insert(e) – Insert employee e into the data structure.
AvgDecile(k) – Returns the average salary of the k’th ...
1
vote
1
answer
69
views
If a key in a red-black tree has exactly one child (which isn't null) then it is always red
I have the following claim:
Prove or disprove: If a key in a red-black tree has exactly one child (which isn't null) then it is always red.
My attempt:
Disproof.
We will exhibit a counterexample:
...
- 123
1
vote
0
answers
82
views
Finding height of binary search tree
Suppose given a binary search tree $T$ with $n$ nodes with depth $h$.
We did $n$ times search with cost $c_i$ for search $i^{th}$ search on
$T$ ,and $\sum_{i=1}^{n}c_i=O(n\log n)$. what we can say ...
user132812
0
votes
1
answer
64
views
Check two balanced binary search trees that sub set of each other
Given two balanced binary search trees $T_1,T_2$. We want to check,
are $T_1\subseteq T_1$ or not. $T_1$ have $n_1$ nodes, and $T_2$ have
$n_2$ nodes.
Instructor say it can be done in $O(n_1+n_2)$ ...
user132812
2
votes
1
answer
3k
views
What exactly is the difference between a Balanced Binary Search Tree and an AVL tree?
I'm learning some Data Structures and I cannot figure out the difference between the Balanced BST and the AVL Tree. From my understanding, an AVL tree is a balanced tree with the height difference <...
- 469
0
votes
1
answer
20
views
Maintaining balanced BSTs in order to get $\frac{n}{2}$ largest elements in constant time
I wonder what is the best data structure I can use in order to achieve the following:
Given a data structure based on a balanced BST, I would like to get a tree with the $\lfloor\frac{n}{2}\rfloor$ ...
- 131
1
vote
2
answers
6k
views
Time complexity for balancing an unbalanced binary tree
The question here is that: There is an unbalanced binary tree with n-nodes. What is the time complexity to balance the tree?
The solution I thought of involved solving using Recursion where for the ...
- 83
0
votes
1
answer
567
views
Is the tree shown a valid red-black tree?
I have made a red-black tree and I think that it is not valid. Could someone please verify?
...
4
votes
3
answers
6k
views
Why is Binary Heap never unbalanced?
My professor asks this question: Binary Search tree has Rotation Method to prevent it from degenerating into a linear structure (unbalanced tree). Why is there no need for such method for Binary Heaps?...
- 141
0
votes
1
answer
142
views
Which binary search trees have constant time rebalancing time at min/max?
Given that I'm already at either the min or the max node of a binary search tree, which balanced variant would require only constant time bottom-up rebalancing after an update (add new min/max, or ...
- 203
0
votes
1
answer
42
views
Augmenting a tree such that we preserve the insertion operation optimal runtime
Suppose we are given a red-black tree with $n$ vertices with distinct keys and we want to store, as addition information in each vertex $v$, the biggest key out of the keys that are smaller than $v$ (...
user101904
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
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
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
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
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
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
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
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
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
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
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
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
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
10
votes
4
answers
41k
views
What is "rank" in a binary search tree and how can it be useful?
I am having a bit of trouble wrapping my mind around what a ranked binary search tree is and why having a rank is important. I am hoping that someone can clarify a few things for me.
What I have ...
- 245
1
vote
1
answer
393
views
Remove from black/red tree subtree with red root, red sibling and black parent in $O(\lg n)$
How can i remove from a red/black tree a subtree whose root and its sibling are red, and their parent is black, in $O(\lg n)$ time, while keeping the red/black properties at the end of the process?
...
- 121