All Questions
Tagged with binary-search-trees binary-trees
55 questions
-1
votes
1
answer
23
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
26
views
I don't understand the reason behind O(h) time complexity in this MIT OCW Algorithms question
I faced the following question in a problem session: Gal Ore is a scientist who studies climate. As part of her research, she often needs to query the maximum temperature the earth has observed within ...
2
votes
2
answers
159
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 ...
- 375
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
0
answers
31
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 ...
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
1
vote
1
answer
176
views
Randomly generated binary search trees case comparison
Although not an assignment, just out of curiosity; I am trying to compare a two cases
A scenario where I pick a tree out of the set of possible binary search trees on the keys $1,2,\ldots,n$, with ...
- 33
1
vote
0
answers
34
views
What is the gold-standard description of the 2-3 tree (search, insert, delete)?
After several hours of frustration, I finally realized that the definition of two-three trees aren't standard (my lecture notes, this video, this other video, and Wikipedia) are different. My lecture ...
- 111
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
3
votes
1
answer
207
views
Using pre-,post-, and in-order indexes to find information about a Binary Search Tree
Recently I have been studying ways of traversing a BST (in python), and have collided with the terms pre-order, post-order and in-order.
I believe that I understood the three terms pretty well, and ...
- 189
3
votes
1
answer
327
views
finding an algorithm for creating a priority search tree in linear time with presorting
A priority search tree is a binary tree satisfying the following:
every node $u$ stores a point $p_u = (x_u,y_u)$
every nonleaf $u$ stores an x-coordinate $x_u'$ called the split-line coordinate.
If $...
- 207
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
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
0
votes
1
answer
676
views
When can a (max) heap be a BST?
Cheers, let's suppose we have a MAX heap which does not allow duplicate elements. Is it possible for this heap to be a BST ? Choose the right answer(s) below:
A heap can never be a BST
A heap is ...
0
votes
1
answer
120
views
Find two nodes in a BST such that the root's key is the average of their keys without extra space in $\theta(n)$ worst case time
We can do this in $\theta(n^2)$ time if we calculate the average of all couples of nodes in the tree and compare it to the root, but this is too much time.
We can do this in linear time but with extra ...
- 243
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
0
votes
0
answers
135
views
Probability that BST has exact height
Consider keys $[ 1 \ldots n]$. We want to calculate probability that BST tree has height = $h$.
(We assume that distribution is uniform over all $C_{n}$ trees, where $C_n$ - n-th Catalan number).
...
- 151
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
205
views
How many different (full/complete) in-order binary-trees do exist?
Given be a binary tree whose elements printed in-order results in [1,2,3,4].
Q1: How many different binary-trees do exist?
Q2: How many different complete binary-...
- 111
2
votes
0
answers
1k
views
Algorithm to delete BST nodes with duplicated values
In a binary search tree the following must hold:
Greater keys are in the right-subtree
Smaller or EQUAL keys belong to the left-subtree
All the algorithms I found to delete a node start by finding ...
- 121
1
vote
2
answers
77
views
Inorder tree tranversal on binary search tree doesn't give the elements in order?
I have been told that inorder tree tranversal of binary search trees returns the tree elements in order. I came up with this binary search tree:
...
0
votes
1
answer
1k
views
Constructing preorder traversal from postorder of a Binary Search Tree in O(n)
We are given postorder traversal of a Binary "SEARCH" Tree (in an array) and we want to find (print) its preorder traversal.
A very naive solution is to check from end until we find element less than ...
- 145
1
vote
1
answer
64
views
question about the construction of BSTs using a repeated sequence of rotations
How can I show that any binary search tree can be balanced with at most O(n log n) rotations (“balanced” here means that the lengths of any two paths from root to leaf differ by at most 1).
- 107
2
votes
1
answer
158
views
Height of epsilon-balanced binary search tree
In Balanced Binary Search Trees on the basis of size of left and right child subtrees, Hannes says:
For example, one can say, a BST is balanced, if each subtree has at
most epsilon * n nodes, ...
- 143
0
votes
2
answers
1k
views
Leaf nodes of B+ Tree
I have a b+ tree and i want to find the record associated with a specific key Ki.
So i run the b+ tree search algorithm. If a certain node in the search path is a leaf and K=Ki, then the record exists ...
- 123
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
0
answers
70
views
Finding Binary Search Tree Height, What happens to duplicates?
I'm going over past exam papers with this question:
The answer to a). will be (height of 5):
For b.):
I assume the height function will be to find the height of the tree. So, I will have to compare ...
- 15
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
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
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
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
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
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.
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
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
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
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
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
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
4
votes
3
answers
707
views
What purpose do the leaves in a range trees serve?
I'm getting into algorithms and I came upon range trees. What confuses me is the leaves in a range tree, since for example:
When you remove the leaves:
It's just a regular BST.
And, every ...
