Ćwiczenia 12 - Drzewo BST

STRUCT-TREE T
TREE-INSERT(T,15)
TREE-INSERT(T,5)
TREE-INSERT(T,16)
TREE-INSERT(T,3)
TREE-INSERT(T,12)
TREE-INSERT(T,20)
TREE-INSERT(T,10)
TREE-INSERT(T,6)
TREE-INSERT(T,7)
TREE-INSERT(T,13)
TREE-INSERT(T,18)
TREE-INSERT(T,23)
WRITE(T)
WRITE(TREE-SEARCH-RECURSIVE(T,13))
WRITE(TREE-SEARCH-ITERATIVE(T,13))
WRITE(TREE-SUCCESSOR(TREE-SEARCH-RECURSIVE(T,5)))
WRITE(TREE-SUCCESSOR(TREE-SEARCH-RECURSIVE(T,13)))
TREE-DELETE(T,13)
WRITE(T)
TREE-DELETE(T,16)
WRITE(T)
TREE-DELETE(T,5)
WRITE(T)

STRUCT-TREE
1	root = NIL

STRUCT-NODE
1	key = NIL
2	p = NIL
3	left = NIL
4	right = NIL

TREE-SEARCH-RECURSIVE(T,k) // argument T tylko dla funkcji opakowującej
1	x = T.root
2	if x = NIL OR x.key = k
3		return x
4	if k < x.key
5		return TREE-SEARCH-RECURSIVE(x.left,k)
6	else
7		return TREE-SEARCH-RECURSIVE(x.right,k)

TREE-SEARCH-ITERATIVE(T,k)
1	x = T.root
2	while x ≠ NIL AND k ≠ x.key
3		if k < x.key
4			x = x.left
5		else
6			x = x.right
7	return x

TREE-SUCCESSOR(x)
1	if x.right ≠ NIL
2		return TREE-MINIMUM(x.right)
3	y = x.p
4	while y ≠ NIL AND x = y.right
5		x = y
6		y = y.p
7	return y

TREE-INSERT(T,k)
1	z.key = k
2	y = NIL
3	x = T.root
4	while x ≠ NIL
5		y = x
6		if z.key < x.key
7			x = x.left
8		else
9			x = x.right
10	z.p = y
11	if y = NIL
12		T.root = z
13	else
14		if z.key < y.key
15			y.left = z
16		else
17			y.right = z

TREE-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 = NIL OR z.right = NIL
6		y = z //case 1 2
7	else
8		y = TREE-SUCCESSOR(z) //case 3
9	if y.left ≠ NIL
10		x = y.left
11	else
12		x = y.right
13	if x ≠ NIL
14		x.p = y.p //case 2 3
15	if y.p = NIL
16		T.root = x
17	else
18		if y = y.p.left
19			y.p.left = x
20		else
21			y.p.right = x
22	if y ≠ z //case 3
23		z.key = y.key