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, ...
21
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 ...
16
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 ...
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
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
To quote from the answer to “Traversals from the root in AVL trees and Red Black Trees” question
For some kinds of binary search trees, including red-black trees but
not AVL trees, the "fixes" to the tree can fairly easily be predicted
on the way down and performed during a single top-down pass, making
the second pass unnecessary. Such insertion ...
11
The claim is that there are at most $2$ nodes which are expanded at each level. We will prove this by contradiction.
Consider the segment tree given below.
Let's say that there are $3$ nodes that are expanded in this tree. This means that the range is from the left most colored node to the right most colored node. But notice that if the range extends to ...
11
I've been researching this topic recently as well, so here are my findings, but keep in mind that I am not an expert in data structures!
There are some cases where you can't use B-trees at all.
One prominent case is std::map from C++ STL. The standard requires that insert does not invalidate existing iterators
No iterators or references are invalidated....
10
I don't think that degree of a tree is a standard term in either graph theory nor data structures. A degree is usually a property of a node/vertex of a graph, which denotes the number of its incident edges. For trees you sometimes consider only the edges to the children.
I suppose "B-tree with minimum degree of 2" means that every node has at least two ...
9
A B-Tree node can contain more than one key values whereas a BST node contains only one. There are lower and upper bounds on the number of keys a node can contain. These bounds can be expressed in terms of a fixed integer t>=2 called the minimum degree of the B-tree.
Every node other than the root must have at least t-1 keys. Every internal node other ...
9
I suggest you use a binary search tree, augmented so that leaves can contain an interval (a run of consecutive integers). Maintain the invariant that the intervals do not overlap and are in order (following the search tree invariant). (This can be considered a special case of an interval tree or a segment tree, for the special case where the intervals do ...
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
If you modify the AVL tree by storing the size of the subtree at each node rather than just its height, then you can find the median in time $O(\log n)$ using the fact that the tree is balanced. To accomplish this, you write a more general procedure Select which accepts a node $v$ and a number $k$, and finds the $k$th smallest node at the subtree rooted at $...
8
Well the crucial idea about vEB trees is the following: You store all the elements as a 0/1 bitvector of size $s$. For example the vector $(0,1,1,0)$ denotes that in your universe of size $s=4$, the third and second elements are present. Now you subdivide the vectors in blocks of size $\sqrt{s}$ and for every block you also store a flag, if there is at least ...
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
A B-Tree is a type of dictionary, no more and no less. It can be used to implement a set (e.g. see the interface for java.util.Set for the sort of operations we're talking about), but is most commonly used to implement a map (ditto for java.util.Map). So let's just look at maps for a moment.
If you think about a linguistic dictionary, it's ordered by "word",...
8
The search operation is the same for all binary search trees - recurse into the left or right branch depending on whether the element is smaller or larger than the current root. Red-black trees are not special.
The complexity of the search operation is equal to the height of the tree.
Different varieties of binary search trees differ in what guarantees on ...
8
When you're asking about "exact" memory usage, do consider that all of those pointers may not be necessary. To see why, consider that the number of binary trees with $n$ nodes is $C_{2n}$, where:
$$C_i = \frac{1}{i+1} { 2i \choose i }$$
are the Catalan numbers. Using Stirling's approximation, we find:
$$\log C_{2n} = 2n - O(\log n)$$
So to represent a ...
8
You have introduced $n$ and $m$ as the order of B-tree, I will stick to $m$.
Their height will be in the best case $\lceil log_m(N + 1) \rceil$, and the worst case is height $\lceil log_{\frac{m}{2}}(N)\rceil$ but there is also a saturation factor $d$, that you have not mentioned.
The height will be $O(log N)$, please notice that $m$ disappeared, because it ...
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
You're not wrong, but neither are they. The normal formulation is to have the left subtree values be strictly less than ($<$) the current value and the right greater than or equal to ($\geq$) the current value, or vice versa ($\leq$ and $>$), however using $\leq$ and $\geq$ still results in a working BST in the sense that the tree provides an ordering. ...
7
Yes, this is possible.
You can read about it in Ramzi Fadel and Kim Vagn Jakobsen's "Data structures and algorithms in a two-level memory", section 3.1.6, (mirror) or in the OCaml standard library, at the "split" function.
One of the key insights is that the merge function you mention is, with more careful accounting, $O(h_1 - h_2)$, where $h_1$ is the ...
7
If I understand your question correctly, then yes of course you can build a balanced binary tree in $O(n)$ time. Here is a simple pseudocode:
L = [2, 4, 1, 3, 5, 6, 8]
q = Queue()
node root{value = L[0]}
q.add(root)
k = 1
while !q.isEmpty:
n = q.pop
if k < L.size:
n.left = node{value=L[k]}
k++
q.add(n.left)
if k < L.size:
n....
6
I don't think there is a polynomial probability for losing 'balance'. After you insert an element in a skip list, you build a tower of copies above it by flipping a coin until it comes up heads.
So you have layers with fewer and fewer elements as you reach the top. Since a tower has height $k$ with probability $2^{-k}$, there is an element at height $k$ ...
6
In fact, a red-black tree can have all black nodes. In that case the tree is completely balanced and has the required bound.
6
Yes, I believe there is (though I don't remember the details of the paper to confirm).
This is the original paper which dealt with that:
Nievergelt J. and Reingold E.M., "Binary search trees of bounded
balance", Proceedings of the fourth annual ACM symposium on Theory of
computing, pp 137--142, 1972
Here is a page on weight-balanced trees which ...
6
AVL trees should be binary search trees. In the example you gave, 2 is the right child of 3. That isn't right since 2 < 3. Assume the 2 and 3 are switched, which results in a correct binary tree.
Remember the rule for AVL trees: for any node, the height difference between the left child and right child is at most 1. Following the tree down, the 10 is ...
6
In a nutshell: IDA* traverses all paths of lengths iteratively larger and it stops only when expanding (as opposed to generating) the goal node with a cost such that all paths of an inferior cost have been already examined. Monotonicity (or consistency) is not required but admissibility of the heuristic function is a must if optimal solutions are required.
...
Only top voted, non community-wiki answers of a minimum length are eligible
