Maulida Ayu Fitriani

14/371998/PPA/4631 ANALISIS ALGORITMA

Bangun BST untuk kunci berikut sesuai urutan: 4, 3, 2, 1, 11, 8, 5, 6, 7, 9, 10,12, 13.

Kemudian warnai node pada level ganjil dengan warna hitam dan node pada level genap

dengan warna merah (asumsi root ada pada level 1) ulangi menggunakan konsep

transformasi RBT sehingga terbentuk RBT yang benar.

BST dan coloring:

Level ganjil: Hitam

Level genap: Merah

4

3

2

7

10 6

12 8

11

9 13 5

1

Transformasi RBT

4

3

2

7

10 6

12 8

11

9 13 5

1

RIGHT ROTATE

4

3

2

7 10

6

11

8

9 12

5

1

13

CASE 1

RECOLORING

4

3

2

7 10

6

11

8

9 12

5

1

13

LEFT ROTATE

4

3

2

7

10 6

11

8

9 12 5

1

13

RIGHT ROTATE

4

3

2

7

10 6

11

8

9 12 5

1 13

LEFT ROTATE

4

3

2

7 10 5

11

8

9 12 6

1 13

RECOLORING

4

3

2

7 10 5

11

8

9 12 6

1 13