Questions tagged [binary-search-trees]

The tag has no usage guidance.

46 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5 votes
0 answers
77 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
4 votes
0 answers
90 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 ...
Margaret Bloom's user avatar
3 votes
0 answers
52 views

If I randomly swap pairs of inputs how unbalanced will a binary search tree become?

Treesort sorts input by putting input into a binary search tree and then flattening the tree. In some cases the tree can become unbalanced and so a self-balancing tree is required. There is no ...
Molly Stewart-Gallus's user avatar
2 votes
0 answers
231 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
2 votes
0 answers
1k 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 ...
jpenna's user avatar
  • 121
2 votes
0 answers
67 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 ...
Netch's user avatar
  • 141
2 votes
0 answers
356 views

How many similar binary search trees are made from different permutations?

If I have numbers ranging from 1 to n, and I generate all the permutations of these numbers. Now, I create Binary search tree from these permutations. For a value n i want to know how many BSTs would ...
Rajeev Pandey's user avatar
2 votes
0 answers
120 views

What would be the probabilty of a randomly generated tree to be a Red-Black Tree

The question is not related to the homework I was working on a homework, and the specification was to generate a random tree with n elements(n being in the thousands for the assignment) and asked me ...
Daniel Rodríguez's user avatar
1 vote
0 answers
76 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
1 vote
0 answers
60 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....
D Wot's user avatar
  • 11
1 vote
0 answers
95 views

Upper bound on the average path length in binary search tree

I have been reading the chapter 6.2.2 in Knuth's book about lower and upper bound on the average path length in binary search tree. And I have problems with understanding small details of Theorem M (...
rbtrht's user avatar
  • 275
1 vote
0 answers
65 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 ...
roctothorpe's user avatar
  • 1,158
1 vote
0 answers
127 views

Splay Tree - Insert Permutation

Let $T$ be a Splay Tree. For a given permutation $\sigma$ on a set $S = \{1,2,3,...n \}$ we defined the following function: ...
Maaour's user avatar
  • 111
1 vote
0 answers
34 views

Looped binary sorting tree

I want to add a points one by one into sorting tree. I have less then function to order them by angle from absciss: for points $\mathbf p_i = (x_i,y_i)$ and $\mathbf p_j = (x_j,y_j)$ it just sign of ...
Tomilov Anatoliy's user avatar
1 vote
0 answers
36 views

Read nodes of a BST in blocks of size $k$ and traverse it in $\mathcal{O}(log_kn)$

This describes how one can neatly store a binary search tree as an array. I'm looking for a way to store a BST that will allow me to traverse any root to leaf path by loading $\mathcal{O}(log_kn)$ ...
PlsWork's user avatar
  • 427
1 vote
0 answers
1k views

Day-Stout-Warren algorithm for balancing BST. How does vine to tree work?

I was trying to understand the dsw algorithm for balancing a binary search tree in-place using this virgina tech page. The wikipedia page and vt page are more or less similar. I am having a hard time ...
Rpant's user avatar
  • 111
0 votes
0 answers
23 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
0 answers
38 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
0 votes
0 answers
71 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
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
  • 551
0 votes
0 answers
157 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
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
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
0 votes
0 answers
114 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
0 votes
1 answer
102 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 ...
user183748292's user avatar
0 votes
0 answers
89 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 ...
CforLinux 's user avatar
0 votes
0 answers
96 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 ...
CforLinux 's user avatar
0 votes
0 answers
97 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 ...
Miriam Nam's user avatar
0 votes
0 answers
104 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). ...
openspace's user avatar
  • 151
0 votes
0 answers
23 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? ...
Muhammad Arfeen's user avatar
0 votes
2 answers
831 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 ...
AleWolf's user avatar
  • 123
0 votes
0 answers
47 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 ...
Anon's user avatar
  • 103
0 votes
0 answers
67 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 ...
Red's user avatar
  • 15
0 votes
0 answers
348 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 ...
Robin Andrews's user avatar
0 votes
0 answers
61 views

AVL Tree Inner Nodes

If k is the height of an AVL Tree, the minimal number of inner nodes is: N(k) = N(k-1) + N(k-2) +1. Why is this formula true?
Kevin Wu's user avatar
  • 101
0 votes
0 answers
137 views

An AVL tree is a BST, but AVL tree can be not complete, then why do we define AVL tree a BST?

An AVL tree is a BST, and a BST is a complete tree, but AVL tree doesn't necessarily have to be complete. Thus, why do we define AVL tree a BST?
Hang Chen's user avatar
  • 335
0 votes
0 answers
512 views

How to find point of maximum overlap in both X and Y Axis?

I was given a array R of n rectangles [each element in the array is a bottom left point(x1,y1) and a top right point (x2,y2)] , parallel to the axis, and an array P of n points [each element is a ...
Jamaico's user avatar
0 votes
0 answers
151 views

IO efficiency of a complete binary search tree

I was given this as a homework exercise, yet I don't know whether my solution is sound: Given a complete binary search tree where blocks are formed in order of the value of the nodes. What would ...
b9s's user avatar
  • 183
0 votes
0 answers
70 views

Find keys between $x$ and $y$ in binary search tree

Given $x$ and $y$, I want to find keys $k$ such that $x<k<y$, in a binary search tree. Can this be done in time $O(n + h)$, where $n$ is the number of keys between $x$ and $y$, and $h$ is the ...
mohammad_1m2's user avatar
0 votes
1 answer
1k views

Time complexity of creating the unique binary tree from given inorder and preorder (or postorder) traversal sequences

Given inorder and preorder (or postorder) traversal sequences of a binary tree balanced binary tree binary search tree of n nodes, what is the time complexity of creating the respective unique tree.
vishalgoel's user avatar
-1 votes
2 answers
39 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
Holz's user avatar
  • 1
-1 votes
1 answer
274 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)?
Sai Teja's user avatar
-1 votes
1 answer
687 views

Binary search trees: multiple `Successor()` calls

Show that, given a tree node a, the time complexity of calling k times to Successor() is $O(k+h)$, where $h$ is the tree height. ...
galah92's user avatar
  • 327
-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 ...
Pravesh's user avatar