powrót

Ćwiczenia 13 - Drzewo czerwono-czarne

Aplikacja
  1. Każdy węzeł jest albo czerwony, albo czarny.
  2. Każdy liść NIL jest czarny.
  3. Jeśli węzeł jest czerwony, to obaj jego synowie są czarni.
  4. Każda prosta ścieżka z ustalonego węzła do liścia ma tyle samo czarnych węzłów.

Main

STRUCT-TREE T
RB-INSERT(T,11)
RB-INSERT(T,2)
RB-INSERT(T,14)
RB-INSERT(T,1)
RB-INSERT(T,7)
RB-INSERT(T,15)
RB-INSERT(T,5)
RB-INSERT(T,8)
WRITE(T)
RB-INSERT(T,4)
WRITE(T)
RB-DELETE(T,11)
WRITE(T)
RB-DELETE(T,7) // case 2
WRITE(T)
RB-DELETE(T,14)
WRITE(T)
RB-DELETE(T,1) // case 3 4
WRITE(T)
RB-DELETE(T,15) // case 1 2
WRITE(T)

Drzewo czerwono-czarne (10 pkt termin: 20:59:00 21-01-2016)

STRUCT-TREE
1	root = NIL
2	nil = STRUCT-NODE

STRUCT-NODE
1	key = NIL
2	p = NIL
3	left = NIL
4	right = NIL
5	color = BLACK // color = 0 "red" color = 1 "black"

LEFT-ROTATE(T,x)
1	y = x.right
2	x.right = y.left
3	if y.left ≠ NIL
4		y.left.p = x
5	y.p = x.p
6	if x.p = NIL
7		T.root = y
8	else
9		if x = x.p.left
10			x.p.left = y
11		else
12			x.p.right = y
13	y.left = x
14	x.p = y

RB-INSERT(T,x)
1	TREE-INSERT(T,x)
2	x.color = RED
3	while x ≠ T.root AND x.p.color = RED
4		if x.p = x.p.p.left
5			y = x.p.p.right
6			if y.color = RED // case 1L
7				x.p.color = BLACK
8				y.color = BLACK
9				x.p.p.color = RED
10				x = x.p.p
11			else
12				if x = x.p.right // case 2L
13					x = x.p
14					LEFT-ROTATE(T,x)
15				x.p.color = BLACK //case 3L
16				x.p.p.color = RED
17				RIGHT-ROTATE(T,x.p.p)
18		else
19			y = x.p.p.left
20			if y.color = RED // case 1R
21				x.p.color = BLACK
22				y.color = BLACK
23				x.p.p.color = RED
24				x = x.p.p
25			else
26				if x = x.p.left // case 2R
27					x = x.p
28					RIGHT-ROTATE(T,x)
29				x.p.color = BLACK //case 3R
30				x.p.p.color = RED
31				LEFT-ROTATE(T,x.p.p)
32	T.root.color = BLACK

RB-DELETE(T,k)
1	z = TREE-SEARCH-RECURSIVE(T,k)
2	// case 1 z jest liściem
3	// case 2 z ma jedno dziecko
4	// case 3 z ma dwoje dzieci
5	if z.left = T.nil OR z.right = T.nil
6		y = z //case 1 2
7	else
8		y = TREE-SUCCESSOR(z) //case 3
9	if y.left ≠ T.nil
10		x = y.left
11	else
12		x = y.right
13	x.p = y.p //case 2 3
14	if y.p = T.nil
15		T.root = x
16	else
17		if y = y.p.left
18			y.p.left = x
29		else
30			y.p.right = x
31	if y ≠ z //case 3
32		z.key = y.key
33	if y.color = BLACK
34		RB-DELETE-FIXUP(T,x)

RB-DELETE-FIXUP(T,x)
1	while x ≠ T.root AND x.color = BLACK
2		if x = x.p.left
3			w = x.p.right
4			if w.color = RED // case 1R
5				w.color = BLACK
6				x.p.color = RED
7				LEFT-ROTATE(T,x.p)
8				w = x.p.right
9			if w.left.color = BLACK AND w.right.color = BLACK // case 2R
10				w.color = RED
11				x = x.p
12			else
13				if w.right.color = BLACK // case 3R
14					w.left.color = BLACK
15					w.color = RED
16					RIGHT-ROTATE(T,w)
17					w = x.p.right
18				w.color = x.p.color // case 4R
19				x.p.color = BLACK
20				w.right.color = BLACK
21				LEFT-ROTATE(T,x.p)
22				x = T.root
23		else
24			w = x.p.left
25			if w.color = RED // case 1L
26				w.color = BLACK
27				x.p.color = RED
28				RIGHT-ROTATE(T,x.p)
29				w = x.p.left
30			if w.left.color = BLACK AND w.right.color = BLACK // case 2L
31				w.color = RED
32				x = x.p
33			else
34				if w.left.color = BLACK // case 3L
35					w.right.color = BLACK
36					w.color = RED
37					LEFT-ROTATE(T,w)
38					w = x.p.left
39				w.color = x.p.color // case 4L
40				x.p.color = BLACK
41				w.left.color = BLACK
42				RIGHT-ROTATE(T,x.p)
43				x = T.root
44	x.color = BLACK
  1. RIGHT-ROTATE