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, ...
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 ...
13
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 ...
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
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 $...
9
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
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
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
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
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.
...
6
Without storing points in the inner nodes, but the cut value and cut coordinate, one can use this algorithm to perform NN search:
Procedure NN(node), given query q
if(node is leaf)
Search all points, in node, update current best
else {internal node}
if( cut_coord(q) <= node's cut-value )
NN(left-child)
if( cut-coor(q) + ...
6
I assume that we start labeling heights from $0$.
Actually your approach is right. You must consider the left-side (or right-side) sub-tree with the least possible amount of nodes and the right-side (or left-side) sub-tree with the most possible amount of nodes, and both sub-trees must be AVL trees too. For this purpose, we fix the height of left-side sub-...
6
This is an interesting question. Certainly worth asking.
The choice of a data structure is very much dependent on what you want
to do with it. A more costly sophisticated structure, no matter how
smart, is a bad choice if you can meet your need with something
cheaper in space or time.
As I was writing this answer, I discovered that the wikipedia article
on ...
6
Both Huffman trees and optimal binary decision trees can be though of as mechanisms for playing the (probabilistic) 20 questions game optimally. In the 20 questions game you are given a set of items $X$ and a probability distribution $\pi$ over $X$, and then you are presented an unknown item $x \sim \pi$. Your task is to discover $x$ using the least expected ...
6
Adding to aelguindy's answer: You just can't put n unsorted items into any kind of data structure, and then enumerate them in sorted order, in better than O (n log n) total time - because if you could, then you could sort an array in better than O (n log n) time.
If we define a "sorted" data structure as any data structure that can be enumerated in sorted ...
6
This is a nice question.
In the comparison model or, what is more general, the algebraic decision-tree model, the problem of element distinctness has a lower bound of $\Theta(n\log n)$ time-complexity in the worst case as said in this Wikipedia article. So there is no algorithm to count distinct elements in linear time in the worst case, even without ...
Only top voted, non community-wiki answers of a minimum length are eligible
