Questions tagged [binary-trees]
a rooted tree in which each node has no more than two children
554
questions
3
votes
1
answer
541
views
Size of the universe for van Emde Boas Trees
In order to achieve the time complexity of $O(\log \log u)$ for van Emde Boas trees I read in this lecture that the the universe size $u$ is chosen as $u = 2^{2^k}$ for some integer $k$ for van Emde ...
- 1,191
3
votes
3
answers
26k
views
Average number of comparisons to locate item in BST
This is a GRE practice question.
If a node in the binary search tree above is to be located by binary tree search, what is the expected number of comparisons required to locate one of the items (...
- 233
3
votes
1
answer
852
views
Efficient data structure for insertion, deletion and smallest-not-in-range query on an array of integers
I'm trying to make a data structure $A$ that has the following features:
insert($a$) operation : insert given integer $a$ to $A$. It is assured that all integers are unique.
delete($b$) operation : ...
user149684
3
votes
2
answers
64
views
When should we construct trees, graphs to analyse an algorithm?
In many algorithms, it's easy to understand how the algorithm is executed, but as for why it works well and how it can work, it's not very easy to see, sometimes, authors construct trees or graphs to ...
- 145
3
votes
2
answers
856
views
Relationship between height and depth of a binary tree
The wikipedia says that the number of nodes n in a full binary tree, is at least $n=2^h-1$ and at most $n=2^{h+1}-1$, where h is the height of the tree.
The following binary tree is full according to ...
- 131
3
votes
1
answer
11k
views
Is a balanced binary tree a complete binary tree?
Considering that the opposite is true it's not mentioned anything about this. I am assuming its not, but I need a very good distinction between these two types of binary trees.
All I know is this:
...
- 156
3
votes
2
answers
4k
views
AVL Trees Height-Balance Property
An AVL tree is one that satisfies the height-balance property which states that: For every position p of T, the heights of the children of p differ by at most 1.
Below is an example AVL tree. However,...
- 133
3
votes
1
answer
8k
views
What is the size of the Perfect binary tree with n nodes in last level
I want to know how to calculate total number of nodes in a perfect balanced binary tree with $n$ nodes in the last level. I know the answer is $2\cdot 2^{\log n} - 1$. Just curious how this can be ...
- 123
3
votes
1
answer
413
views
Maintaining search indices with binary trees
There are some documents to be indexed, that means I need to read the docs and extract the words and index them by storing at which document they appear and at which position.
For each word initially ...
- 131
3
votes
1
answer
290
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 $...
- 207
3
votes
1
answer
294
views
Dynamic data structure that checks all prefix sums of a subsequence are >= 0 and sum is = 0
Lets consider sequences whose elements are $-1,0,1$.
Subsequence $A[i...j]$ is $good$ if sum of its elements $=0$.
Example: for sequence $1,1,0,-1,-1,1$ subsequence $1,0,-1,-1,1$ is $good$.
...
- 207
3
votes
1
answer
3k
views
Which Tree traversal String is unique?
Assume we have a tree and we want to serialize it.
Example:
...
- 143
3
votes
2
answers
4k
views
AVL tree worst case height proof
The worst case height of AVL tree is $1.44 \log n$. How do we prove that?
I read somewhere about Fibonacci quicks but did not understand it.
- 394
3
votes
1
answer
2k
views
Difficulty in updating the balance factor of nodes in AVL tree
In this figure x,y,z are the nodes on which rotation is performed and T1, T2, T3, T4 are the subtrees.
I have understood how the rotation is working and have no trouble with that. The problem I am ...
- 33
3
votes
2
answers
617
views
Heights series in the DFS traversal of a binary tree
Assume a binary tree of height N. All nodes have exactly 2 children and all leaves have height N. For example, the following tree has N=3:
...
- 31
3
votes
2
answers
6k
views
How exactly Hashing performs better than a Binary Search?
The time complexity of a Binary Search is O(log n) and Hashing is O(1) - so I've read. I have also read that Hashing outperforms Binary search when input is large, for example in millions. But I see ...
- 183
3
votes
2
answers
2k
views
General method behind converting recursive inorder, preorder and postorder traversals of a binary tree to a non-recursive one?
I am reading both recursive and non-recursive using stack methods to implement inorder, preorder and postorder traversal of a binary tree at https://en.wikipedia.org/wiki/Tree_traversal#Depth-...
- 4,895
3
votes
2
answers
4k
views
Does the rebalancing propagate upwards only to update the height of the nodes in an AVL tree?
I was studying AVL trees and was wondering if the only reason one propagates upwards to the node in an insert is to change the height. It seems to me that rebalancing does not recursively propagate ...
- 3,040
3
votes
1
answer
812
views
Running time analysis of a segment tree
Can someone provide an analysis of the update and query operations of a segment tree?
I thought of a way which goes like this - At every node, we make at most two recursive calls on the left and ...
- 243
3
votes
1
answer
4k
views
Smallest(k) in red-black tree. How is it O(logn)?
Is it the same as find minimum for a binary search tree?
I know recoloring runs in O(logn) and rotations are O(1).
Even if we are wanting it to find the 'k-th' smallest key in the red-black tree.
...
- 101
3
votes
2
answers
2k
views
Finding no. of leaf nodes for each node in a BST
A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is
$\qquad \min(\#\text{...
- 1,463
3
votes
1
answer
913
views
Height of a full binary tree
A full binary tree seems to be a binary tree in which every node is either a leaf or has 2 children.
I have been trying to prove that its height is O(logn) unsuccessfully.
Here is my work so far:
I ...
- 33
3
votes
1
answer
115
views
Does 'reverse' mean 2 separate things in contexts of tree vs. graph traversal?
I'm somewhat confused about the Wikipedia terms about the meaning of 'reversed' in the context of tree & graph treversals
Suppose I have a tree:
...
- 145
3
votes
1
answer
90
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 ...
- 133
3
votes
1
answer
6k
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 ...
- 43
3
votes
1
answer
2k
views
$O(n\log n)$- algorithm for finding tree root
All numbers from $1$ to $n = 2^k-1$ are written in unknown way in a full binary tree of height $k$. We say that a number $t$ lies between $i$ and $j$ if after removing $t$ from the tree we obtain ...
3
votes
1
answer
1k
views
What is the main difference between binary decision tree and binary decision diagram(BDD)?
What is the main difference between binary decision tree and binary decision diagram(BDD)? From what I can tell I only understand that a binary decision diagram is a more compact representation ...
- 431
3
votes
1
answer
168
views
Is there a name for this traversal-optimized representation of a binary tree data structure?
I have used a purely functional binary tree structure in which there is a single node that is "marked". It allows for $O(1)$ access and modification of the marked node's value, as well as $O(1)$ ...
3
votes
1
answer
102
views
Prove $T$ is a BST iff for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child of $x$
Let $T$ be a complete binary tree. Prove that $T$ is a binary search tree if and only if for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child ...
- 527
3
votes
1
answer
520
views
Minimum number of rotations of a binary tree to convert it into another
I have the following binary tree, which I'm trying to convert into the target binary tree (second tree in the post) using minimum number of tree rotations. The theoretical minimum number of rotations ...
- 155
3
votes
1
answer
608
views
I/O cost to traverse a tree stored in preorder form
Let T be a binary tree that is stored in the disk following the preorder layout.
For example if this is $T$:
then $T$ will be stored in the disk as follows:
<...
- 629
3
votes
2
answers
2k
views
Can the height of a binary search tree be less than that of a red-black tree?
This is a question from the book Algorithms by Robert Sedgewick and Kevin Wayne.
"Find a sequence of keys to insert into a BST and into a red-black BST such that the height of the BST is less than ...
- 31
3
votes
1
answer
5k
views
How do binary trees use memory to store its data?
So I know that arrays use a block on contiguous memory addresses to store data to memory, and lists (not linked lists) make use of static arrays and when data is appended to the list, if there is no ...
- 131
3
votes
1
answer
1k
views
Algorithm to determine two binary expression trees will give the same result based on associative and commutative properties of some operators
Given n different numbers, I would like to find out whether there exists an algebraic expression using all the n numbers, with n−1 binary operators and unlimited number of parentheses, that ...
- 173
3
votes
2
answers
2k
views
Dynamic programming to find the least possible balance of a full binary tree
I am given $n$ positive integers $x_1,x_2,\cdots,x_n$ as input. These are the weights of the leaves in a full binary tree, $x_1$ being the leftmost leaf and $x_n$ the rightmost leaf. The weight of an ...
- 61
3
votes
1
answer
8k
views
Updating an AVL Tree Based On Balance Factors
I'm looking at the lecture review for one of my computer science classes and I'm having trouble coming up with an answer. Could someone help me work through it?
Background:
Let the balance factor ...
- 179
3
votes
3
answers
10k
views
Why does the formula floor((i-1)/2) find the parent node in a binary heap?
I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the index of the parent of element at index i can be found with
parent ...
- 49
3
votes
1
answer
743
views
Keeping a binary search tree by splitting nodes (like a B-Tree)
A B-tree is kept balanced (i.e. all leaves at same depth) by splitting a node when adding a child that won't fit, and propagating this splitting up to the root.
Can the same technique be used to keep ...
- 31
3
votes
1
answer
634
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 ...
- 1,743
3
votes
1
answer
384
views
Why do you reason about the minimum number of nodes of an AVL tree of height h to argue the height is $\log n$ of an AVL tree?
Recall the standard argument for showing an AVL free is of size $\log n$:
Let $n_h = $ be the minimum number of nodes of an AVL tree of height
$h$. Then we have:
$$ n_{h} \geq 1 + n_{h-1} + ...
- 3,040
3
votes
1
answer
2k
views
Maximal number of rotations after deleting a node in an AVL tree
What is the maximal number $c$ of single rotations after deleting a node from an AVL tree? We treat double rotations as two single ones.
I know that it is $O(\log n)$ but I'm trying to find a more ...
- 573
3
votes
1
answer
100
views
Finding the number of $L\leq j\leq R$ such that $a[j] \leq a[i]$
I have recently encountered the following problem which I heard can be solved by using BIT (binary indexed trees) but I am not sure how:
Given an array $a[1, 2, \ldots, n]$ and $Q$ queries of the ...
- 31
3
votes
1
answer
485
views
Unique keys in a binary search tree
I'm studying for my finals and I can across this statement.
"For a fixed set of (unique) keys, any binary search tree containing those keys can
be converted to any other BST on the same set of keys ...
- 339
3
votes
1
answer
112
views
Changing AVL's balance factor to some other $s>2 \in \mathbb{N}$
Given we change the rule to:
$-s \ \ \leq$ height(left-subtree) - height(right-subtree) $\leq \ \ s$
I was wandering whether it's possible and how would it affect the trees' height, would it ...
- 157
3
votes
1
answer
112
views
Are all data structures in the von Neumann architecture based on the array, or array-like?
I am an old Pythonista now learning C and how various data structures and types are implemented, such as binary trees and hash tables. Learning about the latter, leads me understand that the hash ...
- 131
3
votes
1
answer
223
views
Distinct Binary Heaps
I have $n$ elements out of $n-1$ are distinct. The repeated element is either minimum or maximum element. I need to figure out how many distinct max heaps can be made from it.
My analysis : I started ...
- 93
3
votes
1
answer
80
views
Finding $k$-th element in prefix of size $i$
Let's say we are given array $A$ of size $n$. We need to answer some numbers of queries. For each query we are given index $i$ and integer value $k$, $k \le i$. If we take the first $i$ elements of ...
- 1,428
3
votes
2
answers
2k
views
What are drawbacks of Tree Sort algorithm (with balanced tree) vs Tree Sort (with unbalanced tree)?
Tree Sort algorithm with unbalanced tree may yield $O(n^2)$ worst-case time complexity/performance. But Tree Sort algorithm with balanced tree guarantees $O(n\log n)$ worst-case time performance.
So ...
- 173
3
votes
1
answer
676
views
Link-cut trees: using access() and link()
I am having some trouble on understanding link-cut trees, so I need some help.
Suppose that we have nodes $A, B, C, D$ and we want to do the following operations:
Link(A,B)
Link(B,C)
Link(C,D)
...
- 133
3
votes
1
answer
1k
views
Binary tree To Red-Black tree
I have a question regarding the solution provided by Karolis Juodelė.
Given in this question; Colour a binary tree to be a red-black tree
Black = black nodes, white = red nodes
So for this tree when ...
- 31