192
Intuitively, you can think of a binary indexed tree as a compressed representation of a binary tree that is itself an optimization of a standard array representation. This answer goes into one possible derivation.
Let's suppose, for example, that you want to store cumulative frequencies for a total of 7 different elements. You could start off by writing ...
78
Heap just guarantees that elements on higher levels are greater (for max-heap) or smaller (for min-heap) than elements on lower levels, whereas BST guarantees order (from "left" to "right"). If you want sorted elements, go with BST.by Dante is not a geek
Heap is better at findMin/findMax (O(1)), while BST is good at all finds (O(logN)). Insert is O(logN)...
39
Summary
Type BST (*) Heap
Insert average log(n) 1
Insert worst log(n) log(n) or n (***)
Find any worst log(n) n
Find max worst 1 (**) 1
Create worst n log(n) n
Delete worst log(n) log(n)
All average times on this table are the same as their worst times except for Insert.
*: everywhere in ...
36
Both binary search trees and binary heaps are tree-based data structures.
Heaps require the nodes to have a priority over their children. In a max heap, each node's children must be less than itself. This is the opposite for a min heap:
Binary search trees (BST) follow a specific ordering (pre-order, in-order, post-order) among sibling nodes. The tree must ...
28
Tree Examples (image):
A: B:
‾‾ ‾‾
1 1
/ / \
2 2 3
/
3
This is an example that fits your scenario, Tree A root׳s value is 1, having a left child with value 2, and his left child has also a left child with value 3.
Tree B root׳s value is 1, ...
23
Let's first think about this intuitively. In the best-case scenario, the tree is perfectly balanced; in the worst-case scenario, the tree is entirely unbalanced:
Starting from the root node $p$, this left tree has twice as many nodes at each succeeding depth, such that the tree has $n=\sum_{i=0}^{h}2^i =2^{h+1}-1$ nodes and a height $h$ (which is in this ...
19
I'm assuming that by $n$, you mean the total number of nodes in the binary tree. The height (or depth) of a binary tree is the length of the path from the root node (the node without parents) to the deepest leaf node. To make this height minimum, the tree most be fully saturated (except for the last tier) i.e. if a specific tier has nodes with children, then ...
19
A Fenwick tree is a binary tree used to efficiently handle cumulative frequencies or sums in an array.
Without loss of generality we shall examine a 16-element array. Imagine a binary tree imposed on top of the array. Furthermore, label all the left edges in this tree with a "0" and all the right edges with a "1". We get something like this:
This is the so ...
18
There is nothing to be done: for instance, let $S_k$ denote the star graph with $k$ leaves. The graph $S_k$ has a unique spanning tree (which is $S_k$ itself), and it has a vertex with degree exactly $k$.
In fact, the general problem of finding a degree-constrained minimum spanning tree is NP-complete.
17
If looking for the key 60 we reach a number $K$ less than 60, we go right (where the larger numbers are) and we never meet numbers less than $K$. That argument can be repeated, so the numbers 10, 20, 40, 50 must occur along the search in that order.
Similarly, if looking for the key 60 we reach a number $K$ larger than 60, we go leftt (where the smaller ...
14
Hash tables can only tell you if an element is present or not.
Here are somethings you can do with a binary tree that you can't do wiht a hash table.
sorted traversal of the tree
find the next closest element
find all elements less than or greater than a certain value
See this wikipedia article on K-d trees for an example of a real world data structure ...
13
With data structure one has to distinguish levels of concern.
The abstract data structures (objects stored, their operations) in this question are different. One implements a priority queue, the other a set. A priority queue is not interested in finding an arbitrary element, only the one with largest priority.
The concrete implementation of the structures. ...
12
If for each node of a tree, the longest path from it to a leaf node is no more than twice longer than the shortest one, the tree has a red-black coloring.
Here's an algorithm to figure out the color of any node n
if n is root,
n.color = black
n.black-quota = height n / 2, rounded up.
else if n.parent is red,
n.color = black
n.black-quota = ...
12
Here's a simpler logical proof.
Last leaf is $n^{th}$ index. Its parent is at index $\lfloor{n/2}\rfloor$ and similarly, there is no element such that its parent is ($\lfloor n/2 +1\rfloor)^{th}$ element. Thus leaves are indexed from $\lfloor{n/2}\rfloor$ +1 to n.
Hence, total number of leaves = n- $\lfloor(n/2)\rfloor$ = $\lceil(n/2)\rceil$.
12
According to this book (Chapter 3.2), a node in a BST has rank $k$ if precisely $k$ other keys in the BST are smaller. So, if you order all the BST nodes according to their keys, then each node with rank $k$ will take $k$-th place.
11
A binary tree has 1 or 2 children at non-leaf nodes and 0 nodes at leaf nodes. Let there be $n$ nodes in a tree and we have to arrange them in such a way that they still form a valid binary tree.
Without proving, I am stating that to maximize the height, given nodes should be arranged linearly, i.e. each non-leaf node should have only one child:
...
11
One application domain where binary trees are better, or more easily adjustable than certain alternatives, are persistent data structures (which are often used in (purely) functional programming).
A persistent data structure is a data structure that preserves the previous version of itself when it is modified. (Data structures that do not have this property ...
11
The depth of a decision tree is the length of the longest path from a root to a leaf.
The size of a decision tree is the number of nodes in the tree.
Note that if each node of the decision tree makes a binary decision, the size can be as large as $2^{d+1}-1$, where $d$ is the depth. If some nodes have more than 2 children (e.g., they make a ternary ...
10
I think that the original paper by Fenwick is much clearer.
The answer above by @templatetypedef requires some "very cool observations" about the indexing of a perfect binary tree, which are confusing and magical to me.
Fenwick simply said that the responsibility range of every node in the interrogation tree would be according to its last set bit:
E.g. as ...
9
I actually touched upon this in response to your previous question, but the general idea is that there are $n$ nodes in a binary tree, and starting from the root, at each depth there is: 1, 2, 4, 8, 16 ... maximum nodes. We see that at the greatest depth, there is (at most) half of all nodes ($n/2$). Remember that the height of a node is the distance from ...
9
Suppose you had an empty array:
0 0 0 0 0 0 0 0 0 0 (array)
0 0 0 0 0 0 0 0 0 0 (cumulative sums)
And you wanted to make a range update of +5 to [3..7]:
0 0 0 5 5 5 5 5 0 0 (array)
0 0 0 5 10 15 20 25 25 25 (desired cumulative sums)
How could you store the desired cumulative sums using 2 binary indexed trees?
The trick ...
9
A generalization of this class of problems is widely studied. See, e.g., this paper for a survey.
In your particular case, the problem can be easily solved without any asymptotic change in the computational complexity. Run the binary search three times. At least two of the three results must be equal to the hidden number. Return the majority result.
There ...
8
Recall, how expected value is defined. You count the for every element $X$ in the tree the number of comparisons it takes to locate it, say $C(X)$. Then
$$E[\text{# of comparisons}]=\sum_{X\in\{A,\ldots,H\}} p_X \cdot C(X),$$
where $p_x$ denotes the probability that $X$ is chosen, which is the same for all $X$, namely $1/8$. In other words, you compute the ...
8
As it is, your formula is ambiguous; it is not clear which pair of parentheses to insert in order to get a binary tree. Both
$\qquad \displaystyle \varphi_1 \lor (\varphi_2 \lor \varphi_3)$
and
$\qquad \displaystyle (\varphi_1 \lor \varphi_2) \lor \varphi_3$
are feasible. Luckily for you, $\lor$ is associative, so you can choose either one:
[source]
...
8
There is a general formula for this sum:
$$
\sum_{h=0}^m h2^h = \sum_{h=1}^m \sum_{k=1}^h 2^h = \sum_{k=1}^m \sum_{h=k}^m 2^h = \sum_{k=1}^m (2^{m+1}-2^k) = m2^{m+1} - (2^{m+1}-2).
$$
Overall, we get
$$
\sum_{h=0}^m h2^h = (m-1)2^{m+1} + 2.
$$
When $m = \lg n$, this works out to be $2n\lg n - 2n + 2$.
8
This may not be an exact answer but some information of interest related to your question
Other answers have mentioned various ways in which the binary data structure can be represented and you might want to use one of them but mostly when using databases the Adjacency List Model and Nested Set Model are used for representing Binary Trees.
Binary Trees are ...
8
Your algorithm runs in linear time on all inputs. The algorithm visits each node of the tree exactly once, and does $O(1)$ work per node. Therefore it runs in time $\Theta(n)$, where $n$ is the number of nodes.
The argument above is better than using recurrences, since it is more immediate. It also shows that if you had an arbitrary tree (not necessarily ...
8
Lets assume you consider trees of $n$ nodes. Now take any binary tree with $n$ nodes and name the nodes according to their pre-order numbering. Then clearly the pre-order sequence of the tree will be $1,2,\dots,n$.
This means that we can name the nodes of any binary tree structure so that it will generate the same pre-order sequence as that of another ...
8
Counting argument
The number of unlabeled binary trees of $n$ nodes is the $n^\text{th}$ Catalan number $C_n=(2n)!/(n!(n+1)!).$ For example there are 5 binary trees of 3 nodes,
o o o o o
/ / / \ \ \
o o o o o o .
/ \ ...
7
Consider how a complete binary tree of height $h$ is constructed, one vertex at the root level, two at the first level below the root, four at the second level below, and so on, until the $h^{th}$ level, which has at least one vertex, but at most twice as many as the previous level. Note that the number of vertices at each level is a power of two (excluding ...
Only top voted, non community-wiki answers of a minimum length are eligible
