rbtree.c (rbtree_splitroot): Count output black-heights correctly.

The root is black, so the default would be that the subtrees have
black-height one less.  But if their roots (exist and) are red, then
we'll blacken them, which increases the black-height by one again.

diff --git a/rb-rbregress.ref b/rb-rbregress.ref
index ca80d60d3ead118b118621b6c377c611334ef51d..d2a77b0d400cf9e16487814f1cca529f8c1c72ae 100644 (file)
--- a/rb-rbregress.ref
+++ b/rb-rbregress.ref
@@ -156,3 +156,111 @@ tree dump, ht = 3
        #0x0000001f (n =   1)                       ( ) 55
        #0x00000022 (n =   5)           (*) 57
        #0x00000021 (n =   1)                   (*) 59
+
+;; `rbtree_splitroot' just could not track subtree heights correctly.
+tree dump, ht = 4
+       #0x00000044 (n =   2)                           (*) 4
+       #0x00000043 (n =   1)                               ( ) 6
+       #0x00000046 (n =   4)                   (*) 10
+       #0x00000045 (n =   1)                           (*) 11
+       #0x0000004b (n =   9)               ( ) 13
+       #0x00000047 (n =   1)                           (*) 17
+       #0x0000004a (n =   4)                   (*) 18
+       #0x00000048 (n =   1)                               ( ) 19
+       #0x00000049 (n =   2)                           (*) 20
+       #0x00000050 (n =  14)           (*) 22
+       #0x0000004c (n =   1)                           (*) 23
+       #0x0000004f (n =   4)                   (*) 25
+       #0x0000004d (n =   1)                               ( ) 26
+       #0x0000004e (n =   2)                           (*) 27
+       #0x00000061 (n =  31)   (*) 30
+       #0x00000051 (n =   1)                               ( ) 32
+       #0x00000052 (n =   2)                           (*) 33
+       #0x00000057 (n =   7)                   (*) 34
+       #0x00000054 (n =   2)                           (*) 36
+       #0x00000053 (n =   1)                               ( ) 38
+       #0x00000056 (n =   4)                       ( ) 40
+       #0x00000055 (n =   1)                           (*) 41
+       #0x00000060 (n =  16)           (*) 43
+       #0x00000058 (n =   1)                               ( ) 45
+       #0x00000059 (n =   2)                           (*) 46
+       #0x0000005f (n =   8)                   (*) 48
+       #0x0000005a (n =   1)                               ( ) 49
+       #0x0000005b (n =   2)                           (*) 51
+       #0x0000005e (n =   5)                       ( ) 53
+       #0x0000005d (n =   2)                           (*) 61
+       #0x0000005c (n =   1)                               ( ) 62
+tree dump, ht = 3
+       #0x00000062 (n =   1)                   (*) 6
+       #0x00000064 (n =   3)               ( ) 15
+       #0x00000063 (n =   1)                   (*) 16
+       #0x00000066 (n =   5)           (*) 23
+       #0x00000065 (n =   1)                   (*) 24
+       #0x00000070 (n =  15)       ( ) 33
+       #0x00000067 (n =   1)                   (*) 35
+       #0x0000006a (n =   4)               ( ) 36
+       #0x00000069 (n =   2)                   (*) 37
+       #0x00000068 (n =   1)                       ( ) 39
+       #0x0000006f (n =   9)           (*) 40
+       #0x0000006b (n =   1)                   (*) 43
+       #0x0000006e (n =   4)               ( ) 47
+       #0x0000006d (n =   2)                   (*) 48
+       #0x0000006c (n =   1)                       ( ) 49
+       #0x00000075 (n =  20)   (*) 50
+       #0x00000071 (n =   1)                   (*) 57
+       #0x00000074 (n =   4)           (*) 59
+       #0x00000072 (n =   1)                       ( ) 61
+       #0x00000073 (n =   2)                   (*) 62
+tree dump, ht = 4
+       #0x00000044 (n =   1)                               ( ) 4
+       #0x00000043 (n =   2)                           (*) 6
+       #0x00000046 (n =   4)                   (*) 10
+       #0x00000045 (n =   1)                           (*) 11
+       #0x0000004b (n =  17)           (*) 13
+       #0x00000064 (n =   1)                               ( ) 15
+       #0x00000063 (n =   3)                           (*) 16
+       #0x00000047 (n =   1)                               ( ) 17
+       #0x0000004a (n =   6)                   (*) 18
+       #0x00000048 (n =   1)                               ( ) 19
+       #0x00000049 (n =   2)                           (*) 20
+       #0x00000050 (n =  12)               ( ) 22
+       #0x0000004c (n =   1)                               ( ) 23
+       #0x00000065 (n =   2)                           (*) 24
+       #0x0000004f (n =   5)                   (*) 25
+       #0x0000004d (n =   1)                               ( ) 26
+       #0x0000004e (n =   2)                           (*) 27
+       #0x00000061 (n =  28)       ( ) 30
+       #0x00000051 (n =   2)                           (*) 32
+       #0x00000052 (n =   1)                               ( ) 33
+       #0x00000057 (n =   4)                       ( ) 34
+       #0x00000067 (n =   1)                           (*) 35
+       #0x00000054 (n =   6)                   (*) 36
+       #0x00000069 (n =   1)                           (*) 37
+       #0x00000053 (n =  10)           (*) 38
+       #0x00000068 (n =   1)                           (*) 39
+       #0x00000056 (n =   3)                   (*) 40
+       #0x00000055 (n =   1)                           (*) 41
+       #0x00000060 (n =  41)   (*) 43
+       #0x00000058 (n =   1)                           (*) 45
+       #0x00000059 (n =   3)                   (*) 46
+       #0x0000006e (n =   1)                           (*) 47
+       #0x0000005f (n =  12)           (*) 48
+       #0x0000005a (n =   1)                               ( ) 49
+       #0x00000075 (n =   3)                           (*) 50
+       #0x0000005b (n =   1)                               ( ) 51
+       #0x0000005e (n =   6)                       ( ) 53
+       #0x00000071 (n =   2)                           (*) 57
+       #0x00000074 (n =   1)                               ( ) 59
+       #0x0000005d (n =   8)                   (*) 61
+       #0x0000005c (n =   1)                           (*) 62
+tree dump, ht = 2
+       #0x00000062 (n =   2)           (*) 6
+       #0x00000066 (n =   1)               ( ) 23
+       #0x00000070 (n =   5)       ( ) 33
+       #0x0000006a (n =   2)           (*) 36
+       #0x0000006f (n =   1)               ( ) 40
+       #0x0000006b (n =  10)   (*) 43
+       #0x0000006d (n =   1)               ( ) 48
+       #0x0000006c (n =   2)           (*) 49
+       #0x00000072 (n =   4)       ( ) 61
+       #0x00000073 (n =   1)           (*) 62

diff --git a/rbregress.in b/rbregress.in
index 38dc1718fcffe9bdda4afae0db8a22777a62e1a2..8a7c75e367bc8c87f192c35190851a729a177d6c 100644 (file)
--- a/rbregress.in
+++ b/rbregress.in
@@ -88,3 +88,64 @@ D!
 D!
 
 \ D! ) D! ) D!
+
+:
+:;; `rbtree_splitroot' just could not track subtree heights correctly.
+
+=                                              (((((_ *4
+                                                       (_ 6 _))
+                               *10
+                                               (_ *11 _))
+                       13
+                                               ((_ *17 _)
+                               *18
+                                                       ((_ 19 _)
+                                               *20 _)))
+               *22
+                                               ((_ *23 _)
+                               *25
+                                                       ((_ 26 _)
+                                               *27 _)))
+       *30
+                                                       ((((_ 32 _)
+                                               *33 _)
+                               *34
+                                               ((_ *36
+                                                       (_ 38 _))
+                                       40
+                                               (_ *41 _)))
+               *43
+                                                       (((_ 45 _)
+                                               *46 _)
+                               *48
+                                                       (((_ 49 _)
+                                               *51 _)
+                                       53
+                                               (_ *61
+                                                       (_ 62 _))))))
+D!
+
+(
+=                                      (((((_ *6 _)
+                               15
+                                       (_ *16 _))
+                       *23
+                                       (_ *24 _))
+               33
+                                       (((_ *35 _)
+                               36
+                                       (_ *37
+                                               (_ 39 _)))
+                       *40
+                                       ((_ *43 _)
+                               47
+                                       (_ *48
+                                               (_ 49 _)))))
+       *50
+                                       ((_ *57 _)
+                       *59
+                                               ((_ 61 _)
+                                       *62 _)))
+D!
+
+| D! ) D!

diff --git a/rbtree.c b/rbtree.c
index 8cb7cdeb904c098f393b519fa8cbf4dff24f7634..e4dbeba61197b06bbfec54fa12cdc7813dfd2696 100644 (file)
--- a/rbtree.c
+++ b/rbtree.c
@@ -1285,7 +1285,7 @@ void *rbtree_splitroot(struct bstnode **left_out, int *lht_out,
       if (right->f&RBF_RED) { right->f &= ~RBF_RED; }
     } else {
       if (blkht < 0) blkht = rbtree_height(node);
-      lht = rht = blkht;
+      lht = rht = blkht - 1;
       if (left && left->f&RBF_RED) { lht++; left->f &= ~RBF_RED; }
       if (right && right->f&RBF_RED) { rht++; right->f &= ~RBF_RED; }
       if (lht_out) *lht_out = lht;