168
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 ...
63
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)...
35
For counting many types of combinatorial objects, like trees in this case, there are powerful mathematical tools (the symbolic method) that allow you to mechnically derive such counts from a description how the combinatorial objects are constructed. This involves generating functions.
An excellent reference is Analytic Combinatorics by the late Philipe ...
34
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 ...
32
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 ...
31
Claim: Red-black trees can be arbitrarily un-$\mu$-balanced.
Proof Idea: Fill the right subtree with as many nodes as possible and the left with as few nodes as possible for a given number $k$ of black nodes on every root-leaf path.
Proof: Define a sequence $T_k$ of red-black trees so that $T_k$ has $k$ black nodes on every path from the root to any (...
30
The simpler balancing algorithm can require $\Omega(n)$ amortized time per rotation in the worst case. Suppose the tree is just a totally unbalanced path of right children; no node has a left child. The only leaf in this tree is the tree with the maximum key. If you rotate this step by step up to the root, you've used $n-1$ rotations, and the resulting ...
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, ...
26
A whole treatise could be written on this topic; I'm just going to cover some salient points, and I'll keep the discussion of other data structures to a minimum (there are many variants indeed). Throughout this answer, $n$ is the number of keys in the dictionary.
The short answer is that hash tables are faster in most cases, but can be very bad at their ...
20
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 ...
18
Claim: No, there is no such $\mu$.
Proof: We give an infinite sequence of AVL trees of growing size whose weight-balance value tends to $0$, contradicting the claim.
Let $C_h$ the complete tree of height $h$; it has $2^{h+1}-1$ nodes.
Let $S_h$ the Fibonacci tree of height $h$; it has $F_{h+2} - 1$ nodes. [1,2,TAoCP 3]
Now let $(T_h)_{i\geq 1}$ with $T_h ...
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.
18
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 ...
17
Definition 1. is also known as weight-balancedness¹ and definition 2. as height-balancedness.
Height-balancedness does not imply weight-balancedness; examples are both AVL- and Red-Black-Trees. See here and here for proofs, respectively.
Weight-balancedness does imply height-balancedness, though. This can be proven by showing the following stronger fact by ...
16
First, I'll assume that all elements are distinct. No amount of sequentialisations is going to tell you the shape of a tree with elements [3,3,3,3,3]. It is possible to reconstruct some trees with duplicate elements, of course; I don't know what nice sufficient conditions exist.
Continuing on the negative results, you can't fully rebuild a binary tree from ...
16
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 ...
14
No. Consider a red-black tree with the following special structure.
The left subtree is a complete binary tree with depth $d$, in which every node is black.
The right subtree is a complete binary tree with depth $2d$, in which every node at odd depth is red, and every node at even depth is black.
It's straightforward to check that this is a valid red-...
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
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 ...
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
I don't think your proof is valid, because it only considers trees, and a certain type of trees at that. If there were an algorithm with a smaller lower bound for what you describe, we'd have a sorting algorithm faster than $\Omega(n \log n)$ no matter which of the two operations is $\log n$. So the problem reduces to proving that sorting cannot be faster ...
12
Just two pointers:
If you want to actually combine the ideas of priority queues and binary search trees, think about combining heap and BST in one structure.
There is the concept of self-organising lists. The idea is to move recently accessed element to (or towards the) front in order to speed up future accesses to the same element, thusly "learning" the ...
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 = ...
11
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$.
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 ...
11
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.
10
Do not forget that $\log n$ still grows exponentially (in $\log(n)$) faster than $\log(\log n)$!
Indeed, if you look at the quotient of $\log(n)$ and $\log(\log(n))$, there is not much impressive to see:
[source]
But still, you get a factor five to six for sizes up to $100000$. Note that larger sizes are not uncommon in practice, and a speedup by that ...
10
Yes, you can perform this compression in $O(n \log n)$ time, but it is not easy :) We first make some observations and then present the algorithm. We assume the tree is initially not compressed - this is not really needed but makes analysis easier.
Firstly, we characterize 'structural equality' inductively. Let $T$ and $T'$ be two (sub)trees. If $T$ and ...
10
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:
...
Only top voted, non community-wiki answers of a minimum length are eligible
