For the worst case of a red-black tree, what would a tree with 10 nodes look like?Since there can not be 2 consecutive red nodes and there is rotation is it safe to say that it balances out the trees leveling it I tried this attempt at creating a tree with 10 nodes:
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ What do you mean by "the worst case of a red-black tree"? There are many possible red-black trees with 10 nodes. What do you mean by "it balances out the trees leveling"? I see your question was migrated and you don't have an account here. If you (or anyone else) is still interested in the question, please edit it to clarify what you are asking. $\endgroup$– D.W. ♦Commented Mar 24, 2017 at 22:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
As you can read as "Properties" in the "Wiki Red-Black Tree", "the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf.".
For a Red-Black Tree having 'N' nodes, the mean length path is 'ln(N + 1) + 1' (for 'N=10' 'Lmean = 2.397 + 1 >> 4').
Note: `ln(X) = neperian logarithm'.
So the Longest balanced-path from root to leaf is shorter than the double of the mean length '< 2 * ln(N + 1) + 1'. (for 'N= 10' longest < 8).
-
$\begingroup$ I don't see how this answers the question. Please reserve the 'answer' box for material that answers the question that was asked. If you want to post a comment or side remarks, please use the 'comment' feature. Also, your claim about the 'mean path length' seems incorrect. For one th8ing, ln(N+1)+1 is an irrational number; the average length (taken over all paths of a particular tree) can't possibly be irrational. $\endgroup$– D.W. ♦Commented Mar 24, 2017 at 22:12