Questions tagged [binary-search-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
46 views

How does depths of nodes change after left-rotation in a BST (Exercise qustion from Cormen)

Let a,b,c be arbitrary nodes in the subtrees $\alpha$, $\beta$, $\gamma$, respectively, in the left tree of Figure 13.2. How do the depths of a,b,c change when a left rotation is performed on node x ...
user avatar
  • 109
0 votes
0 answers
15 views

How can I get the overall winner's leaf node in a loser tournament tree used for k-way merge?

I've read the wikipedia that has some insight on how a loser tournament tree ought to be constructed, but I'm confused as hell by the pseudo-code shown. How are you supposed to get the overall winner'...
user avatar
  • 113
0 votes
0 answers
26 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 ...
user avatar
-1 votes
0 answers
21 views

Best Case of Red Black Tree Insertion and Deletion

Question: During the insertion and deletion operation of a Red Black Tree data structure, each operation, can result in $\Omega(\log{n})$ color inversions? True or False? EDIT: Each operation ...
user avatar
0 votes
0 answers
50 views

Complexity of finding the kth smallest element of all the elements in two order statistics binary search trees

What is the time complexity of finding the kth smallest element of all the elements in two order statistics binary search trees? An order statistics tree is a binary search tree where the size of a ...
user avatar
2 votes
1 answer
70 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 ...
user avatar
  • 164
0 votes
1 answer
79 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 ...
user avatar
1 vote
2 answers
29 views

What is the time complexity of adding to a BST if we are to maintain balance

If we have a BST but want to keep it balanced, how much more expensive does adding an element to it become? Clearly adding an element (without maintaining balance) is of time complexity O(log(n)), as ...
user avatar
0 votes
0 answers
27 views

Red Black Tree: number of internal nodes vs leaf nodes

Given a generic Red Black Tree with n nodes is correct to say that the number of internal nodes is ⌊n/2⌋ and the number of leaf nodes is ⌊n/2⌋ + 1 ?
user avatar
  • 337
0 votes
1 answer
49 views

Depth-first search (DFS) time complexity for a Red-Black Tree

If we indicate n as the number of nodes of a Red-Black Tree, which is the time complexity of a DFS algorithm that analyzes only the internal nodes of the Tree? I think that the complexity is O(n), but ...
user avatar
  • 337
3 votes
1 answer
115 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 ...
user avatar
  • 187
3 votes
1 answer
91 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 $...
user avatar
0 votes
1 answer
46 views

BST subtree value range

Suppose we have a node x in BST, and let max and min be the largest and smallest keys in the subtree rooted at x respectively. Prove that for any node n outside this subtree, the key of n is either ...
user avatar
  • 9
4 votes
1 answer
361 views

Big O vs. Big Theta for AVL tree operations

On the Wikipedia page for AVL trees, the time/space complexity for common operations is stated both for average case (in Big Theta) and worst case (in Big O) scenarios. I understand both Big O and Big ...
user avatar
0 votes
1 answer
36 views

n search operations on an arbitrary Splay tree

For an arbitrary spay tree with n nodes, if we perform n find operations, is there a way of generalizing what the tree would ...
user avatar
1 vote
1 answer
38 views

Least-balanced possible red-black tree of n distinct nodes

Let's say we have a red-black tree of $n$ total nodes where all keys are distinct. The subtree rooted at the root node's left child has $n_L$ nodes, and similarly the subtree rooted at the root node'...
user avatar
0 votes
1 answer
14 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 ...
user avatar
0 votes
1 answer
48 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 ...
user avatar
0 votes
1 answer
71 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. ...
user avatar
0 votes
1 answer
117 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 ...
user avatar
0 votes
0 answers
22 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: ...
user avatar
  • 317
1 vote
3 answers
336 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 ...
user avatar
  • 151
0 votes
0 answers
11 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 ...
user avatar
  • 140
2 votes
1 answer
95 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 ...
user avatar
0 votes
0 answers
48 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 ...
user avatar
1 vote
3 answers
553 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 ...
user avatar
3 votes
1 answer
60 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 ...
user avatar
1 vote
1 answer
59 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 ...
user avatar
0 votes
1 answer
172 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 ...
user avatar
0 votes
1 answer
40 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 ...
user avatar
0 votes
0 answers
44 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 ...
user avatar
0 votes
1 answer
47 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$...
user avatar
1 vote
1 answer
147 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 ...
user avatar
  • 13
0 votes
0 answers
48 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 ...
user avatar
0 votes
0 answers
91 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 ...
user avatar
1 vote
1 answer
240 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 ...
user avatar
0 votes
1 answer
43 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 ...
user avatar
  • 13
1 vote
1 answer
56 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: ...
user avatar
  • 123
1 vote
1 answer
139 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 $...
user avatar
0 votes
0 answers
49 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 ...
user avatar
0 votes
1 answer
61 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)$ ...
user avatar
1 vote
1 answer
90 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: ...
user avatar
1 vote
1 answer
488 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, ...
user avatar
  • 113
1 vote
2 answers
452 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 ...
user avatar
  • 113
0 votes
1 answer
1k 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 ...
user avatar
  • 3
0 votes
0 answers
55 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). ...
user avatar
  • 151
2 votes
1 answer
772 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 <...
user avatar
  • 449
1 vote
1 answer
610 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 ...
user avatar
4 votes
0 answers
77 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 ...
user avatar
1 vote
2 answers
60 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 ...
user avatar