pkg/adt violates red-black tree black-height property

[gyuho]

Introduction to Algorithms by Charles E. Leiserson, Clifford Stein, Ronald Rivest, and Thomas H. Cormen:

13.1 Properties of red-black trees

5. For each node, all simple paths from the node to descendant leaves contain the
   same number of black nodes.

Current delete operation violates "black-height" property.

For example, given this red-black tree:

Let's delete the node 11.

The tree should be rebalanced as below:

After deleting 11 (requires rebalancing):

                        [510,511]
                        /      \
                --------        ----------------------------
               /                                            \
           [383,384]                                     [830,831]
           /       \                                    /          \
          /         \                                  /            \
[261,262](red)     [410,411]                  [647,648]           [899,900](red)
        /               \                           \                     /    \
       /                 \                           \                   /      \
    [82,83]           [292,293]                [815,816](red)      [888,889]    [972,973]
        \                                                           /
         \                                                         /
        [238,239](red)                                       [953,954](red)

However, current implementation returns:

After deleting 11 (requires rebalancing):

                       [510,511]
                        /      \
              ----------        --------------------------
             /                                            \
         [82,83]                                       [830,831]
               \                                      /          \
                \                                    /            \
             [383,384]                        [647,648]           [899,900]
             /       \                              \                 /    \
            /         \                              \               /      \
      [261,262]      [410,411]                      [815,816] [888,889]    [972,973]
        /   \                                                                /
       /     \                                                              /
[238,239]   [292,293]                                                [953,954]

This violates "black-height" property.

ref. #10877.

[gyuho]

PRs:

• pkg/adt: refactor + add more test cases #10959
• [TESTING xkeyideal] pkg/adt: fix red black tree to maintain black-height property #10963
• [TESTING textbook implementation] pkg/adt: fix red black tree to maintain black-height property #10964

[gyuho]

Basically we need fix

etcd/pkg/adt/interval_tree_test.go

Lines 255 to 303 in 3b631e1

	// delete the node "11"
	range11 := NewInt64Interval(11, 12)
	if deleted := tr.Delete(NewInt64Interval(11, 12)); !deleted {
	t.Fatalf("range %v not deleted", range11)
	}
	expectedAfterDelete11 := []visitedInterval{
	{root: NewInt64Interval(510, 511), color: black, left: NewInt64Interval(383, 384), right: NewInt64Interval(830, 831), depth: 0},
	{root: NewInt64Interval(383, 384), color: black, left: NewInt64Interval(261, 262), right: NewInt64Interval(410, 411), depth: 1},
	{root: NewInt64Interval(830, 831), color: black, left: NewInt64Interval(647, 648), right: NewInt64Interval(899, 900), depth: 1},
	{root: NewInt64Interval(261, 262), color: red, left: NewInt64Interval(82, 83), right: NewInt64Interval(292, 293), depth: 2},
	{root: NewInt64Interval(410, 411), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 2},
	{root: NewInt64Interval(647, 648), color: black, left: newInt64EmptyInterval(), right: NewInt64Interval(815, 816), depth: 2},
	{root: NewInt64Interval(899, 900), color: red, left: NewInt64Interval(888, 889), right: NewInt64Interval(972, 973), depth: 2},
	{root: NewInt64Interval(82, 83), color: black, left: newInt64EmptyInterval(), right: NewInt64Interval(238, 239), depth: 3},
	{root: NewInt64Interval(292, 293), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
	{root: NewInt64Interval(815, 816), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
	{root: NewInt64Interval(888, 889), color: black, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 3},
	{root: NewInt64Interval(972, 973), color: black, left: NewInt64Interval(953, 954), right: newInt64EmptyInterval(), depth: 3},
	{root: NewInt64Interval(238, 239), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 4},
	{root: NewInt64Interval(953, 954), color: red, left: newInt64EmptyInterval(), right: newInt64EmptyInterval(), depth: 4},
	}
	visitsAfterDelete11 := tr.visitLevel()
	if !reflect.DeepEqual(expectedAfterDelete11, visitsAfterDelete11) {
	// "black-height" property is violated here
	//
	// TODO: fix this
	// [510,511]
	// / \
	// ---------- --------------------------
	// / \
	// [82,83] [830,831]
	// \ / \
	// \ / \
	// [383,384] [647,648] [899,900]
	// / \ \ / \
	// / \ \ / \
	// [261,262] [410,411] [815,816] [888,889] [972,973]
	// / \ /
	// / \ /
	// [238,239] [292,293] [953,954]
	//
	t.Logf("level order after deleting '11' expected %v, got %v", expectedAfterDelete11, visitsAfterDelete11)
	}
	}

ref. https://github.com/etcd-io/etcd/tree/master/pkg/adt

[xkeyideal]

https://github.com/etcd-io/etcd/blob/master/pkg/adt/interval_tree.go#L298

delete node 514 and 11, will not exec the deleteFixUp function, because the node x is nil

I can pass all test cases with my codes.

[gyuho]

@xkeyideal I tried your patch. TestIntervalTreeDelete passes but not TestIntervalTreeContains. Can you try again in a new branch?

[xkeyideal]

@gyuho Please see the code https://github.com/xkeyideal/etcd/blob/master/pkg/adt/interval_tree.go

I change it based on your test cases, it can pass TestIntervalTreeContains

[gyuho]

@xkeyideal Could you create a new PR? Thanks.

[xkeyideal]

@gyuho #10977

[gyuho]

@xkeyideal #10978

[gyuho]

Fixed via 003362e.

Thanks @xkeyideal