We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [binary-trees]

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

72 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
0answers
609 views

Chained operations on sequences with two operators

Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation? Can we learn from matrix chain multiplication? A generalization of matrix chain ...
6
votes
2answers
214 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 ...
5
votes
0answers
192 views

Average redundancy in Huffman or Hu-Tucker codes on random symbol probabilities

Huffman and Hu-Tucker codes are well-known compression schemes, which both come close to the entropy lower bound. It is known that if $L_1$ and $L_2$ are the lengths of a Huffman resp. Hu-Tucker code, ...
4
votes
0answers
265 views

Efficient deletion in Fenwick tree

Suppose there is an array of nonzero integer values A[n], which has a Fenwick tree representation F[n]. The most simplistic way ...
3
votes
0answers
31 views

Proving an upper-bound on the cost of all calls to rebuild() during a sequence of m operations in a scapegoat tree

I'm reading through Open Data Structures by Pat Morin and am currently looking at scapegoat trees. The book is free and can be downloaded from here: http://opendatastructures.org/ods-java.pdf On page ...
3
votes
0answers
142 views

Total number of red black tree arrangements

Consider a list of n integers. And assume we take each integer from this list sequentially and add it to a red-black tree. Then for the n! permutations of the list how many red-black tree ...
3
votes
0answers
252 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 ...
3
votes
0answers
534 views

Optimal Binary Search Trees Knuth

Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica 1 (1): 14–25,doi:10.1007/BF00264289 Please have a look at this paper, specifically page 18 in which he tries to prove his ...
3
votes
0answers
513 views

Range bit inversions and range set bit queries with a binary indexed tree

I am trying to solve this problem using a binary indexed tree. The problem can be summarized as follows: You are given a series of commands that operate on an array initially all zeroes. 1) ...
3
votes
1answer
682 views

what is the name for the space between the leaves of a tree

I am trying to write a data-type not for a tree, but for the spaces in between the leaves of thee tree. In number theory (a part of math) this is known as a topograph does it have a name in CS?
2
votes
0answers
18 views

Nested dissection vs kd-tree

Could you explain, please, the difference between the nested dissection and kd-tree. For me they look same representing a tree data structure for a distribution of points in a multi-dimensional ...
2
votes
0answers
35 views

Documentation of “bin number” trees

TL;DR: I implemented a special (?) binary tree and can't find any further details on the method I used on the internet. I would like to know if there are any scientific papers discussing my ...
2
votes
0answers
197 views

Analysis expected depth of a binary search tree given random values?

I have a guess about the problem above. Suppose I have a binary search tree $T$ initially empty. Suppose I drawn $x_1,\ldots,x_k$ (from some real interval $[a,b]$) keys and I want to insert the keys ...
2
votes
0answers
123 views

Algorithm to find nodes with given a distance

We have a map of a branching river without any islands (tree of confluences, see picture), there are piers on the river bank ( not necessarily on the confluences). We are given the distances between ...
2
votes
0answers
412 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 ...
2
votes
0answers
130 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 ...
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
247 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 ...
2
votes
0answers
78 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
0answers
18 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
577 views

How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
2
votes
0answers
565 views

Red black tree - Insert/Delete proof of correctness

From the Cormen book I was studying the chapter focused on the red black tree. I was particularly interested in why the procedures for insert/delete fixup works (namely a formal proof). I report both ...
2
votes
0answers
83 views

Can the right childs of a node in an AVL tree be both balanced after an insert and need rebalancing?

I was trying to come up with a case where one would need rebalance the following case in an AVL tree: I think that case impossible to happen during an insert. It seems to me that its impossible to ...
2
votes
0answers
54 views

Two flavors of red-black trees with different performance

I've implemented two red-black trees (using the pseudo-code in CLRS) with slightly different flavors: 1) In the first tree, all the data is stored in the leaves. 2) In the second tree, the data is ...
2
votes
0answers
237 views

Marking nodes of a complete binary tree

Suppose that I have a binary tree with $N = 2^h - 1$ nodes, initially all nodes are unmarked Over time via this process nodes became marked. Suppose that nodes have unique identifiers in range of $[1,...
2
votes
0answers
40 views

How to find number of occurences of specific distances in binary (search) trees?

I want to calculate the amount of tree structures that have a given maximal distance between two nodes given an amount n of nodes (or keys). E.g. with ...
2
votes
0answers
219 views

Difference between fully-reduced BDD and quasi-reduced BDD

I am trying to figure out difference between fully- and quasi-reduced BDDs. I have read a lot of material but still it is not very clear. As I am trying to figure out the quasi reduced version for ...
1
vote
1answer
374 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.
1
vote
0answers
57 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
42 views

Building segment tree to find minimum suffix sum in range

Let's say we have array $A$ of $N$ integers, each of them in the range $[-1, 1]$. We define an array $B$ of $N+1$ integers, such that $$B_{N+1} = 0, \\B_i = A_i + A_{i+1} + A_{i+2} + \dots + A_{N}= ...
1
vote
0answers
75 views

Splay trees: why are depths of nodes on the access path halved?

The original paper describing splay trees Self-Adjusting Binary Search Trees by Sleator and Tarjan claims that: Splaying not only moves x to the root, but roughly halves the depth of every node ...
1
vote
1answer
168 views

Understanding B tree key deletion step from CLRS algorithm

CLRS explains B tree key deletion as follows: If the key $k$ is in node $x$ and $x$ is a leaf, delete the key $k$ from $x$. If the key $k$ is in node $x$ and $x$ is an internal node, do the ...
1
vote
0answers
145 views

Proof of Fenwick Tree's correctness

Unfortunately (like many other authors) Fenwick does a very bad job of explaining his work (the Binary Indexed Tree) in the original text. The paper lacks a proper formal proof of why this structure ...
1
vote
0answers
38 views

Number of binary trees of size $n$ such that all subtrees of same size are equal?

For a binary tree $t$, let the size $|t|$ be the number of leaves of $t$. I am interested in the following property of a binary tree $t$: If two subtrees $t'$ and $t''$ of $t$ have the same size, i.e. ...
1
vote
0answers
54 views

How to assign the increasing keys to the nodes of a complete binary tree on n nodes in inorder?

I'm looking at the Multiplicative Binary Search and come across this. It's the preparation you need to do for you to use the Multiplicative binary search procedure. I somehow do not know how to do ...
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
89 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 ...
1
vote
0answers
743 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 ...
1
vote
0answers
439 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 ...
1
vote
0answers
149 views

How to encode each possible b-tree of a sequence of n numbers?

Lehmer codes can be used to encode each possible permutation of a sequence of n numbers. Often the main goal is just to map a range of numbers from 1 to x to the possible permutations of a sequence of ...
1
vote
0answers
244 views

Binary Indexed Tree(Fenwick Tree) - Range update and point Query

With the help of TopCoder Tutorial and this post, I was able to understand the basic idea of how basic the cumulative frequency sum is stored in the left subtree of a BIT node.I was successfully able ...
1
vote
0answers
2k views

Merging two binary heaps in linear time

Given two binary heaps, each represented by a binary tree with 2k-1 elements, design an algorithm to merge the two heaps into one heap in linear time. I've been having some difficulty in solving ...
1
vote
0answers
114 views

Minimize the depth of a tree of computation

Assume you have a binary tree of additions, where each two nodes are added together until the root is the sum of all the nodes. For example: ...
1
vote
1answer
1k views

Red Black Tree deletion algorithm (CLRS, 3rd edition) : Deleting the root

I have been following the third edition of Introduction to Algorithms (by Cormen, Rivest et al), and have been studying the deletion algorithm for red black trees. However, I am confounded at the ...
1
vote
0answers
198 views

Ranking in complete binary trees

I have a binary tree, the node has two subtrees, every node except the the leaves, has 2 children and all the leaves are at the same level. I want to know the worst and best case complexities when I ...
1
vote
0answers
155 views

LLRB Tree How to prove if left and left of left node are black, then this node must be a red node?

Im learning the delete operation on Left-leaning Red Black Tree invented by Prof. Sedgewick. In delete operation, a node could be only deleted from a 3-node or a 4-node but 2-node. In order to ensure ...
1
vote
0answers
75 views

Inversion of BDD

How can I write an algorithm which inverts a 2-level BDD? It should take as input a 2L-level quasi-reduced BDD rooted at $r$ encoding a relation $R : B^L → 2^{B^L}$ and returns the 2L-level quasi-...
1
vote
0answers
90 views

Proving that a BST with N>=1 nodes will have log(N+1) levels

I am trying to prove by induction the following theorem: Use Induction to prove the following fact: for every integer, $N\ge 1$ , a BST with $N$ nodes must have at least $\log( N + 1)$ levels. I've ...
0
votes
0answers
6 views

Performing crossover on trees in genetic algorithm

I'm using genetic algorithm for solving a problem. Each chromosome is a B* tree (where each node has only 2 child nodes). I'm wondering how to perform the crossover. I found an example which says ...