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, ...
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 ...
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 ...
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
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
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
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 ...
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
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 ...
10
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 ...
10
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....
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
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
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 ...
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
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
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....
7
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
