Rules for BST Deletion
Red-Black Tree Deletion
Men-delete X dari BST: 1. Jika X adalah leaf, tinggal delete 2. Jika X punya satu anak, ganti dengan anak tsb. 3. Jika X punya dua anak, ganti nilainya dgn predecessor secara inorder.
Men-delete X dari RB Trees: 1. Jika X adalah merah? No problem 2. Jika X adalah hitam? Jika X bukan root, akan mengubah jumlah node hitam salah satu path ke leaf.
Red-Black Trees
Red-Black Trees
Tujuan Top-Down Deletion
Terminology
Men-delete X dari RB Trees: z Usahakan X adalah leaf merah z Sambil mencari lokasi X, semua node yang ditemui diganti merah. z Jika terjadi rule-violation, perbaiki dengan rotasi.
z z z z z
X adalah node yang sdg ditinjau T adalah X’s sibling P adalah parent dari X dan T R adalah anak kanan dari T X L adalah anak kiri dari T
Asumsi: selalu ada pola simetrinya!
P T L
R
1
Red-Black Trees
Red-Black Trees
Basic Strategy
Step 1 – Periksa root!
z Sambil
1.
turun ke lokasi item yang hendak di-delete, kita ubah setiap node X menjadi merah. z Setiap mengubah X ke merah, kita tahu:
Jika kedua anak root hitam: a. Ubah root ke merah. b. Lanjutkan X ke arah lokasi c. Lanjutkan ke Step 2
2.
– P juga merah (baru saja dikunjungi) – T adl hitam (karena P merah)
Jika salah satu anak root merah, lanjutkan ke Step 2B.
Red-Black Trees
Red-Black Trees
Step 2 – Kasus Utama
Case 2A: X punya 2 anak hitam
Sambil turun ke lokasi, kita temui situasi ini sampai mencapai item yang hendak di-delete.
2A1. T punya dua anak hitam 2A2. T punya anak dalam merah 2A3. T punya anak luar merah
P
X
T
Ubah X menjadi merah, dan lakukan penyesuaian thd node lain, rotasi jika perlu berdasar warna X dan anak-anak T. 2A. X punya dua anak hitam 2B. X punya setidaknya satu anak merah.
P
X
T L
R
Jika L dan R merah, bisa dikategorikan kasus 2A2 atau 2A3
2
Case 2A1: Color Flip
Case 2A2: Double Rotation
P
P
X
T
X
L
P T
X
P
T L a
R
X
T a
b
R
b
Red-Black Trees
Case 2A3: Single Rotation P
Case 2B – X punya 1 anak merah Lanjutkan turun ke anak X:
T
2B1. Jika X’ merah, lanjutkan turun ke anak X’.
X
T L
P R
X
R L
2B2. Jika X hitam (T merah dan P hitam). z Lakukan Rotasi T terhadap P z Recolor P dan T z Kembali ke Step 2
3
Red-Black Trees
P
Case 2B
X
Lanjutkan turun ke anak X!
Case 2B2 P X
Step 3
T
Case 2B1 T
P T T P
Kembali ke Step 2
Akhirnya ditemukan node yang didelete – sebuah leaf atau parent dari sebuah leaf. Tinggal delete! Ubah kembali root menjadi hitam.
X
Lanjutkan turun ke anak X lagi!
X
TopTop-Down Deletion Scenario
Red-Black Trees
Contoh 1: Delete 10
Ada anak merah
Step 1
Root → merah X → merah Step 2 Dua anak hitam
Satu anaknya merah Anak luar merah
Anak dalam merah Step 2A1 Flip color
X’ merah Step 2B1
Step 2A3 Step 2A2
Step 2B
Single rotation
Double rotation Step 3
Delete X
Step 4
Root → hitam
15
Turun ke anak
6
X’ hitam
Step 2B2
X 17
3
12
20
16
Turun ke anak Rotasi T thd P Recolor T&P
10 7
Ke Step 2
13
18
23
Step 1 – Root punya 2 anak hitam. Jadikan Root merah
4
Contoh 1: Delete 10 (lanjutan)
Contoh 1: Delete 10 (lanjutan)
15
15
X 6
17
3
12
6 20
16
17
3
12
X
20
16
X′ 10
18
13
7
10
23 7
Turun ke anak Root, X pindah ke 6
Contoh 1: Delete 10 (lanjutan)
Contoh 1: Delete 10 (lanjutan) 15
6
17 12
23
Salah satu anak X merah (case 2B). Turun ke anak, X pindah ke 12. Karena X baru (12) juga merah (2B1), turun lagi ke 10.
15
3
18
13
6 20
16
17
3
12
20
16
X 10 7
13
18
23
Step 3: karena 10 adalah node yang akan di-delete, nilainya diperbaharui dengan nilai anaknya (7) dan selanjutnya delete 7.
7
13
18
23
Kondisi akhir setelah root dijadikan hitam (Step 4) lagi .
5
Contoh 2: Delete 9
Contoh 2: Delete 9 (lanjutan)
X 15
X 15
6
17
3 2
12 4
9
6 20
16 13
3 2
12 4
Step 1 – root punya 1 anak merah Root dijadikan merah. X = root, lanjutkan ke step 2
Contoh 2: Delete 9 (lanjutan)
17
9
13
X punya 1 anak merah (case 2B). Lanjutkan turun ke anak, yaitu 6. Karena 6 juga merah (case 2B1), lanjutkan lagi turun ke 12.
Contoh 2: Delete 9 (lanjutan)
15
15
P 6 3 T 2
4
17
X 12 9
20
16
16
6 20
13
X punya 2 anak hitam. Sibling X juga punya 2 anak hitam. Case 2A1 – recolor X, P dan T. Lanjutkan turun ke node 9.
17
P 12
3 2
4
9
X
16 13
20
T
X sekarang node yang akan di-delete, tapi hitam. Kembali ke step 2. X punya 2 anak hitam dan T punya 2 anak hitam – case 2A1. Recolor X, P dan T.
6
Contoh 2: Delete 9 (lanjutan)
Contoh 2: Delete 9 (lanjutan)
15
15
6
17
P 12
3 2
4
9
X
16 13
6 20
17
3 2
T
Step 3 – Delete 9 sebagai leaf merah. Step 4 – Recolor root ke hitam.
12 4
16 13
Kondisi akhir setelah root menjadi hitam kembali.
Contoh 3: Delete 11
Contoh 3: Delete 11 (lanjutan)
X 15 10 5 3 2
4
7 6
11 9
15 X 10
17 12 13
20
5
Valid and unaffected right subtree
Step 1 – root punya 2 anak hitam. Jadikan root merah. Set X ke anak dari root (10)
3 2
4
17 12
7 6
11 9
13
Valid and unaffected right subtree
X punya satu anak merah (case 2B) Turun ke node anak, X = 12
7
Contoh 3: Delete 11 (lanjutan) 15
P
2
6
17 X 12
7
4
15
10
5 T 3
Contoh 3: Delete 11 (lanjutan)
11
Valid and unaffected right subtree
13
9
Karena X adalah hitam (case 2B2), dan T merah P hitam, rotasi T thd P. Recolor T and P dan kembali ke step 2
Contoh 3: Delete 11 (lanjutan)
17
5 3 2
10 4
9
11
13
Sekarang X sudah hitam dengan parent merah dan sibling hitam. X dan T punya 2 anak merah (case 2A1). Recolor X, P dan T.
Contoh 3: Delete 11 (lanjutan)
15
15 17
5 3 2
10 4
7 T 6
9
Lanjutkan X ke 11.
Valid and unaffected right subtree
X 12 13
17
5
P
11
Valid and unaffected right subtree
X 12
7 T 6
P
3 2
10 4
12
7 6
9
11 X
P
Valid and unaffected right subtree
13 T
Karena 11 yang hendak di-delete hitam, kembali ke step 2. X dan T keduanya punya 2 anak hitam. Recolor X, P dan T.
8
Contoh 3: Delete 11 (lanjutan)
Contoh 3: Delete 11 (lanjutan)
15
15 17
5 3 2
10 4
12
7 6
9
11 X
P
Valid and unaffected right subtree
13 T
Sekarang node yang hendak di-delete merah. Step 3 – delete 11 sebagai node merah.
17
5 3 2
10 4
12
7 6
Valid and unaffected right subtree
9
13
Step 4 – kembalikan root ke hitam.
9
