Lines Matching full:rank
38 * splay trees and rank-balanced trees.
52 * A rank-balanced tree is a binary search tree with an integer
53 * rank-difference as an attribute of each pointer from parent to child.
54 * The sum of the rank-differences on any path from a node down to null is
55 * the same, and defines the rank of that node. The rank of the null node
61 * "Rank Balanced Trees", ACM Transactions on Algorithms Volume 11 Issue 4 June
63 * - every rank-difference is 1 or 2.
64 * - the rank of any leaf is 1.
66 * For historical reasons, rank differences that are even are associated
67 * with the color red (Rank-Even-Difference), and the child that a red edge
70 * Every operation on a rank-balanced tree is bounded as O(lg n).
71 * The maximum height of a rank-balanced tree is 2lg (n+1).
307 /* Macros that define a rank-balanced tree */
496 * Return the rank of the subtree rooted at elm, or -1 if the subtree \
497 * is not rank-balanced, or has inconsistent augmentation data.
533 * balance criterion "the rank of any leaf is 1" precludes the \
544 /* the rank of the tree rooted at elm grew */ \
630 * 'parent' with one higher rank, and then reduces its rank if 'parent' has
632 * with lower rank, to avoid the leaf check. Define RB_STRICT_HST to 1 to get
649 * rank-2 leaf. Demote that leaf. */ \
656 /* the rank of the tree rooted at elm shrank */ \