Questions tagged [binary-search-trees]

The tag has no usage guidance.

29 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
1answer
527 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: ...
2
votes
0answers
34 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
196 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
608 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
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
53 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)$ ...
1
vote
0answers
785 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 ...
0
votes
1answer
26 views

How to construct a perfect BST from an unbalanced BST with n elements (assuming that n=(2^i)-1, i is natural)

How do I construct a perfect BST from an unbalanced BST with $n$ elements (assuming that $n=2^i-1$, $i$ is natural). ** At the worst case of $O(n)$**.
0
votes
1answer
82 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 ...
0
votes
0answers
25 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 ...
0
votes
0answers
25 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 ...
0
votes
0answers
107 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 ...
0
votes
1answer
86 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 ...
0
votes
0answers
110 views

Time complexity proof of finding the $i$ object in binary search tree is $O(h+i)$ by inorder

I'm looking for time complexity proof of finding the $i$ object in binary search tree is $O(h+i)$ by inorder run. when $h$ is the height of the tree.
0
votes
0answers
41 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?
0
votes
0answers
119 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?
0
votes
0answers
424 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 ...
0
votes
0answers
118 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 ...
0
votes
0answers
66 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 ...
0
votes
1answer
563 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.
-1
votes
2answers
32 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
-1
votes
1answer
122 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)?
-1
votes
1answer
508 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. ...
-3
votes
1answer
4k 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 ...