All Questions
Tagged with binary-search-trees trees
23 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 ...
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
49
views
Is binary tree balanced if and only if the morris traversal of the tree produces ordered list?
I'm trying to check if the binary tree is binary search tree. My idea is to use Morris traversal. Intuitively a binary tree is balanced iff Morris traversal produces a sorted threaded linked list.
The ...
- 105
5
votes
0
answers
83
views
Completeness of red-black tree operations
Red-black trees are defined to have the following invariants:
The nodes are in sorted order (it is a binary search tree).
The root is black, and leaves are black.
Every red node has black children.
...
- 541
3
votes
0
answers
363
views
Is there a way to parallelise find and inserts for a binary search tree?
Background: I'm working on a data structure benchmark tool to benchmark insert and search time and I am trying to improve my own implementation of a BST to support parallelism.
I have implemented a ...
- 131
0
votes
1
answer
109
views
I think I have discovered a new sorting algorithm using binary search tree [closed]
If we some how transform a Binary Search Tree into a form where no node other than root may have both right and left child and the nodes the right sub-tree of the root may only have right child, and ...
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
0
votes
0
answers
136
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 ...
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
801
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 ...
- 13
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
0
answers
49
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 ...
- 103
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
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
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
1k
views
Binary Search Tree Stability Data Structure
After constructing a binary search tree, you can read off the key values in ascending order by performing an in-order traversal.
Will the resulting sorted order be stable?
If so, how would the tree ...
- 121
0
votes
1
answer
366
views
Merging two binary search tress
You have two binary search trees A and B, each one is a complete binary tree containing $2^k-1$
nodes. The maximum value of the keys in the tree A is less than the minimum value of the keys
in tree B. ...
-3
votes
1
answer
9k
views
Constructing binary search tree from given data
The data are in alphabets.
U, N, I, V, E, R, S, I, T, Y, O, F, P, O, K, H, A, R, A.
Perform pre, in and post order traversals.
I'm confused as how to construct it in the 1st place. Only sense i ...
- 1
2
votes
1
answer
2k
views
Should all internal node keys in B+ tree also be in the leaves?
I was reading about B+ tree insertion.
The algorithm takes following form:
Insert the new node as the leaf node.
If the leaf node overflows, split the node and copy the middle element to the parent ...
- 1,773
2
votes
1
answer
4k
views
Facts about internal and external path lengths of binary tree
While learning binary tree's properties, I came across internal path length and external path length, number of comparisons required for successful and unsuccessful search.
My book specifies some ...
- 1,773
3
votes
1
answer
756
views
Binary Search Tree Traversal output validity and unique BST construction
I had two specific type of questions involving Binary Search Tree (not simple Binary Tree) traversals :
Given x-order traversal output of BST, can we state if it is valid or invalid output?
(For ...
- 1,773