Questions tagged [binary-search-trees]
The binary-search-trees tag has no usage guidance.
133
questions
0
votes
1answer
10 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 ...
0
votes
1answer
30 views
What's the sum of heights of a random binary search tree
What's the sum of heights of a random binary search tree?
By a random binary search tree, I mean the usual definition: you have $n$ keys to be inserted, and all Permutations are equally likely.
The ...
0
votes
1answer
27 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. ...
0
votes
1answer
64 views
Height of AVL Tree
I found an AVL tree implementation on the internet and experimented:
For a tree with node count of 2^20, the minimal and maximal tree heights are 16 and 24.
While these heights are lg(n)-ish, I am ...
0
votes
0answers
18 views
Two variants of the BST remove algorithm
I have seen two variants of the BST remove algorithm in the case where the node to be removed has both children.
Variant 1:
Replace the node with the right-most child in the left subtree
Variant 2:
...
1
vote
3answers
318 views
How does the Inorder-tree-walk algorithm move to a different node after hitting a leaf?
A friend and I did the Inorder-tree-walk with pen and paper.
We both can't figure out how the algorithm would move 'up' the tree again upon hitting a leaf:
We are using the algorithm as described by ...
0
votes
0answers
10 views
Comparing the added cost of replacing a map with an extra Merkle tree to provide non-membership proofs
Here is the trade-off:
-Merkle trees that append leaves to the right tend to have a better Locality of reference, and thus shorter batch proofs (a lot of sibling nodes will be common and thus fetched ...
1
vote
1answer
69 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 ...
0
votes
0answers
38 views
Rebalance the following AVL tree after inserting G. You need to show the middle step if it happens. Briefly explain the operations
I recently learned AVL Trees but I still lack a complete understanding of the concept. I understand that an AVL tree is a Binary search tree that checks for the height of the tree, but I still don't ...
1
vote
3answers
339 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
1answer
53 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 ...
1
vote
1answer
51 views
Minimum absolute difference in a BST is always between
Given a Binary Search Tree(BST) I would like to understand can absolute minimum difference between any two nodes of a BST is always between adjacent nodes. If Yes or No can we generalize it ? Assume ...
0
votes
1answer
83 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
1answer
31 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 ...
0
votes
0answers
36 views
Calculating the expected height of a randomly built binary search tree
I need to calculate the expected height of a randomly built binary search tree, BST, with 4 different keys: $x < y < z < w$
According to Catalan numbers, there are 14 possible trees, 8 with ...
0
votes
1answer
39 views
Finding 2 nodes which sum equals twice their common ancestor in RBT in $\Theta(n\lg n)$
I have a red black tree, $T$, and I need to write an algorithm to find 2 nodes $x$ and $y$ so that $key[x] + key[y] = 2 \cdot key[p(x, y)]$, where $p(x, y)$ is the lowest common ancestor of $x$ and $y$...
1
vote
1answer
92 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 ...
0
votes
0answers
32 views
BST deletion of node with 2 children by copying right child to predecessor
I try to delete a node, $z$, with 2 children in binary search tree by exchanging $z$'s right child and $z$'s predecessor, $y$, right child, which is NULL because $y$ has no right child, if it had then ...
0
votes
0answers
86 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 ...
0
votes
0answers
49 views
Average depth BST upper bound
I have a question regarding the BST average depth upper bound. Following the proof from Data Strucutures and Algorithms in Java by Weiss (3rd edition), I was wondering if there was some kind of ...
1
vote
1answer
85 views
For a balanced binary search tree what is the worst case case time complexity for accessing all elements within a range of nodes?
I have this question which is asking for the worst case time complexity for a balanced binary search tree, assume the nodes are labeled as integers and we consider a range of ...
0
votes
1answer
28 views
Converting Binary Search Tree into Decreasing Ordered Linked List
Given a BST with n nodes, the algorithm should create a linked list that contains a decreasing order sorted array. The algorithm should have a worst case time complexity O(n). The signature of the ...
1
vote
1answer
54 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:
...
-1
votes
1answer
41 views
Are there any trees where Preorder$(T_1) =$ Preorder$(T_2)$ and Inorder $(T_1) = $Inorder $(T_2)$, but $T_1 \neq T_2$?
Is it possible for two binary trees $T_1 \neq T_2$ that both Preorder and Inorder traversal are equal ?
1
vote
1answer
115 views
Prove a statement about searching in binary search tree
Suppose search $n$ times in a given binary search tree $T$ with $n$ nodes. each searching have cost $C_i$, and $\sum_{i=1}^{n}C_i=O(n\log n)$. Now the problem is to find height of $T$. I think it be $...
0
votes
0answers
45 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 ...
0
votes
1answer
58 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)$ ...
1
vote
1answer
72 views
Cormen problem 13-1 part d
I am going through problem 13-1 in CLRS 3rd edition. I came up with the following algorithm as a solution:
...
0
votes
1answer
298 views
prove correctness of in-order tree traversal subroutine
I'm trying to prove that in-order tree traversal prints the keys in sorted order. it's shown here, but what I want is to prove correctness using ordinary induction.
Claim: For any n-node subtree, ...
1
vote
2answers
408 views
is it possible to create an avl tree given any set of numbers?
I am studying balanced trees, especially AVL trees. My question is whether is it possible to create an avl tree given any set of numbers. is it possible to prove the following statement?
Let $A$ be ...
0
votes
1answer
904 views
Find amount of elements greater then number k in a BST
I am trying to find an Algorithm to find the amount of elements in a BST which are greater than a certain number K.
I found it problematic as there are elements which might be greater then K but wont ...
0
votes
0answers
34 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).
...
1
vote
1answer
627 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 <...
1
vote
1answer
353 views
Recurrence formula for optimal binary search tree
This question is from Section 15.5 of Introduction to Algorithms (third edition).
We are given sequence of keys, $ k = \{ k_{1},k_{2},\dots,k_{n} \}$, where $k_{1}<k_{2} <\dots<k_{n} $.
For ...
4
votes
0answers
75 views
Understanding the Transition points of a BST
I'm trying to understand the definition of Transition point of a BST, as given in Demaine, Erik D., et al. "Dynamic optimality-almost." SIAM Journal on Computing 37.1 (2007): 240-251
...
1
vote
2answers
57 views
What factors of the integer dataset being sorted can I change, in order to compare two sorting algorithms?
I am comparing two comparison and binary data structure based sorting algorithms, the Tree Sort, and the Heap Sort. I am measuring the time taken for both algorithms to sort an increasing size of an ...
1
vote
0answers
34 views
Splay tree amortized analysis cost using Access Lemma
Currently studying for an algorithms exam and I came across this question and solution, but I can't understand the solution where it references nodes of depth less than $4\log n$ and not restructuring....
0
votes
2answers
42 views
Call stack is hard to maintain in my brain. What should I?
When I study Binary Search Tree, I try to use a pencil and paper to scratch the process of in-order traversal. However, I find that it is hard to maintain the call stack in my brain without paper and ...
0
votes
1answer
17 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$ ...
0
votes
1answer
57 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-...
0
votes
0answers
15 views
Parent Node in BST
Is it a good idea to store a pointer to the parent node in a binary search rather than to find the parent node several times?
...
0
votes
1answer
303 views
Remove range of keys from Binary Search Tree in O(s+h)
I have a binary search tree with integer keys. I have to remove a range (m, n]eZ of keys from the BST in O(s + h)
where s is the number of keys to remove and h is the height of the tree.
Attempted ...
1
vote
0answers
580 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 ...
0
votes
1answer
839 views
How to find time complexity of this pseudocode
Recently, I came across a question about finding sum of all values in range $[low, high]$ in BST $T$.
Then I formulated following algorithm to carry out that task:
We do inorder traversal of ...
1
vote
2answers
45 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:
...
2
votes
0answers
49 views
Reasoning for awkward style of TreeMap.getHigherEntry
Consider a binary search tree (AVL, red-black, whatever). The goal "find the least key strictly greater than the specified one" ("upper_bound" in C++ STL, higherEntry//higherKey in Java, etc.) can be ...
0
votes
1answer
546 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 ...
1
vote
1answer
49 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).
0
votes
1answer
52 views
How to construct a perfect BST from an unbalanced BST with n elements (assuming that n=(2^i)-1, i is natural)
How do I construct a perfect BST from an unbalanced BST with $n$ elements (assuming that $n=2^i-1$, $i$ is natural). ** At the worst case of $O(n)$**.
2
votes
1answer
121 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, ...
