Questions tagged [binary-search-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
8
votes
3answers
15k views

What is “rank” in a binary search tree and how can it be useful?

I am having a bit of trouble wrapping my mind around what a ranked binary search tree is and why having a rank is important. I am hoping that someone can clarify a few things for me. What I have ...
6
votes
2answers
331 views

Balanced Binary Search Tree Two-Sum with Constraints

My question spawns from this question. The question is straightforward: Can we find whether there exist 2 values in a balanced binary search tree where their sum equals a given target value? Now ...
5
votes
2answers
1k 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?
5
votes
1answer
536 views

Data structure for handling intervals

I am trying to create a data structure for handling the subsets of the real line of the form $[x,y)$. That is, suppose $X \subseteq \mathbb{R}$ and the data structure supports two types of operations: ...
4
votes
4answers
2k views

Why use binary search trees when hash tables exist?

Hash tables perform lookup, insertion, and deletion in O(1) time (expected and amortized) while the different variants of binary search tree (BST) - treap, splay, AVL, red-black - offer at best O(log ...
4
votes
3answers
407 views

What purpose do the leaves in a range trees serve?

I'm getting into algorithms and I came upon range trees. What confuses me is the leaves in a range tree, since for example: When you remove the leaves: It's just a regular BST. And, every ...
3
votes
1answer
592 views

BST representation of Hash Tables

I'm reading this book Cracking Coding Interview. In this book author is speaking about BST representation of Hash Tables. I googled a lot for BST Representation of Hash Table. Code in C++ but didn't ...
3
votes
2answers
2k views

Which of the following sequences could not be the sequences of nodes examined in a binary search tree?

Suppose that we have numbers between $1$ and $1000$ in a binary search tree and want to search for the number $363$. Which of the following sequences could not be the sequences of nodes examined <...
3
votes
1answer
442 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 ...
3
votes
3answers
98 views

BST - Sufficient condition for connecting a node to a parent

Let's assume that we have a binary search tree with node Y that hasn't a right child and for whom a successor exists in the tree. I want to prove that if I insert a node X into the tree and node X is ...
2
votes
1answer
102 views

Height of epsilon-balanced binary search tree

In Balanced Binary Search Trees on the basis of size of left and right child subtrees, Hannes says: For example, one can say, a BST is balanced, if each subtree has at most epsilon * n nodes, ...
2
votes
1answer
32 views

in order of binary search tree

This is what I got for the in-order of the bst but it's wrong because I'm answering some questions about some successors of some of the letters and I got them wrong. so I'm wondering where in this in-...
2
votes
1answer
106 views

Proof that a subtree of a red-black tree has no more than $\frac{3n}{4}$ nodes

I have a red-black tree with $n$ nodes, rooted at $x$. How can I prove or disprove that the number of nodes in any subtree of $x$ (including the root of the subtree) will never be greater than $\frac{...
2
votes
1answer
209 views

How to find the number of Binary Search Trees with given number of nodes and leaves?

With 7 nodes of distinct values (unique), how many Binary search trees (BST) can be formed such that: Exactly $1$ leaf node(s) present? Exactly $2$ leaf nodes present? I was able to solve the first ...
2
votes
1answer
75 views

Efficient search algorithm for a monotonic boolean array wherein the probability of target's location is available apriori

A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$. $$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in ...
2
votes
1answer
1k views

Average height of a BST with n Nodes

I have to find the maximum, minimum, and average height of a BST with n nodes. After doing some researching I found that the maximum height is $n-1$ and the minimum height is $\log_2(n+1)-1$. My ...
2
votes
1answer
46 views

What is the average size of a jump in a binary tree?

Assume that a full binary tree is layed out in memory recursively in the following way. First the Root followed by Tree representation of left subtree followed by tree representation of right subtree. ...
2
votes
1answer
72 views

Randomized BST height analysis : How $Z_{n,i}$ and $Y_{k-1}$ are independent?

I am referring to this video https://www.youtube.com/watch?v=vgELyZ9LXX4 at 1:08:39 . $n$ : number of nodes in the tree $Z_{n,k}$ : Indicator random variable that activates when rank of the root ...
2
votes
1answer
456 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 ...
2
votes
1answer
1k views

What is the advantage of leaf trees vs. node trees?

In the book "Advanced Data Structures", Chapter 2 ("Search Trees"), the author, Peter Braß, mentions two versions of binary trees (emphases in the quoted text are mine): "...two different models ...
2
votes
0answers
35 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 ...
2
votes
0answers
203 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 ...
2
votes
0answers
111 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 ...
2
votes
0answers
44 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 ...
2
votes
3answers
633 views

Why is the number of comparisons in a BST missing key lookup about 2 ln N?

In (An Introduction to the Analysis of Algorithms) by Philippe Flajolet and Robert Sedgewick it's written that: Insertions and search misses in a BST built from N random keys require ~ 2 ln N (about 1....
1
vote
3answers
396 views

Why is Binary Heap never unbalanced?

My professor asks this question: Binary Search tree has Rotation Method to prevent it from degenerating into a linear structure (unbalanced tree). Why is there no need for such method for Binary Heaps?...
1
vote
2answers
39 views

Inorder tree tranversal on binary search tree doesn't give the elements in order?

I have been told that inorder tree tranversal of binary search trees returns the tree elements in order. I came up with this binary search tree: ...
1
vote
2answers
502 views

Why do we use multiple data structures? [duplicate]

I'm studying elementary data structures like Linked List, Doubly Linked List and Binary Trees like Binary Search Trees. Both runs in worst case O(n) in the same operations, so why don't we use only ...
1
vote
1answer
175 views

how does rotation works in AVL trees and what is a good way to understand it?

If we consider this tree with T1 and T2 as subtrees, and we want to rotate on x (rotating the edge between T1 and x), what is the result? how does it work then? Does the x stay in its place and T1 ...
1
vote
1answer
851 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 ...
1
vote
1answer
1k views

Number of binary search trees with maximum possible height for n nodes

I'm using the definition of the height of a tree as the longest possible path from the root to a leaf by its number of edges, e.g. a tree of 2 nodes has a height of 1. With that in mind, what would ...
1
vote
1answer
2k views

How many permutations for generating a specific binary search tree?

The keys 2, 4, 6, 7, and 8 have been inserted, one by one, in some unknown order, into an initially empty BST. The result is this BST: There are 120 different permutations of the five keys, but not ...
1
vote
1answer
2k 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
vote
1answer
33 views

question about the construction of BSTs using a repeated sequence of rotations

How can I show that any binary search tree can be balanced with at most O(n log n) rotations (“balanced” here means that the lengths of any two paths from root to leaf differ by at most 1).
1
vote
1answer
504 views

AVL Tree rotations : How to balance below AVL Tree with imbalance at root node

How to balance this AVL tree after inserting node 5, using left/right rotations as indicated in the AVL tree tutorial. I have tried applying both double rotations but with no luck. Either of the ...
1
vote
1answer
69 views

Searching in a Binary Search Tree

I'm studying Binary Search Trees (BST) and I would like to verify that my understanding of BSTs is correct. For example, let S = [17, -10, 7, 19, 21, 23, -13, 31, 59]. Binary Search Tree for S, with ...
1
vote
2answers
199 views

Deriving the average depth for a randomly generated binary search tree

If $D(n)$ is the internal path length (sum of the depths of all nodes) for some tree $T$ with $n$ nodes then we have the following recurrence relation: $$D(n)=D(i)+D(n-i-1)+N-1$$ where I simply taken ...
1
vote
1answer
35 views

Generate a unique number for a set of sequences of letters

A sequence of English letters are given, every sequence forms a word and we know that the size of each word is at most $15$ and the number of words is at most $50000$. For a given input word $w$ I ...
1
vote
1answer
410 views

Rooted Binary Tree - Chain Nodes Algorithm

The question is that I have to give a recursive algorithm in pseudocode, that counts the number of chain node in a rooted binary tree. Chain node is defined as a node that has only one child and that ...
1
vote
1answer
73 views

A data structure for holding numbers in 2 sets, using BST?

Design a data structure for holding numbers in two sets: Init - initiate the DS with two empty sets. O(1) Insert(a,S) - insert number ...
1
vote
1answer
1k 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
1
vote
1answer
330 views

Remove from black/red tree subtree with red root, red sibling and black parent in $O(\lg n)$

How can i remove from a red/black tree a subtree whose root and its sibling are red, and their parent is black, in $O(\lg n)$ time, while keeping the red/black properties at the end of the process? ...
1
vote
0answers
45 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 ...
1
vote
1answer
97 views

fixing a slightly broken BST tree

I'm stuck on this question, a BST is slightly broken only if there is a node with value x in which : there is at least one value less than x on its right branch or atleast one value greater than x on ...
1
vote
1answer
451 views

Binary Search Tree – Number of comparisons when element is not found

I am confused regarding Binary Search Trees (BST) when an element does not exist in the tree. For example, to search for element "6", would it take 5 comparisons to search for this element? My ...
1
vote
0answers
58 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 (...
1
vote
0answers
54 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 ...
1
vote
0answers
22 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: ...
1
vote
0answers
26 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 ...
1
vote
0answers
35 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)$ ...