ໜັງສືພິມ

ຈາກ ວິກິພີເດຍ
ໜັງສືພິມຫຼາຍສະບັບ

ໜັງສືພິມ (ຄຳເຄົ້າ: ໜັງສືພິມພ໌[໑], ອັງກິດ: newspaper, ຝະລັ່ງ: journal) ແມ່ນສິ່ງພິມທີ່ສະເໜີຂ່າວ ການເຄື່ອນໄຫວໃໝ່ໆ ທັງພາຍໃນແລະພາຍນອກປະເທດ ມີກຳໜົດການອອກທີ່ແນ່ນອນຕາຍໂຕ ໂດຍສ່ວນໃຫຍ່ຈະອອກເປັນລາຍມື້. ນອກຈາກນີ້ແລ້ວຍັງມີໜັງສືພິມລາຍສາມມື້ ລາຍສັບປະດາ ແລະລາຍເດືອນ. ໜັງສືພິມມັກຈະພິມລົງໃນເຈ້ຍສຳລັບພິມໜັງສືພິມໂດຍສະເພາະ ເຊິ່ງມີລາຄາຖືກ.

ອ້າງອີງ[ແກ້ໄຂ]

  1. ສົມຈິຕ ພັນລັກ. (2012) ພາສາລາວລ້ານຊ້າງ ກ່ອນປີ ພ.ສ 2478; ຄ.ສ 1935 ສະບັບຄົ້ນຄວ້າ. ສົມມະນາ ການພິມ ສປປ ລາວ.

12.2 Red-Black Trees

A historically popular alternative to the AVL tree is the red-black tree. Operations on

red-black trees take O(logN) time in the worst case, and, as we will see, a careful nonrecursive

implementation (for insertion) can be done relatively effortlessly (compared with

AVL trees).

12.2 Red-Black Trees 567

A red-black tree is a binary search tree with the following coloring properties:

1. Every node is colored either red or black.

2. The root is black.

3. If a node is red, its children must be black.

4. Every path from a node to a null pointer must contain the same number of black

nodes.

A consequence of the coloring rules is that the height of a red-black tree is at

most 2 log(N + 1). Consequently, searching is guaranteed to be a logarithmic operation.

Figure 12.9 shows a red-black tree. Red nodes are shown with double circles.

The difficulty, as usual, is inserting a new item into the tree. The new item, as usual,

is placed as a leaf in the tree. If we color this item black, then we are certain to violate

condition 4, because we will create a longer path of black nodes. Thus, the item must be

colored red. If the parent is black, we are done. If the parent is already red, then we will

violate condition 3 by having consecutive red nodes. In this case, we have to adjust the

tree to ensure that condition 3 is enforced (without introducing a violation of condition 4).

The basic operations that are used to do this are color changes and tree rotations.

12.2.1 Bottom-Up Insertion

As we have already mentioned, if the parent of the newly inserted item is black, we are

done. Thus insertion of 25 into the tree in Figure 12.9 is trivial.

There are several cases (each with a mirror image symmetry) to consider if the parent

is red. First, suppose that the sibling of the parent is black (we adopt the convention that

null nodes are black). This would apply for an insertion of 3 or 8, but not for the insertion

of 99. Let X be the newly added leaf, P be its parent, S be the sibling of the parent (if it

exists), and G be the grandparent. Only X and P are red in this case; G is black, because

otherwise there would be two consecutive red nodes prior to the insertion, in violation of

red-black rules. Adopting the splay tree terminology, X, P, and G can form either a zig-zig

10 20

15 70

30

60 85

5 50

40 55

65 80 90

Figure 12.9 Example of a red-black tree (insertion sequence is: 10, 85, 15, 70, 20, 60,

30, 50, 65, 80, 90, 40, 5, 55)

568 Chapter 12 Advanced Data Structures and Implementation

C A

B B

A

A A B1 B2

C

P S

X

G

X

X G

P

S

C

B1 B2

P S

C

S

G X

P G

Figure 12.10 Zig rotation and zig-zag rotation work if S is black

chain or a zig-zag chain (in either of two directions). Figure 12.10 shows how we can rotate

the tree for the case where P is a left child (note there is a symmetric case). Even though X

is a leaf, we have drawn a more general case that allows X to be in the middle of the tree.

We will use this more general rotation later.

The first case corresponds to a single rotation between P and G, and the second case

corresponds to a double rotation, first between X and P and then between X and G.

When we write the code, we have to keep track of the parent, the grandparent, and, for

reattachment purposes, the great-grandparent.

In both cases, the subtree’s new root is colored black, and so even if the original

great-grandparent was red, we removed the possibility of two consecutive red nodes.

Equally important, the number of black nodes on the paths into A, B, and C has remained

unchanged as a result of the rotations.

So far so good. But what happens if S is red, as is the case when we attempt to insert

79 in the tree in Figure 12.9? In that case, initially there is one black node on the path

from the subtree’s root to C. After the rotation, there must still be only one black node.

But in both cases, there are three nodes (the new root, G, and S) on the path to C. Since

only one may be black, and since we cannot have consecutive red nodes, it follows that

we’d have to color both S and the subtree’s new root red, and G (and our fourth node)

black. That’s great, but what happens if the great-grandparent is also red? In that case, we

could percolate this procedure up toward the root as is done for B-trees and binary heaps,

until we no longer have two consecutive red nodes, or we reach the root (which will be

recolored black).

12.2.2 Top-Down Red-Black Trees

Implementing the percolation would require maintaining the path using a stack or parent

links. We saw that splay trees are more efficient if we use a top-down procedure, and it

12.2 Red-Black Trees 569

c1 c2 c1 c2

X X

Figure 12.11 Color flip: only if X’s parent is red do we continue with a rotation

turns out that we can apply a top-down procedure to red-black trees that guarantees that

S won’t be red.

The procedure is conceptually easy. On the way down, when we see a node X that has

two red children, we make X red and the two children black. (If X is the root, after the color

flip it will be red but can be made black immediately to restore property 2.) Figure 12.11

shows this color flip. This will induce a red-black violation only if X’s parent P is also red.

But in that case, we can apply the appropriate rotations in Figure 12.10. What if X’s parent’s

sibling is red? This possibility has been removed by our actions on the way down, and so

X’s parent’s sibling can’t be red! Specifically, if on the way down the tree we see a node Y

that has two red children, we know that Y’s grandchildren must be black, and that since Y’s

children are made black too, even after the rotation that may occur, we won’t see another

red node for two levels. Thus when we see X, if X’s parent is red, it is not possible for X’s

parent’s sibling to be red also.

As an example, suppose we want to insert 45 into the tree in Figure 12.9. On the way

down the tree, we see node 50, which has two red children. Thus, we perform a color

flip, making 50 red, and 40 and 55 black. Now 50 and 60 are both red. We perform the

single rotation between 60 and 70, making 60 the black root of 30’s right subtree, and

70 and 50 both red. We then continue, performing an identical action if we see other

nodes on the path that contain two red children. When we get to the leaf, we insert 45

as a red node, and since the parent is black, we are done. The resulting tree is shown in

Figure 12.12.

As Figure 12.12 shows, the red-black tree that results is frequently very well balanced.

Experiments suggest that the average red-black tree is about as deep as an average AVL

tree and that, consequently, the searching times are typically near optimal. The advantage

10 20

15 60

30

50 70

5 40

45 80 90

55 65 85

Figure 12.12 Insertion of 45 into Figure 12.9

570 Chapter 12 Advanced Data Structures and Implementation

of red-black trees is the relatively low overhead required to perform insertion, and the fact

that, in practice, rotations occur relatively infrequently.

An actual implementation is complicated not only by the host of possible rotations

but also by the possibility that some subtrees (such as 10’s right subtree) might be empty,

and the special case of dealing with the root (which among other things, has no parent).

Thus, we use two sentinel nodes: one for the root, and nullNode, which indicates

a nullptr pointer as it did for splay trees. The root sentinel will store the key −∞ and

a right link to the real root. Because of this, the searching and printing procedures need

to be adjusted. The recursive routines are trickiest. Figure 12.13 shows how the inorder

traversal is rewritten. The printTree routines are straightforward. The test t!=t->left could

be written as t!=nullNode. However, there is a trap in a similar routine that performs

the deep copy. This is also shown in Figure 12.13. The copy constructor calls clone

after other initialization is complete. But in clone, the test t==nullNode does not work,

because nullNode is the target’s nullNode, not the source’s (that is, not rhs’s). Thus we use a

trickier test.

Figure 12.14 shows the RedBlackTree skeleton, along with the constructor.

Next, Figure 12.15 (page 574) shows the routine to perform a single rotation. Because

the resultant tree must be attached to a parent, rotate takes the parent node as a parameter.

Rather than keeping track of the type of rotation as we descend the tree, we pass item as a

parameter. Since we expect very few rotations during the insertion procedure, it turns out

that it is not only simpler, but actually faster, to do it this way. rotate simply returns the

result of performing an appropriate single rotation.

Finally, we provide the insertion procedure in Figure 12.16 (on page 574). The routine

handleReorient is called when we encounter a node with two red children, and also

when we insert a leaf. The trickiest part is the observation that a double rotation is really

two single rotations, and is done only when branching to X (represented in the insert

method by current) takes opposite directions. As we mentioned in the earlier discussion,

insert must keep track of the parent, grandparent, and great-grandparent as the tree is

descended. Since these are shared with handleReorient, we make these class members.

Note that after a rotation, the values stored in the grandparent and great-grandparent are no

longer correct. However, we are assured that they will be restored by the time they are next

needed.

12.2.3 Top-Down Deletion

Deletion in red-black trees can also be performed top-down. Everything boils down to

being able to delete a leaf. This is because to delete a node that has two children, we

replace it with the smallest node in the right subtree; that node, which must have at most

one child, is then deleted. Nodes with only a right child can be deleted in the same manner,

while nodes with only a left child can be deleted by replacement with the largest node in

the left subtree, and subsequent deletion of that node. Note that for red-black trees, we

don’t want to use the strategy of bypassing for the case of a node with one child because

that may connect two red nodes in the middle of the tree, making enforcement of the

red-black condition difficult.

12.2 Red-Black Trees 571

1 void printTree( ) const

2 {

3 if( header->right == nullNode )

4 cout << "Empty tree" << endl;

5 else

6 printTree( header->right );

7 }

8

9 void printTree( RedBlackNode *t ) const

10 {

11 if( t != t->left )

12 {

13 printTree( t->left );

14 cout << t->element << endl;

15 printTree( t->right );

16 }

17 }

18

19 RedBlackTree( const RedBlackTree & rhs )

20 {

21 nullNode = new RedBlackNode;

22 nullNode->left = nullNode->right = nullNode;

23

24 header = new RedBlackNode{ rhs.header->element };

25 header->left = nullNode;

26 header->right = clone( rhs.header->right );

27 }

28

29 RedBlackNode * clone( RedBlackNode * t ) const

30 {

31 if( t == t->left ) // Cannot test against nullNode!!!

32 return nullNode;

33 else

34 return new RedBlackNode{ t->element, clone( t->left ),

35 clone( t->right ), t->color };

36 }

Figure 12.13 Tree traversals with two sentinels: printTree and copy constructor

Deletion of a red leaf is, of course, trivial. If a leaf is black, however, the deletion is

more complicated because removal of a black node will violate condition 4. The solution

is to ensure during the top-down pass that the leaf is red.

Throughout this discussion, let X be the current node, T be its sibling, and P be

their parent. We begin by coloring the root sentinel red. As we traverse down the tree,

we attempt to ensure that X is red. When we arrive at a new node, we are certain

1 template <typename Comparable>

2 class RedBlackTree

3 {

4 public:

5 explicit RedBlackTree( const Comparable & negInf );

6 RedBlackTree( const RedBlackTree & rhs );

7 RedBlackTree( RedBlackTree && rhs );

8 ~RedBlackTree( );

9

10 const Comparable & findMin( ) const;

11 const Comparable & findMax( ) const;

12 bool contains( const Comparable & x ) const;

13 bool isEmpty( ) const;

14 void printTree( ) const;

15

16 void makeEmpty( );

17 void insert( const Comparable & x );

18 void remove( const Comparable & x );

19

20 enum { RED, BLACK };

21

22 RedBlackTree & operator=( const RedBlackTree & rhs );

23 RedBlackTree & operator=( RedBlackTree && rhs );

24

25 private:

26 struct RedBlackNode

27 {

28 Comparable element;

29 RedBlackNode *left;

30 RedBlackNode *right;

31 int color;

32

33 RedBlackNode( const Comparable & theElement = Comparable{ },

34 RedBlackNode *lt = nullptr, RedBlackNode *rt = nullptr,

35 int c = BLACK )

36 : element{ theElement }, left{ lt }, right{ rt }, color{ c } { }

37

38 RedBlackNode( Comparable && theElement, RedBlackNode *lt = nullptr,

39 RedBlackNode *rt = nullptr, int c = BLACK )

40 : element{ std::move( theElement ) }, left{ lt }, right{ rt }, color{ c } { }

41 };

42

43 RedBlackNode *header; // The tree header (contains negInf)

44 RedBlackNode *nullNode;

45

46 // Used in insert routine and its helpers (logically static)

47 RedBlackNode *current;

Figure 12.14 Class interface and constructor

12.2 Red-Black Trees 573

48 RedBlackNode *parent;

49 RedBlackNode *grand;

50 RedBlackNode *great;

51

52 // Usual recursive stuff

53 void reclaimMemory( RedBlackNode *t );

54 void printTree( RedBlackNode *t ) const;

55

56 RedBlackNode * clone( RedBlackNode * t ) const;

57

58 // Red-black tree manipulations

59 void handleReorient( const Comparable & item );

60 RedBlackNode * rotate( const Comparable & item, RedBlackNode *theParent );

61 void rotateWithLeftChild( RedBlackNode * & k2 );

62 void rotateWithRightChild( RedBlackNode * & k1 );

63 };

64

65 /**

66 * Construct the tree.

67 * negInf is a value less than or equal to all others.

68 */

69 explicit RedBlackTree( const Comparable & negInf )

70 {

71 nullNode = new RedBlackNode;

72 nullNode->left = nullNode->right = nullNode;

73

74 header = new RedBlackNode{ negInf };

75 header->left = header->right = nullNode;12.2 Red-Black Trees

A historically popular alternative to the AVL tree is the red-black tree. Operations on

red-black trees take O(logN) time in the worst case, and, as we will see, a careful nonrecursive

implementation (for insertion) can be done relatively effortlessly (compared with

AVL trees).

12.2 Red-Black Trees 567

A red-black tree is a binary search tree with the following coloring properties:

1. Every node is colored either red or black.

2. The root is black.

3. If a node is red, its children must be black.

4. Every path from a node to a null pointer must contain the same number of black

nodes.

A consequence of the coloring rules is that the height of a red-black tree is at

most 2 log(N + 1). Consequently, searching is guaranteed to be a logarithmic operation.

Figure 12.9 shows a red-black tree. Red nodes are shown with double circles.

The difficulty, as usual, is inserting a new item into the tree. The new item, as usual,

is placed as a leaf in the tree. If we color this item black, then we are certain to violate

condition 4, because we will create a longer path of black nodes. Thus, the item must be

colored red. If the parent is black, we are done. If the parent is already red, then we will

violate condition 3 by having consecutive red nodes. In this case, we have to adjust the

tree to ensure that condition 3 is enforced (without introducing a violation of condition 4).

The basic operations that are used to do this are color changes and tree rotations.

12.2.1 Bottom-Up Insertion

As we have already mentioned, if the parent of the newly inserted item is black, we are

done. Thus insertion of 25 into the tree in Figure 12.9 is trivial.

There are several cases (each with a mirror image symmetry) to consider if the parent

is red. First, suppose that the sibling of the parent is black (we adopt the convention that

null nodes are black). This would apply for an insertion of 3 or 8, but not for the insertion

of 99. Let X be the newly added leaf, P be its parent, S be the sibling of the parent (if it

exists), and G be the grandparent. Only X and P are red in this case; G is black, because

otherwise there would be two consecutive red nodes prior to the insertion, in violation of

red-black rules. Adopting the splay tree terminology, X, P, and G can form either a zig-zig

10 20

15 70

30

60 85

5 50

40 55

65 80 90

Figure 12.9 Example of a red-black tree (insertion sequence is: 10, 85, 15, 70, 20, 60,

30, 50, 65, 80, 90, 40, 5, 55)

568 Chapter 12 Advanced Data Structures and Implementation

C A

B B

A

A A B1 B2

C

P S

X

G

X

X G

P

S

C

B1 B2

P S

C

S

G X

P G

Figure 12.10 Zig rotation and zig-zag rotation work if S is black

chain or a zig-zag chain (in either of two directions). Figure 12.10 shows how we can rotate

the tree for the case where P is a left child (note there is a symmetric case). Even though X

is a leaf, we have drawn a more general case that allows X to be in the middle of the tree.

We will use this more general rotation later.

The first case corresponds to a single rotation between P and G, and the second case

corresponds to a double rotation, first between X and P and then between X and G.

When we write the code, we have to keep track of the parent, the grandparent, and, for

reattachment purposes, the great-grandparent.

In both cases, the subtree’s new root is colored black, and so even if the original

great-grandparent was red, we removed the possibility of two consecutive red nodes.

Equally important, the number of black nodes on the paths into A, B, and C has remained

unchanged as a result of the rotations.

So far so good. But what happens if S is red, as is the case when we attempt to insert

79 in the tree in Figure 12.9? In that case, initially there is one black node on the path

from the subtree’s root to C. After the rotation, there must still be only one black node.

But in both cases, there are three nodes (the new root, G, and S) on the path to C. Since

only one may be black, and since we cannot have consecutive red nodes, it follows that

we’d have to color both S and the subtree’s new root red, and G (and our fourth node)

black. That’s great, but what happens if the great-grandparent is also red? In that case, we

could percolate this procedure up toward the root as is done for B-trees and binary heaps,

until we no longer have two consecutive red nodes, or we reach the root (which will be

recolored black).

12.2.2 Top-Down Red-Black Trees

Implementing the percolation would require maintaining the path using a stack or parent

links. We saw that splay trees are more efficient if we use a top-down procedure, and it

12.2 Red-Black Trees 569

c1 c2 c1 c2

X X

Figure 12.11 Color flip: only if X’s parent is red do we continue with a rotation

turns out that we can apply a top-down procedure to red-black trees that guarantees that

S won’t be red.

The procedure is conceptually easy. On the way down, when we see a node X that has

two red children, we make X red and the two children black. (If X is the root, after the color

flip it will be red but can be made black immediately to restore property 2.) Figure 12.11

shows this color flip. This will induce a red-black violation only if X’s parent P is also red.

But in that case, we can apply the appropriate rotations in Figure 12.10. What if X’s parent’s

sibling is red? This possibility has been removed by our actions on the way down, and so

X’s parent’s sibling can’t be red! Specifically, if on the way down the tree we see a node Y

that has two red children, we know that Y’s grandchildren must be black, and that since Y’s

children are made black too, even after the rotation that may occur, we won’t see another

red node for two levels. Thus when we see X, if X’s parent is red, it is not possible for X’s

parent’s sibling to be red also.

As an example, suppose we want to insert 45 into the tree in Figure 12.9. On the way

down the tree, we see node 50, which has two red children. Thus, we perform a color

flip, making 50 red, and 40 and 55 black. Now 50 and 60 are both red. We perform the

single rotation between 60 and 70, making 60 the black root of 30’s right subtree, and

70 and 50 both red. We then continue, performing an identical action if we see other

nodes on the path that contain two red children. When we get to the leaf, we insert 45

as a red node, and since the parent is black, we are done. The resulting tree is shown in

Figure 12.12.

As Figure 12.12 shows, the red-black tree that results is frequently very well balanced.

Experiments suggest that the average red-black tree is about as deep as an average AVL

tree and that, consequently, the searching times are typically near optimal. The advantage

10 20

15 60

30

50 70

5 40

45 80 90

55 65 85

Figure 12.12 Insertion of 45 into Figure 12.9

570 Chapter 12 Advanced Data Structures and Implementation

of red-black trees is the relatively low overhead required to perform insertion, and the fact

that, in practice, rotations occur relatively infrequently.

An actual implementation is complicated not only by the host of possible rotations

but also by the possibility that some subtrees (such as 10’s right subtree) might be empty,

and the special case of dealing with the root (which among other things, has no parent).

Thus, we use two sentinel nodes: one for the root, and nullNode, which indicates

a nullptr pointer as it did for splay trees. The root sentinel will store the key −∞ and

a right link to the real root. Because of this, the searching and printing procedures need

to be adjusted. The recursive routines are trickiest. Figure 12.13 shows how the inorder

traversal is rewritten. The printTree routines are straightforward. The test t!=t->left could

be written as t!=nullNode. However, there is a trap in a similar routine that performs

the deep copy. This is also shown in Figure 12.13. The copy constructor calls clone

after other initialization is complete. But in clone, the test t==nullNode does not work,

because nullNode is the target’s nullNode, not the source’s (that is, not rhs’s). Thus we use a

trickier test.

Figure 12.14 shows the RedBlackTree skeleton, along with the constructor.

Next, Figure 12.15 (page 574) shows the routine to perform a single rotation. Because

the resultant tree must be attached to a parent, rotate takes the parent node as a parameter.

Rather than keeping track of the type of rotation as we descend the tree, we pass item as a

parameter. Since we expect very few rotations during the insertion procedure, it turns out

that it is not only simpler, but actually faster, to do it this way. rotate simply returns the

result of performing an appropriate single rotation.

Finally, we provide the insertion procedure in Figure 12.16 (on page 574). The routine

handleReorient is called when we encounter a node with two red children, and also

when we insert a leaf. The trickiest part is the observation that a double rotation is really

two single rotations, and is done only when branching to X (represented in the insert

method by current) takes opposite directions. As we mentioned in the earlier discussion,

insert must keep track of the parent, grandparent, and great-grandparent as the tree is

descended. Since these are shared with handleReorient, we make these class members.

Note that after a rotation, the values stored in the grandparent and great-grandparent are no

longer correct. However, we are assured that they will be restored by the time they are next

needed.

12.2.3 Top-Down Deletion

Deletion in red-black trees can also be performed top-down. Everything boils down to

being able to delete a leaf. This is because to delete a node that has two children, we

replace it with the smallest node in the right subtree; that node, which must have at most

one child, is then deleted. Nodes with only a right child can be deleted in the same manner,

while nodes with only a left child can be deleted by replacement with the largest node in

the left subtree, and subsequent deletion of that node. Note that for red-black trees, we

don’t want to use the strategy of bypassing for the case of a node with one child because

that may connect two red nodes in the middle of the tree, making enforcement of the

red-black condition difficult.

12.2 Red-Black Trees 571

1 void printTree( ) const

2 {

3 if( header->right == nullNode )

4 cout << "Empty tree" << endl;

5 else

6 printTree( header->right );

7 }

8

9 void printTree( RedBlackNode *t ) const

10 {

11 if( t != t->left )

12 {

13 printTree( t->left );

14 cout << t->element << endl;

15 printTree( t->right );

16 }

17 }

18

19 RedBlackTree( const RedBlackTree & rhs )

20 {

21 nullNode = new RedBlackNode;

22 nullNode->left = nullNode->right = nullNode;

23

24 header = new RedBlackNode{ rhs.header->element };

25 header->left = nullNode;

26 header->right = clone( rhs.header->right );

27 }

28

29 RedBlackNode * clone( RedBlackNode * t ) const

30 {

31 if( t == t->left ) // Cannot test against nullNode!!!

32 return nullNode;

33 else

34 return new RedBlackNode{ t->element, clone( t->left ),

35 clone( t->right ), t->color };

36 }

Figure 12.13 Tree traversals with two sentinels: printTree and copy constructor

Deletion of a red leaf is, of course, trivial. If a leaf is black, however, the deletion is

more complicated because removal of a black node will violate condition 4. The solution

is to ensure during the top-down pass that the leaf is red.

Throughout this discussion, let X be the current node, T be its sibling, and P be

their parent. We begin by coloring the root sentinel red. As we traverse down the tree,

we attempt to ensure that X is red. When we arrive at a new node, we are certain

1 template <typename Comparable>

2 class RedBlackTree

3 {

4 public:

5 explicit RedBlackTree( const Comparable & negInf );

6 RedBlackTree( const RedBlackTree & rhs );

7 RedBlackTree( RedBlackTree && rhs );

8 ~RedBlackTree( );

9

10 const Comparable & findMin( ) const;

11 const Comparable & findMax( ) const;

12 bool contains( const Comparable & x ) const;

13 bool isEmpty( ) const;

14 void printTree( ) const;

15

16 void makeEmpty( );

17 void insert( const Comparable & x );

18 void remove( const Comparable & x );

19

20 enum { RED, BLACK };

21

22 RedBlackTree & operator=( const RedBlackTree & rhs );

23 RedBlackTree & operator=( RedBlackTree && rhs );

24

25 private:

26 struct RedBlackNode

27 {

28 Comparable element;

29 RedBlackNode *left;

30 RedBlackNode *right;

31 int color;

32

33 RedBlackNode( const Comparable & theElement = Comparable{ },

34 RedBlackNode *lt = nullptr, RedBlackNode *rt = nullptr,

35 int c = BLACK )

36 : element{ theElement }, left{ lt }, right{ rt }, color{ c } { }

37

38 RedBlackNode( Comparable && theElement, RedBlackNode *lt = nullptr,

39 RedBlackNode *rt = nullptr, int c = BLACK )

40 : element{ std::move( theElement ) }, left{ lt }, right{ rt }, color{ c } { }

41 };

42

43 RedBlackNode *header; // The tree header (contains negInf)

44 RedBlackNode *nullNode;

45

46 // Used in insert routine and its helpers (logically static)

47 RedBlackNode *current;

Figure 12.14 Class interface and constructor

12.2 Red-Black Trees 573

48 RedBlackNode *parent;

49 RedBlackNode *grand;

50 RedBlackNode *great;

51

52 // Usual recursive stuff

53 void reclaimMemory( RedBlackNode *t );

54 void printTree( RedBlackNode *t ) const;

55

56 RedBlackNode * clone( RedBlackNode * t ) const;

57

58 // Red-black tree manipulations

59 void handleReorient( const Comparable & item );

60 RedBlackNode * rotate( const Comparable & item, RedBlackNode *theParent );

61 void rotateWithLeftChild( RedBlackNode * & k2 );

62 void rotateWithRightChild( RedBlackNode * & k1 );

63 };

64

65 /**

66 * Construct the tree.

67 * negInf is a value less than or equal to all others.

68 */

69 explicit RedBlackTree( const Comparable & negInf )

70 {

71 nullNode = new RedBlackNode;

72 nullNode->left = nullNode->right = nullNode;

73

74 header = new RedBlackNode{ negInf };

75 header->left = header->right = nullNode;