Skip to main content

Questions tagged [binary-search-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-1 votes
1 answer
19 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 ...
Felix An's user avatar
  • 119
0 votes
0 answers
24 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 ...
Arham Zahid's user avatar
0 votes
0 answers
31 views

Closed-form for exact number of iterations of binary search

Consider a sorted list of $n$ elements $x_1, \ldots, x_n$. Using binary search to find $x_k$ in this list takes $f(n, k)$ iterations, where $f : \mathbb{N}^2 \to \mathbb{N}$ is a function such that, ...
Electro's user avatar
  • 103
0 votes
1 answer
83 views

Can this Binary Search Tree be optimal with $x$ expected comparisons?

I was given this Binary Search Tree. The question asks whether this tree can ever be optimal with $2.1$ expected comparisons, and I am completely lost on how to even approach this problem. Trying to ...
John36's user avatar
  • 1
2 votes
2 answers
107 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 ...
Rohit Pandey's user avatar
0 votes
2 answers
143 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 ...
user167064's user avatar
0 votes
1 answer
54 views

Time Complexity: Determining if a binary tree is balanced

I found an algorithm for determining if a binary tree is height-balanced. It Gets the height of left and right subtrees using dfs traversal. Return true if the difference between heights is not more ...
Ali Naseri's user avatar
1 vote
1 answer
72 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 ...
Mason Rashford's user avatar
0 votes
0 answers
25 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 ...
user166204's user avatar
0 votes
1 answer
40 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 ...
Some Name's user avatar
  • 105
0 votes
1 answer
44 views

Splay Trees - Sequential Access Theorem & lower bound for comparison-based sorting

The following theorem was proven by R.E. Tarjan in 1984: Theorem (Sequential Access Theorem). If we access each of the nodes of an arbitrary initial tree once, in symmetric order, the total time ...
Proper Illumination's user avatar
0 votes
0 answers
41 views

Can a Red Black Tree have a black node with a black descendant? Is this image wrong?

How the story begins? I was learning about Red Black Trees on my own. When one opens the Wikipedia article, it can be read: (Conclusion) If a node N has exactly one child, it must be a red child, ...
tac's user avatar
  • 101
5 votes
0 answers
80 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. ...
Mario Carneiro's user avatar
1 vote
1 answer
78 views

Merge K BST of N elements in total into a single RBT in O(N log K) time

I have the following question to solve; Given $K$ BST consisting of $N$ total elements, show how you can create a Red Black Tree in $O(N\log K)$ time. I had the following idea but it falls on the ...
Alon .G.'s user avatar
0 votes
0 answers
90 views

Deletion of a node from a BST

Placed exactly the code and the explanation of the book : Introduction to Algorithms Third Edition In order to move subtrees around within the binary search tree, we define a subroutine TRANSPLANT, ...
emacos's user avatar
  • 121
1 vote
2 answers
112 views

Merge two binary search trees

Consider two binary search trees T1 and T2, each with height h, with all values in T1 less than all values in T2. I want to merge these both trees to get a new binary search tree of height at most h+1 ...
nicku's user avatar
  • 143
2 votes
1 answer
168 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 ...
Avv's user avatar
  • 505
0 votes
0 answers
25 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 ...
MotiNK's user avatar
  • 553
0 votes
2 answers
1k views

Binary Search Tree Updating

How can I update values in Binary Search Tree without affecting its properties (all the nodes in the left subtree have values that are less than the value of the root node and all the nodes of the ...
Raghad's user avatar
  • 1
1 vote
1 answer
245 views

Two statements about optimal binary search trees

This is a paragraph from the book CLRS: What we need is known as an optimal binary search tree. Formally, we are given a sequence $K = (k_1, k_2, ..., k_n)$ of $n$ distinct keys in sorted order (so ...
Emad's user avatar
  • 411
1 vote
1 answer
82 views

What is the minimal number of nodes with the right subtree in a height-balanced BST?

I have a binary search tree of size $N$. The tree is height balanced: difference of heights of a node's subtrees is no more than 1 (true for RB or AVL trees). $K$ is the number of nodes that have a ...
Andrey Godyaev's user avatar
1 vote
1 answer
163 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 ...
Mike's user avatar
  • 33
2 votes
0 answers
311 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 ...
Eterm's user avatar
  • 129
0 votes
1 answer
138 views

Did I invent a new data structure?

I needed to implement a priority queue for a project I'm working on and had this idea. In a priority queue BST implementation wouldn't it be more efficient if the poll node pointed to its parent since ...
Abdulmalek Almkainzi's user avatar
0 votes
0 answers
203 views

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

Let a,b,c be arbitrary nodes in the subtrees $\alpha$, $\beta$, $\gamma$, respectively, in the left tree of Figure 13.2 (that is given below). How do the depths of a,b,c change when a left rotation is ...
Esha's user avatar
  • 109
0 votes
0 answers
31 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 ...
AyamGorengPedes's user avatar
0 votes
0 answers
70 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 ...
Neel Karia's user avatar
2 votes
1 answer
127 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 ...
Pwaol's user avatar
  • 164
0 votes
1 answer
90 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 ...
Uday Uppal's user avatar
2 votes
2 answers
1k 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 ...
Thornside's user avatar
0 votes
0 answers
56 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 ?
Bender's user avatar
  • 367
0 votes
1 answer
161 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 ...
Bender's user avatar
  • 367
3 votes
1 answer
188 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 ...
Rodrigo's user avatar
  • 189
3 votes
1 answer
303 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 $...
user3472's user avatar
  • 207
0 votes
1 answer
110 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 ...
r_d26's user avatar
  • 9
4 votes
1 answer
744 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 ...
573hgkaf's user avatar
0 votes
1 answer
52 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 ...
addu390's user avatar
1 vote
1 answer
130 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'...
Intrastellar Explorer's user avatar
0 votes
1 answer
33 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 ...
lyhokia's user avatar
0 votes
1 answer
101 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 ...
user126100's user avatar
1 vote
1 answer
267 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. ...
Vectorizer's user avatar
0 votes
1 answer
517 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 ...
Vectorizer's user avatar
0 votes
0 answers
26 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: ...
Sandeep's user avatar
  • 337
1 vote
3 answers
452 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 ...
ilam engl's user avatar
  • 151
2 votes
1 answer
135 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 ...
rtheunissen's user avatar
0 votes
0 answers
126 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 ...
Thomas Wang's user avatar
1 vote
3 answers
2k 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 ...
Divyanshu Shukla's user avatar
3 votes
1 answer
95 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 ...
user8171079's user avatar
1 vote
1 answer
102 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 ...
Kranthi Kiran's user avatar
0 votes
1 answer
630 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 ...
average_discrete_math_enjoyer's user avatar