Questions tagged [binary-search-trees]
The binary-search-trees tag has no usage guidance.
105
questions
0
votes
1answer
21 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
47 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
54 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
1answer
29 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
13 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
38 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
14 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
34 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
14 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
167 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 ...
0
votes
0answers
102 views
Calculate number of nodes in all subtrees without using DFS
Is it possible to calculate the number of nodes using post-traversal order, instead of using DFS?
Below is an illustration of the question:
0
votes
0answers
13 views
Data structure for revising ordering given a (largely) ordered stream of data
I have an input stream of timestamped data that is largely sorted in ascending order by timestamp. There are occasionally out-of-order elements, at which point I need to do each of the following:
...
1
vote
0answers
172 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
0answers
31 views
How many Binary Search Trees are there which have N nodes and their height is log N
How many Binary Search Trees are there which have N nodes and their height is log N ? We need a recursive function to solve this problem. For example if n=2 the answer is 2. If n=3 answer is 1 . If n=...
0
votes
1answer
398 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
42 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
42 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
247 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
35 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
40 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
107 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, ...
0
votes
1answer
193 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 ...
0
votes
2answers
42 views
creating a binary search tree (manual)
I've been given the following values to add to a binary search tree (in the order given)
56, 35, 55, 58, 29, 15, 16, 5, 71, 92, 69, 95
and this is what my tree ended up like:
but apparently it's ...
-1
votes
2answers
32 views
post order for binary search tree
I got this as the post order sequence but the answer says it is wrong. I do get a bit confused with the post order logic as well.
8 11 10 9 13 16 18 15
2
votes
1answer
34 views
in order of binary search tree
This is what I got for the in-order of the bst but it's wrong because I'm answering some questions about some successors of some of the letters and I got them wrong. so I'm wondering where in this in-...
0
votes
1answer
422 views
How is the right, root, left order traversal called in a binary search tree?
In a Binary Search Tree you have the following orders for traversal:
Left, Root, Right is called Inorder (or ascending order).
Root, Left, Right is called Preorder.
Left, Right, Root is called ...
0
votes
2answers
2k 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 ...
0
votes
1answer
58 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?
As far as I know, in red-black tree we also consider the leaf nodes at the NULLS of the visible leaf nodes ...
0
votes
0answers
31 views
RB trees from any balanced BST?
Given any perfectly balanced binary search tree, is it always possible to assign a coloring to the nodes so that it becomes a Red-Black tree? If so, how do you prove this, and if false, what would be ...
0
votes
1answer
27 views
AVL tree balance property states for the two subtrees of a node, their height can differ at most one. Why can't it be zero?
I was thinking that if they were equal, say they are required to be zero this would be enforce the balance property more effectively. Can anyone explain why 1 is a satisfactory rather than just them ...
1
vote
3answers
1k 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?...
0
votes
1answer
73 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 ...
0
votes
0answers
35 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 ...
0
votes
0answers
177 views
Tracing BST Pseudocode for Insertion
I'm having real trouble tracing some pseudocode for insetion into a Binary Search Tree. I need to understand this in order to be able to teach it, but I think there are flaws in the material.
For ...
0
votes
2answers
47 views
Algorithm for searching in BST with only <
How could one construct an algorithm for finding a node in a binary search tree that only requires the presence of $<$ on the key type. The ones I can easily also requires $=$.
0
votes
1answer
34 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$ (...
2
votes
1answer
193 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{...
0
votes
1answer
87 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?
1
vote
1answer
143 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 ...
1
vote
1answer
696 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 ...
1
vote
1answer
661 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
1answer
94 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 ...
3
votes
2answers
136 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
236 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 ...
1
vote
2answers
277 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 ...
0
votes
2answers
3k 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
1answer
164 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)?
0
votes
1answer
84 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 ...
4
votes
1answer
1k 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 ...
2
votes
1answer
2k 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 ...
