# Questions tagged [binary-search-trees]

The tag has no usage guidance.

167 questions
Filter by
Sorted by
Tagged with
1 vote
83 views

### Example of binary trees with maximum rotation distance

In the 1988 paper Rotation Distance, Triangulations, and Hyperbolic Geometry, Sleator, Tarjan and Thurston show that for any pair of $n$-node binary trees, the maximum rotation distance between them ...
629 views

### Binary search tree with height of max 1.44 * log(n) is AVL tree or it's not an iff

Assume I have a binary search tree, and I managed to prove that its height is upper bounded by $1.44 \log(n)$. Now, can I say with confidence that it is, for sure, an AVL tree? or is this condition ...
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 ...
114 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 ...
20 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 ...
25 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 ...
35 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, ...
85 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 ...
1 vote
2k 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, ...
124 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 ...
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 ...
1 vote
93 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 ...
57 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 ...
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 ...
1 vote
82 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 ...
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 ...
43 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 ...
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 ...
181 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 ...
81 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. ...
1 vote
91 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 ...
1 vote
121 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 ...
101 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, ...
26 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 ...
1 vote
273 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. ...
1 vote
261 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 ...
1 vote
84 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 ...
1 vote
172 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 ...
342 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 ...
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 ...
138 views

### Binary Tree Node Insertion

I was trying to implement a Binary Search Tree using this article as a reference: Binary Search Tree in JavaScript. I was thinking especially about the node insertion method. Here's my ...
205 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 ...
5k views

### If inorder traversal of a tree is in ascending order will the tree definitely be a BST?

For a binary search tree (BST) the inorder traversal is always in ascending order. Is the converse also true?
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 ...
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 ...
71 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 ...
564 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? ...
1 vote
353 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 ...
101 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 ...
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 ...
57 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 ?
172 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 ...