Questions tagged [binary-trees]

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

97 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
0answers
613 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
0answers
150 views

Correctness of a greedy Algorithm on Knockout Tournaments

You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a ...
6
votes
2answers
250 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
222 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, ...
5
votes
0answers
290 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 ...
4
votes
0answers
75 views

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

In the following, I consider rooted, unlabelled, ordered binary trees, where each node has exactly $0$ or $2$ children (I will simply call them binary trees). A binary tree $t'$ is a subtree of a ...
4
votes
1answer
580 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
42 views

Node depth in randomly built binary search tree

It can be proved that randomly built binary search trees of size $n$ are of depth $O(\log n)$ and it is clear that level $k$ has at most $2^{k}$ nodes (root's level is 0). I have an algorithm that ...
3
votes
0answers
205 views

What's the number of leaves in AVL tree

How can I prove that the number of leaves in a balanced BST is $\Omega (N)$ where $N$ is the number of nodes in the tree? I tried somehow to prove that an AVL/Fibonacci tree should have $\Omega (N)$ ...
3
votes
0answers
37 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
146 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
275 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
535 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
828 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
24 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
39 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
302 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
91 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 ...
2
votes
0answers
141 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
569 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
138 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
113 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
250 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
91 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
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
634 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
612 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
258 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
41 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
224 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
18 views

Is there an Interval Tree which supports O(1) dynamic space requirements for queries?

I observed that all the interval tree implementations I am able to come up with are required to utilize a stack (or a-like) to answer queries (report any overlapping interval with a key). In general ...
1
vote
2answers
48 views

check if a binary tree is a binary search tree

I have some doubts about this algorithm which checks if a binary tree is a binary search tree: ...
1
vote
0answers
786 views

Find the median element of two AVL trees in $O(\log n)$

I'm attempting the problem of finding the median element in two AVL BST's in $O(\log n)$ time. In this problem, we are given two AVLs, with a combined size of $n$ (the distribution across the two ...
1
vote
0answers
21 views

Determining Range of Current Node in Segment Tree

I was attempting, though failing quite miserably, to find some method of of determining the range of some node $n$. By range I mean an interval $[l,r]$ over the base array that is reachable by the sub-...
1
vote
0answers
13 views

Confusion with “every path from a given node to any of the leaves goes through the same number of black nodes” property of RB trees

One of the properties of Red Black trees is: "every path from a given node/vertex to any of the leaves goes through the same number of black nodes" Two related questions about this property: 1) is ...
1
vote
0answers
30 views

relationship between binary numbers and binomial heaps

I understand that a binomial heap can be represented as binary numbers according to the degree of each tree but what exactly is the relationship between inserting a new node into the binomial heap and ...
1
vote
0answers
132 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
0answers
36 views

Finding a node in a binary tree by looking at the path between it and the root

There is a directed binary tree as shown in the picture (all edges are diercted from higher- to lower-level nodes). In that tree there is some specific unknown node $s$. All nodes in the $(s, root)$ ...
1
vote
0answers
30 views

Scapegoat Trees: Why are they only loosely a-height-balanced?

From Wikipedia: Even a degenerate tree (linked list) satisfies this condition if α=1, whereas an α=0.5 would only match almost complete binary trees. A binary search tree that is α-weight-...
1
vote
0answers
59 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
55 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
56 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
1answer
321 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
197 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
61 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
101 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
969 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 ...