Questions tagged [binary-trees]

a rooted tree in which each node has no more than two children

Filter by
Sorted by
Tagged with
2
votes
0answers
705 views

Tight upper bound on height of a red-black tree

"Introduction to Algorithms" by Cormen et al., 3rd edition, Lemma 13.1 states that A red-black tree with $n$ internal nodes has height at most $2\log(n+1)$, i.e. $h \le 2\log(n+1)$. Can equality ...
0
votes
1answer
1k views

Is a BST considered a data structure or abstract data type

and why? It seem abstract in that it is and idea created and implemented with nodes arranged a certain way. But it did not show up in the text here: https://en.wikipedia.org/wiki/...
1
vote
2answers
342 views

Find height of deepest FULL level in binary tree

Suppose I have a binary tree that is guaranteed to have at least one level that holds the maximum amount of nodes possible. I want to find the height of the deepest level that is full/holds the ...
1
vote
1answer
135 views

Prove key of leaf is larger or smaller than key of parent if leaf is largest key in smaller tree or smallest in larger tree with respect to parent

Show that for any leaf v in a binary search tree, if u is the parent of v, then either key[v] is the largest key in the tree smaller than key[u], or key[v] is the smallest key in the tree larger than ...
6
votes
2answers
274 views

Find if a sequence of node is a result of a binary tree preorder traversal

Assume we have a sequence of 0's and 1's: $n_0, n_1, ..., n_N$, in which 0 stands for a leaf node, and 1 stands for an uncertain node (it may or may not be a leaf node). How to check if this sequence ...
2
votes
1answer
713 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 ...
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
103 views

Update and find-smallest-absolute-value operations on a tree

I have a balanced binary tree that stores a number in each node, initially zero. I want to build a data structure that will support the following two operations: Given a vertex $v$ in the tree and a ...
4
votes
4answers
6k views

How are binary trees represented on disk

Assume I have a word document, the contents in it are stored on the disk as bits. Nothing so complex here. When the word processor reads those bits, it just knows how to display on screen. But what ...
2
votes
2answers
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 ...
3
votes
2answers
481 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: ...
0
votes
1answer
179 views

The height of 5-balnced tree is O(logn)

Binary tree with external leaves is a 5-balanced tree if the path from the root to the farthest external leaf is no more than 5 times as long as the path from the root to the nearest external leaf, ...
0
votes
2answers
3k views

Algorithm to create tournament brackets

I'm designing a web app to host e-sports tournaments and want to create an algorithm that generates tournament brackets. Given a list of participants' user ID's (minimum 4, maximum let's say 64), I ...
3
votes
1answer
107 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)$ ...
1
vote
0answers
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 ...
4
votes
1answer
693 views

Check if a binary tree is a perfect tree

I'm trying to write an algorithm to check if a given binary tree is a perfect binary tree, and of course with the lowest complexity. I was thinking to calculate the height of the tree $h$ and the ...
6
votes
2answers
407 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 ...
2
votes
2answers
4k 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 ...
2
votes
0answers
141 views

Finding post-order traversal of a binary tree from its in-order and pre-order traversals lower bound

I know that we can construct a BST by just having its pre-order traversal in $O(n)$ time (this link). But what if the tree is just a binary tree and we have its in-order and pre-order traversals? I ...
3
votes
1answer
62 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 ...
2
votes
0answers
115 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 ...
0
votes
1answer
32 views

Info about dataset from which a Huffman tree was generated

I know that given the following huffman tree: you can say that C occurs most in the dataset from which it was generated and D and B occur the least. Can you also say that the left most leaf on a ...
2
votes
0answers
251 views

WAVL Trees - Number of rebalances

I was experimenting with a WAVL Tree code I wrote. One thing I noticed is that on average, there was much less rebalancing actions after delete than after insert. In fact, average rebalances after ...
1
vote
1answer
397 views

Number of Inner nodes in a B-Tree

the question goes as follows: In a B-tree (d,2d) of height h, what is the minimal and maximal number of inner-nodes (excluding leaves)? My idea: Minimal: The root is 1, it has a minimum of 2 ...
0
votes
0answers
33 views

Binary Search Tree: If two different traversals are given, will there be a unique tree that satisfies the traversals? [duplicate]

I have come across algorithms that can create a BST if any two of the 3 traversals are given (there would be three different algorithms for the 3 combinations) This is an example I was wondering, is ...
4
votes
2answers
2k views

Have I invented a new data structure?

EDIT: Seems like what this structure is nothing more than a 26-bit bitwise trie, as KWillets suggested in the comments! You can think of the words we insert the trie as 26-bit Bitsets where the i-th ...
0
votes
1answer
555 views

Forming red-black tree from binary tree conserving in-order traversal

What is the optimal algorithm (in terms of time complexity) that can transform any binary tree to a red-black tree, with the requirement that in-order traversal must yield the same values for the new ...
3
votes
1answer
546 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) ...
-1
votes
1answer
1k views

The number of nodes in a binary tree

If a binary tree is both a max-heap and an AVL tree, what is its largest possible number of nodes, assuming all keys are different?
0
votes
1answer
78 views

Build a tree for $(-\infty,+\infty)$ similar to dyadic interval trees for $\left[0,+\infty\right)$

Using dyadic intervals, I can build a binary tree for $\left[0,+\infty\right)$ by having a node the $i$-th at level $l$ representing the range $\left[i\cdot2^l,(i+1)\cdot2^l\right)$ and has the $(i)$- ...
0
votes
2answers
1k views

Is binary tree just a two-dimension-doubly-linked-list?

We all know the structure of a binary tree: struct binary_tree { binary_tree *parent; int data; binary_tree *left; binary_tree *right; }; So a ...
0
votes
1answer
85 views

Binary Tree Question

Using the diagram of a binary tree and algorithm answer the following: If the following commands store(1,laurence), store(1, ron), store(1,graham), store(1,abe) and store(1,martin) are executed what ...
9
votes
4answers
25k 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 ...
0
votes
0answers
36 views

Number of possible balanced binary trees [duplicate]

A tree is balanced if the subtrees of each node differ in height by at most one. How many balanced binary trees can we create from $n$ nodes?
0
votes
1answer
146 views

Where I can find example how prove red black tree?

I need prove that any red-black tree with at least two elements obtained through the insertion algorithm has at least one red node. For this, I need use Induction. I don't understand how apply ...
1
vote
1answer
130 views

A closed form expression for # of inputs of a binary tree and its number of nodes

Is there any closed from expression that can express the number of input pins of a binary tree based on height of the tree and its number of nodes? In case that the binary tree is a full tree, it is ...
0
votes
1answer
625 views

Strict-Binary Tree - Same Post-order & Pre-order sequences?

I'm going through some past exam papers for my course and I'm having trouble completing this one question. It is as follows: "Draw a strict binary tree with seven nodes that has the same pre-order ...
2
votes
1answer
964 views

Determine if the sequence of numbers is a post order traversal of a binary tree

The question is: given a sequence of numbers, find an algorithm that determines if the sequence of numbers is in post order traversal of a binary search trees. Up to now, I have understood the ...
-1
votes
1answer
441 views

Total depth of external nodes in complete binary tree

Assume a proper and complete binary tree $T$ with $n>1$ nodes. Let $E(T)$ represent the sum of the depths of all external nodes in $T$, and $I(T)$ represent the sum of the depths of all internal ...
3
votes
0answers
297 views

What is the intuition behind balancing in AVL trees?

I am not sure that my question is clear from the first sight. But I will try to explain what I mean. For now, I am learning balancing the trees on the example of AVL trees. We know that to balance ...
1
vote
1answer
411 views

Speculating big O for a binary tree

I have a binary tree with $n$ nodes. The tree is not necessarily balanced. For each node of the tree, I count down the total number of the nodes for its left sub-tree as $n_L$ and then I count down ...
2
votes
0answers
102 views

How to cut a full binary tree evenly

Given a full binary tree of size $n$, I need to cut the tree into two by choosing an edge and removing it. I want the cutting to be as equal as possible (i.e. the two subtrees have as equal weight as ...
2
votes
1answer
261 views

The Height of subtree in Heap

In order to find the recurrence function of The Height in Heap, the following figure is drawn. Question 1: How can we compute the height if Right subtree in form of Log in base 3, and why do we have ...
2
votes
0answers
19 views

How to avoid empty spots when inserting in a B+tree

When you insert a new item in a B+tree leaf node, and the node is full, two new nodes are created and they're both filled halfway and the values get re-distributed accordingly. Before the insertion: ...
2
votes
1answer
85 views

Number of n-node binary trees containing an m-node binary subtree

In a paper I see the following lemma about unlabeled binary trees: If $s_1$ and $s_2$ are both m-node binary trees, then the number of n-node binary trees containing $s_1$ as a subtree is the same ...
1
vote
1answer
374 views

Number of nodes of height $h$ in a heap or almost complete binary tree

I came up with the following statement: If there are $X$ nodes of height $h$ in an almost complete binary tree, there can be at most 1 node of height $h$ that is not full. That is to say, $X-1$ ...
1
vote
0answers
607 views

Using rotate to balance a red-black tree?

You have a Black-Red Tree of height h that has two childs: Left child is a full binary tree of height h-1 Right child ...
2
votes
2answers
64 views

Find initial ranks

Assume there is an array $A$ of $n$ elements. $A$ contains every number from $1$ to $n$. We are given an array $B$ of $n$ elements. If we move each element $A[i]$ left by $B[i]$ places starting from $...
1
vote
1answer
887 views

For AVL trees, how do we know if a RL or a LR rotation is needed?

Suppose I am trying to construct a simple AVL tree: Upon inserting 'B' the tree becomes imbalanced. How do I exactly know that I need a LR or RL rotation without making any guesses? From what I ...
0
votes
0answers
606 views

How to build a heap better than Incremental and In-place method using decision tree?

For an array A = [a1, a2, a3, a4] of distinct numbers, I have built heap using binary decision tree by Incremental and In-place method. Incremental method: In-place method: Is there a way to build ...

1
3 4
5
6 7
10