Monday, December 26, 2016

Bab 20. Soal & Penyelesaian C++ (Bagian 2)

Pohon (Bagian 2)




1.       Demonstrasikanlah penggunaan dari poho-B.
Penyelesaian:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
186
188
189
//pohonB.cpp
/*
 * Program C++ untuk mengimplementasikan pohon-B
 */
#include <iostream>
#include <conio.h>
using namespace std;

// Simpul Pohon-B
class SimpulPohonB
{
    private:
        int *kunci;
        int t;
        SimpulPohonB **C;
        int n;
        bool daun;

    public:
        SimpulPohonB(int t1, bool daun1)
        {
            t = t1;
            daun = daun1;
            kunci = new int[2*t-1];
            C = new SimpulPohonB *[2*t];
            n = 0;
        }

        // menjelajah semua simpul pada subpohon dengan akar simpul ini
        void jelajah()
        {
            int i;
            for (i = 0; i < n; i++)
            {
                if (daun == false)
                    C[i]->jelajah();
                cout << " " << kunci[i];
            }
            if (daun == false)
                C[i]->jelajah();
        }

        void sisipTakPenuh(int k)
        {
            int i = n-1;
            if (daun == true)
            {
                while (i >= 0 && kunci[i] > k)
                {
                    kunci[i+1] = kunci[i];
                    i--;
                }
                kunci[i+1] = k;
                n = n+1;
            }

            else
            {
                while (i >= 0 && kunci[i] > k)
                    i--;
                if (C[i+1]->n == 2*t-1)
                {
                    bagiAnak(i+1, C[i+1]);
                    if (kunci[i+1] < k)
                        i++;
                }
                C[i+1]->sisipTakPenuh(k);
            }
        }

        void bagiAnak(int i, SimpulPohonB *y)
        {
            SimpulPohonB *z = new SimpulPohonB(y->t, y->daun);
            z->n = t - 1;
            for (int j = 0; j < t-1; j++)
                z->kunci[j] = y->kunci[j+t];

            if (y->daun == false)
            {
                for (int j = 0; j < t; j++)
                    z->C[j] = y->C[j+t];
            }

            y->n = t - 1;
            for (int j = n; j >= i+1; j--)
                C[j+1] = C[j];
            C[i+1] = z;

            for (int j = n-1; j >= i; j--)
                kunci[j+1] = kunci[j];
            kunci[i] = y->kunci[t-1];
            n = n + 1;
        }

        SimpulPohonB *cari(int k)
        {
            int i = 0;
            while (i < n && k > kunci[i])
                i++;
            if (kunci[i] == k)
                return this;
            if (daun == true)
                return NULL;
            return C[i]->cari(k);
        }
        friend class PohonB;
};

// Kelas PohonB
class PohonB
{
    private:
        SimpulPohonB *akar;
        int t;
    public:
        PohonB(int _t)
        {
            akar = NULL;
            t = _t;
        }

        void jelajah()
        {
            if (akar != NULL)
                akar->jelajah();
        }

        SimpulPohonB* cari(int k)
        {
            return (akar == NULL)? NULL : akar->cari(k);
        }

        void sisip(int k)
        {
            if (akar == NULL)
            {
                akar = new SimpulPohonB(t, true);
                akar->kunci[0] = k;
                akar->n = 1;
            }

            else
            {
                if (akar->n == 2*t-1)
                {
                    SimpulPohonB *s = new SimpulPohonB(t, false);
                    s->C[0] = akar;
                    s->bagiAnak(0, akar);
                    int i = 0;

                    if (s->kunci[0] < k)
                        i++;
                    s->C[i]->sisipTakPenuh(k);
                    akar = s;
                }
                else
                    akar->sisipTakPenuh(k);
            }
        }
};

// Main
int main()
{
    PohonB t(3);
    t.sisip(10);
    t.sisip(20);
    t.sisip(5);
    t.sisip(6);
    t.sisip(12);
    t.sisip(30);
    t.sisip(7);
    t.sisip(17);

    cout << "Penjelajahan atas pohon ";
    t.jelajah();
    cout<<endl;

    int k = 6;
    cout<<k<<" = ";
    (t.cari(k) != NULL)? cout << "Ada\n" : cout << "Tidak Ada";

    k = 15;
    cout<<k<<" = ";
    (t.cari(k) != NULL)? cout << "Ada\n" : cout << "Tidak Ada\n";

    getch();
    return 0;
}

Penjelajahan atas pohon  5 6 7 10 12 17 20 30
6 = Ada
15 = Tidak Ada

2.       Demonstrasikanlah penggunaan Trie untuk mengklasterkan Anagram.
Penyelesaian:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <algorithm>
#include <conio.h>
using namespace std;

/*
 * Deklarasi basis simpul Trie
 */
struct Basis_Simpul_Trie
{
    vector<Basis_Simpul_Trie*> anak;
    int jumAnak;

    Basis_Simpul_Trie(int n)
    {
        jumAnak = n;
        for (int i = 0; i < n; ++i)
            anak.push_back(NULL);
    }
};
/*
 * Deklarasi Simpul Trie
 */
struct SimpulTrie : public Basis_Simpul_Trie
{
    bool apaKata;
    vector<vector<string>::const_iterator> head;

    SimpulTrie(int num):Basis_Simpul_Trie(num), apaKata(false){}
};

/*
 * Deklarasi Kelas Trie
 */
class Trie
{
    public:
        Trie(int n = 26)
        {
            akar = new SimpulTrie(n);
        }

        ~Trie()
        {
            hancurkan(akar);
        }

        void simpul_trie_i(const string& w, vector<string>::const_iterator ind);

        SimpulTrie* GetSimpulAkar()
        {
            return akar;
        }
        private:
            SimpulTrie* akar;
            void hancurkan(SimpulTrie* akar);
};
/*
 * Menyisipkan Simpul Trie
 */
void Trie::simpul_trie_i(const string& w, vector<string>::const_iterator ind)
{
    SimpulTrie *r = akar;
    string::const_iterator runner = w.begin();
    for (; runner!=w.end(); ++runner)
    {
        char karSkrg = *runner;
        int i = karSkrg - 'a';

        if (r->anak[i] == NULL)
        {
            r->anak[i] = new SimpulTrie(r->jumAnak);
        }
        r = (SimpulTrie*)r->anak[i];
    }

    if (!r->apaKata)
        r->apaKata = true;
    r->head.push_back(ind);
}
/*
 * Menghancurkan Trie
 */
void Trie::hancurkan(SimpulTrie* akar)
{
    vector<Basis_Simpul_Trie*>::iterator it = (akar->anak).begin();

    for (; it != (akar->anak).end(); ++it)
    {
        if (*it != NULL)
            hancurkan((SimpulTrie*)(*it));
    }
    delete akar;
}

/*
 * Penjelajahan Trie
 */
void jelajahTrie(const vector<string>& arrayKata, SimpulTrie* r)
{
    size_t i;
    if (r->apaKata)
    {
        vector<vector<string>::const_iterator>::iterator it = (r->head).begin();
        for (; it != (r->head).end(); ++it)
        {
            cout << *(*it) << endl;
        }
    }


    for (i = 0; i < r->jumAnak; ++i)
    {
        if (r->anak[i] != NULL)
            jelajahTrie(arrayKata, (SimpulTrie*)r->anak[i]);
    }
}

/*
 * Mengklasterisasi Anagram menggunakan Trie
 */
void klasterAnagram(const vector<string>& arrayKata, size_t ukuran)
{
    Trie* trie = new Trie(26);

    vector<string>::const_iterator it = arrayKata.begin();
    for (; it != arrayKata.end(); ++it)
    {
        string strSkrg = *it;
        sort (strSkrg.begin(), strSkrg.end());
        trie->simpul_trie_i(strSkrg, it);
    }
    jelajahTrie(arrayKata, trie->GetSimpulAkar());
}
/*
 * Main
 */
int main()
{
    const char* arrayKata[] = {"cat", "dog", "tac", "god", "act", "gdo"};
    size_t ukuran = sizeof(arrayKata) / sizeof(arrayKata[0]);

    vector<string> arrayKata1(arrayKata, arrayKata + ukuran);
    klasterAnagram(arrayKata1, ukuran);

    getch();
    return 0;
}

cat
tac
act
dog
god
gdo

3.       Demonstrasikanlah pohon pencarian biner seimbang dalam sebuah program C++.
Penyelesaian:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
//pohonBinerSeimbang.cpp
/*
 *  Program C++ untuk mengimplementasikan Pohon Pencarian Biner Seimbang
 */
#include <iostream>
#include <cstdlib>
#include <conio.h>
using namespace std;

/* Kelas Simpul_SBBST */

class Simpul_SBBST
{
    public:
        int tinggi, data;
        Simpul_SBBST *kiri, *kanan;

         /* Konstruktor */
         Simpul_SBBST()
         {
             kiri = NULL;
             kanan = NULL;
             data = 0;
             tinggi = 0;
         }

         /* Konstruktor */
         Simpul_SBBST(int n)
         {
             kiri = NULL;
             kanan = NULL;
             data = n;
             tinggi = 0;
         }
};

/*
 * Kelas PohonBSTSeimbang
 */

class PohonBSTSeimbang
{
    private:
        Simpul_SBBST *akar;
    public:
         /* Konstruktor */
         PohonBSTSeimbang()
         {
             akar = NULL;
         }

         /* Fungsi untuk memeriksa apakah pohon kosong */
         bool apaKosong()
         {
             return akar == NULL;
         }

         /* Membuat pohon kosong */
         void membuatKosong()
         {
             akar = NULL;
         }

         /* Fungsi untuk menyisipkan data */
         void sisip(int data)
         {
             akar = sisip(data, akar);
         }

         /* Fungsi untuk mendapatkan tinggi simpul */
         int tinggi(Simpul_SBBST *t)
         {
             return t == NULL ? -1 : t->tinggi;
         }

         /* Fungsi untuk mencari maks dari simpul kiri/kanan */
         int maks(int lhs, int rhs)
         {
             return lhs > rhs ? lhs : rhs;
         }

         /* Fungsi untuk menyisipkan data secara rekursif */
         Simpul_SBBST *sisip(int x, Simpul_SBBST *t)
         {
             if (t == NULL)
                 t = new Simpul_SBBST(x);

             else if (x < t->data)
             {
                 t->kiri = sisip(x, t->kiri);
                 if (tinggi(t->kiri) - tinggi(t->kanan) == 2)
                     if (x < t->kiri->data)
                         t = rotasiDenganAnakKiri(t);
                     else
                         t = doubleDenganAnakKiri(t);
             }

             else if (x > t->data)
             {
                 t->kanan = sisip(x, t->kanan);
                 if (tinggi(t->kanan) - tinggi(t->kiri) == 2)
                     if (x > t->kanan->data)
                         t = rotasiDenganAnakKanan(t);
                     else
                         t = doubleDenganAnakKanan(t);
             }
             t->tinggi = maks(tinggi(t->kiri), tinggi(t->kanan)) + 1;
             return t;
         }

         /* Merotasi simpul pohon biner dengan anak kiri */
         Simpul_SBBST *rotasiDenganAnakKiri(Simpul_SBBST* k2)
         {
             Simpul_SBBST *k1 = k2->kiri;
             k2->kiri = k1->kanan;
             k1->kanan = k2;
             k2->tinggi = maks(tinggi(k2->kiri), tinggi(k2->kanan)) + 1;
             k1->tinggi = maks(tinggi(k1->kiri), k2->tinggi) + 1;
             return k1;
         }

         /* Merotasi simpul pohon biner dengan anak kanan */
         Simpul_SBBST *rotasiDenganAnakKanan(Simpul_SBBST *k1)
         {
             Simpul_SBBST *k2 = k1->kanan;
             k1->kanan = k2->kiri;
             k2->kiri = k1;
             k1->tinggi = maks(tinggi(k1->kiri), tinggi(k1->kanan)) + 1;
             k2->tinggi = maks(tinggi(k2->kanan), k1->tinggi) + 1;
             return k2;
         }

         /*
          * Merotasi ganda pohon biner: pertama-tama anak kiri
          * dengan anak kanannya; kemudian simpul k3 dengan anak kiri baru
          */
         Simpul_SBBST *doubleDenganAnakKiri(Simpul_SBBST *k3)
         {
             k3->kiri = rotasiDenganAnakKanan(k3->kiri);
             return rotasiDenganAnakKiri(k3);
         }

               /*
          * Merotasi ganda pohon biner: pertama-tama anak kanan
          * dengan anak kirinya; kemudian simpul k1 dengan anak kanan baru
          */

         Simpul_SBBST *doubleDenganAnakKanan(Simpul_SBBST *k1)
         {
             k1->kanan = rotasiDenganAnakKiri(k1->kanan);
             return rotasiDenganAnakKanan(k1);
         }

         /* Fungsi untuk menghitung jumlah simpul */
         int hitungSimpul()
         {
             return hitungSimpul(akar);
         }

         int hitungSimpul(Simpul_SBBST *r)
         {
             if (r == NULL)
                 return 0;
             else
             {
                 int l = 1;
                 l += hitungSimpul(r->kiri);
                 l += hitungSimpul(r->kanan);
                 return l;
             }
         }

         /* Fungsi untuk melakukan pencarian thd suatu elemen */
         bool cari(int nil)
         {
             return cari(akar, nil);
         }

         bool cari(Simpul_SBBST *r, int nil)
         {
             bool ditemukan = false;
             while ((r != NULL) && !ditemukan)
             {
                 int nilaiKanan = r->data;

                 if (nil < nilaiKanan)
                     r = r->kiri;
                 else if (nil > nilaiKanan)
                     r = r->kanan;
                 else
                 {
                     ditemukan = true;
                     break;
                 }
                 ditemukan = cari(r, nil);
             }
             return ditemukan;
         }

         /* Fungsi untuk penjelajahan inorder */
         void inorder()
         {
             inorder(akar);
         }

         void inorder(Simpul_SBBST *r)
         {
             if (r != NULL)
             {
                 inorder(r->kiri);
                 cout<<r->data<<"  ";
                 inorder(r->kanan);
             }
         }

         /* Fungsi untuk penjelajahan preorder */
         void preorder()
         {
             preorder(akar);
         }

         void preorder(Simpul_SBBST *r)
         {
             if (r != NULL)
             {
                 cout<<r->data<<"  ";
                 preorder(r->kiri);
                 preorder(r->kanan);
             }
         }

         /* Fungsi untuk penjelajahan postorder */
         void postorder()
         {
             postorder(akar);
         }

         void postorder(Simpul_SBBST *r)
         {
             if (r != NULL)
             {
                 postorder(r->kiri);
                 postorder(r->kanan);
                 cout<<r->data<<"  ";
             }
         }
};

int main()
{
    PohonBSTSeimbang sbbst;
    cout<<"Uji Pohon BST Seimbang\n";
    int nil;
    char ch;

    /*  Melakukan operasi-operasi pohon  */
    do
    {
        cout<<"\nOperasi-Operasi Pohon BST Seimbang\n";
        cout<<"1. Sisip "<<endl;
        cout<<"2. Hitung Simpul"<<endl;
        cout<<"3. Cari"<<endl;
        cout<<"4. Periksa Kosong"<<endl;
        cout<<"5. Membuat Kosong"<<endl;

        int pilihan;
        cout<<"Masukkan pilihan Anda: ";
        cin>>pilihan;

        switch (pilihan)
        {
        case 1 :
            cout<<"Masukkan elemen integer yang akan disisipkan: ";
            cin>>nil;
            sbbst.sisip(nil);
            break;

        case 2 :
            cout<<"Simpul = " <<sbbst.hitungSimpul()<<endl;
            break;

        case 3:
            cout<<"Masukkan elemen integer yang akan dicari: ";
            cin>>nil;

            if (sbbst.cari(nil))
                cout<<nil<<" ditemukan di dalam pohon"<<endl;
            else
                cout<<nil<<" tidak ditemukan"<<endl;
            break;

        case 4 :
            cout<<"Status kosong = ";
            if (sbbst.apaKosong())
                cout<<"Pohon kosong"<<endl;
            else
                cout<<"Pohon tidak kosong"<<endl;
            break;

        case 5 :
            cout<<"\nPohon dikosongkan\n";
            sbbst.membuatKosong();
            break;

        default :
            cout<<"Entri salah \n ";
            break;
        }

        /*  Menampilkan pohon*/
        cout<<"\nPost order : ";
        sbbst.postorder();
        cout<<"\nPre order : ";
        sbbst.preorder();
        cout<<"\nIn order : ";
        sbbst.inorder();
        cout<<"\nAnda ingin melanjutkan (Ketik y atau t): ";
        cin>>ch;
    }
    while (ch == 'Y'|| ch == 'y');

    getch();
    return 0;
}

Uji Pohon BST Seimbang

Operasi-Operasi Pohon BST Seimbang
1. Sisip
2. Hitung Simpul
3. Cari
4. Periksa Kosong
5. Membuat Kosong
Masukkan pilihan Anda: 1
Masukkan elemen integer yang akan disisipkan: 23

Post order : 23
Pre order : 23
In order : 23
Anda ingin melanjutkan (Ketik y atau t): y

Operasi-Operasi Pohon BST Seimbang
1. Sisip
2. Hitung Simpul
3. Cari
4. Periksa Kosong
5. Membuat Kosong
Masukkan pilihan Anda: 1
Masukkan elemen integer yang akan disisipkan: 34

Post order : 34  23
Pre order : 23  34
In order : 23  34
Anda ingin melanjutkan (Ketik y atau t): y

Operasi-Operasi Pohon BST Seimbang
1. Sisip
2. Hitung Simpul
3. Cari
4. Periksa Kosong
5. Membuat Kosong
Masukkan pilihan Anda: 1
Masukkan elemen integer yang akan disisipkan: 45

Post order : 23  45  34
Pre order : 34  23  45
In order : 23  34  45
Anda ingin melanjutkan (Ketik y atau t): y

Operasi-Operasi Pohon BST Seimbang
1. Sisip
2. Hitung Simpul
3. Cari
4. Periksa Kosong
5. Membuat Kosong
Masukkan pilihan Anda: 2
Simpul = 3

Post order : 23  45  34
Pre order : 34  23  45
In order : 23  34  45
Anda ingin melanjutkan (Ketik y atau t): y

Operasi-Operasi Pohon BST Seimbang
1. Sisip
2. Hitung Simpul
3. Cari
4. Periksa Kosong
5. Membuat Kosong
Masukkan pilihan Anda: 4
Status kosong = Pohon tidak kosong

Post order : 23  45  34
Pre order : 34  23  45
In order : 23  34  45
Anda ingin melanjutkan (Ketik y atau t): y

Operasi-Operasi Pohon BST Seimbang
1. Sisip
2. Hitung Simpul
3. Cari
4. Periksa Kosong
5. Membuat Kosong
Masukkan pilihan Anda: 3
Masukkan elemen integer yang akan dicari: 40
40 tidak ditemukan

Post order : 23  45  34
Pre order : 34  23  45
In order : 23  34  45
Anda ingin melanjutkan (Ketik y atau t): y

Operasi-Operasi Pohon BST Seimbang
1. Sisip
2. Hitung Simpul
3. Cari
4. Periksa Kosong
5. Membuat Kosong
Masukkan pilihan Anda: 3
Masukkan elemen integer yang akan dicari: 23
23 ditemukan di dalam pohon

Post order : 23  45  34
Pre order : 34  23  45
In order : 23  34  45
Anda ingin melanjutkan (Ketik y atau t):

4.       Demonstrasikanlah pohon Red-Black (RBT, Red-Black Tree) pada sebuah program C++.
Penyelesaian:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
452
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
252
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
541
542
543
544
545
546
547
547
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
//pohonRedBlack.cpp
/*
 * Program C++ untuk mengimplementasikan RBT (Red Black Tree)
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cassert>
#include <conio.h>

#define INDENT_STEP  4
using namespace std;

enum warna { RED, BLACK };

/*
 * Deklarasi PohonRB
 */
typedef struct SimpulPohonRBT
{
    enum warna warna;
    void *kunci;
    void *nilai;
    SimpulPohonRBT *kiri, *kanan, *induk;
}*simpul;

typedef struct pohonrb_t
{
    simpul akar;
}*pohonrbt;

/*
 * Deklarasi Kelas PohonRB
 */
class PohonRB
{
    public:
        typedef int (*fungsiBanding)(void* kiri, void* kanan);
        pohonrbt ciptakanPohonRBT();
        void* cariPohonRBT(pohonrbt t, void* , fungsiBanding banding);
        void sisipPohonRBT(pohonrbt t, void* , void* , fungsiBanding banding);
        void hapusPohonRBT(pohonrbt t, void* , fungsiBanding banding);
        simpul grandparent(simpul n);
        simpul sibling(simpul n);
        simpul paman(simpul n);

        void verifikasiProperti(pohonrbt t);
        void verifikasiProperti1(simpul akar);
        void verifikasiProperti2(simpul akar);
        warna warnaSimpul(simpul n);

        void verifikasiProperti4(simpul akar);
        void verifikasiProperti5(simpul akar);
        void verifikasiProperti5Helper(simpul n, int , int*);
        simpul simpulBaru(void* kunci, void* , warna , simpul , simpul);
        simpul cariSimpul(pohonrbt t, void* , fungsiBanding banding);

        void rotasiKiri(pohonrbt t, simpul n);
        void rotasiKanan(pohonrbt t, simpul n);
        void gantiSimpul(pohonrbt t, simpul nLama, simpul nBaru);

        void sisipKasus1(pohonrbt t, simpul n);
        void sisipKasus2(pohonrbt t, simpul n);
        void sisipKasus3(pohonrbt t, simpul n);
        void sisipKasus4(pohonrbt t, simpul n);
        void sisipKasus5(pohonrbt t, simpul n);

        simpul simpulMaksimum(simpul akar);
        void hapusKasus1(pohonrbt t, simpul n);
        void hapusKasus2(pohonrbt t, simpul n);
        void hapusKasus3(pohonrbt t, simpul n);
        void hapusKasus4(pohonrbt t, simpul n);
        void hapusKasus5(pohonrbt t, simpul n);
        void hapusKasus6(pohonrbt t, simpul n);
};

/*
 * Menghasilkan Grandparent dari suatu simpul
 */
simpul PohonRB::grandparent(simpul n)
{
    assert (n != NULL);
    assert (n->induk != NULL);
    assert (n->induk->induk != NULL);
    return n->induk->induk;
}

/*
 * Menghasilkan sibling dari simpul
 */
simpul PohonRB::sibling(simpul n)
{
    assert (n != NULL);
    assert (n->induk != NULL);
    if (n == n->induk->kiri)
        return n->induk->kanan;
    else
        return n->induk->kiri;
}

/*
 * Menghasilkan paman dari simpul
 */
simpul PohonRB::paman(simpul n)
{
    assert (n != NULL);
    assert (n->induk != NULL);
    assert (n->induk->induk != NULL);
    return sibling(n->induk);
}

/*
 * Memverifikasi properti dari pohon RBT
 */
void PohonRB::verifikasiProperti(pohonrbt t)
{
    verifikasiProperti1 (t->akar);
    verifikasiProperti2 (t->akar);
    verifikasiProperti4 (t->akar);
    verifikasiProperti5 (t->akar);
}

/*
 * Verifikasi Properti 1
 */
void PohonRB::verifikasiProperti1(simpul n)
{
    assert (warnaSimpul(n) == RED || warnaSimpul(n) == BLACK);
    if (n == NULL)
        return;
    verifikasiProperti1(n->kiri);
    verifikasiProperti1(n->kanan);
}

/*
 * Verifikasi Properti 2
 */
void PohonRB::verifikasiProperti2(simpul akar)
{
    assert (warnaSimpul(akar) == BLACK);
}

/*
 * Menghasilkan warna sebuah simpul
 */
warna PohonRB::warnaSimpul(simpul n)
{
    return n == NULL ? BLACK : n->warna;
}

/*
 * Verifikasi Properti 4
 */
void PohonRB::verifikasiProperti4(simpul n)
{
    if (warnaSimpul(n) == RED)
    {
        assert (warnaSimpul(n->kiri) == BLACK);
        assert (warnaSimpul(n->kanan) == BLACK);
        assert (warnaSimpul(n->induk) == BLACK);
    }

    if (n == NULL)
        return;
    verifikasiProperti4(n->kiri);
    verifikasiProperti4(n->kanan);
}

/*
 * Verifikasi Properti 5
 */
void PohonRB::verifikasiProperti5(simpul akar)
{
    int hitungBlackPath = -1;
    verifikasiProperti5Helper(akar, 0, &hitungBlackPath);
}

void PohonRB::verifikasiProperti5Helper(simpul n, int hitungBlack, int* hitungBlackPath)
{
    if (warnaSimpul(n) == BLACK)
    {
        hitungBlack++;
    }
    if (n == NULL)
    {
        if (*hitungBlackPath == -1)
        {
            *hitungBlackPath = hitungBlack;
        }
        else
        {
            assert (hitungBlack == *hitungBlackPath);
        }
        return;
    }
    verifikasiProperti5Helper(n->kiri,  hitungBlack, hitungBlackPath);
    verifikasiProperti5Helper(n->kanan, hitungBlack, hitungBlackPath);
}

/*
 * Menciptakan Pohon RBT
 */
pohonrbt PohonRB::ciptakanPohonRBT()
{
    pohonrbt t = new pohonrb_t;
    t->akar = NULL;
    verifikasiProperti(t);
    return t;
}

/*
 * Menciptakan simpul baru pada Pohon RBT
 */
simpul PohonRB::simpulBaru(void* k, void* v, warna nWarna, simpul kiri, simpul kanan)
{
    simpul hasil = new SimpulPohonRBT;
    hasil->kunci = k;
    hasil->nilai = v;
    hasil->warna = nWarna;
    hasil->kiri = kiri;
    hasil->kanan = kanan;
    if (kiri  != NULL)
        kiri->induk = hasil;
    if (kanan != NULL)
        kanan->induk = hasil;
    hasil->induk = NULL;
    return hasil;
}

/*
 * Mencari simpul
 */
simpul PohonRB::cariSimpul(pohonrbt t, void* kunci, fungsiBanding banding)
{
    simpul n = t->akar;
    while (n != NULL)
    {
        int hasilBanding = banding(kunci, n->kunci);
        if (hasilBanding == 0)
        {
            return n;
        }

        else if (hasilBanding < 0)
        {
            n = n->kiri;
        }

        else
        {
            assert(hasilBanding > 0);
            n = n->kanan;
        }
    }
    return n;
}

/*
 * Melakukan pencarian pada pohon RBT
 */
void* PohonRB::cariPohonRBT(pohonrbt t, void* kunci, fungsiBanding banding)
{
    simpul n = cariSimpul(t, kunci, banding);
    return n == NULL ? NULL : n->nilai;
}

/*
 * Merotasi kiri
 */
void PohonRB::rotasiKiri(pohonrbt t, simpul n)
{
    simpul r = n->kanan;
    gantiSimpul(t, n, r);
    n->kanan = r->kiri;
    if (r->kiri != NULL)
    {
        r->kiri->induk = n;
    }
    r->kiri = n;
    n->induk = r;
}

/*
 * Merotasi kanan
 */
void PohonRB::rotasiKanan(pohonrbt t, simpul n)
{
    simpul L = n->kiri;
    gantiSimpul(t, n, L);
    n->kiri = L->kanan;
    if (L->kanan != NULL)
    {
        L->kanan->induk = n;
    }
    L->kanan = n;
    n->induk = L;
}

/*
 * Mengganti sebuah simpul
 */
void PohonRB::gantiSimpul(pohonrbt t, simpul nLama, simpul nBaru)
{
    if (nLama->induk == NULL)
    {
        t->akar = nBaru;
    }
    else
    {
        if (nLama == nLama->induk->kiri)
            nLama->induk->kiri = nBaru;
        else
            nLama->induk->kanan = nBaru;
    }
    if (nBaru != NULL)
    {
        nBaru->induk = nLama->induk;
    }
}

/*
 * Menyisipkan simpul ke dalam PohonRBT
 */
void PohonRB::sisipPohonRBT(pohonrbt t, void* kunci, void* nilai, fungsiBanding banding)
{
    simpul simpulDisisipkan = simpulBaru(kunci, nilai, RED, NULL, NULL);
    if (t->akar == NULL)
    {
        t->akar = simpulDisisipkan;
    }
    else
    {
        simpul n = t->akar;
        while (1)
        {
            int hasilBanding = banding(kunci, n->kunci);
            if (hasilBanding == 0)
            {
                n->nilai = nilai;
                return;
            }
            else if (hasilBanding < 0)
            {
                if (n->kiri == NULL)
                {
                    n->kiri = simpulDisisipkan;
                    break;
                }
                else
                {
                    n = n->kiri;
                }
            }
            else
            {
                assert (hasilBanding > 0);
                if (n->kanan == NULL)
                {
                    n->kanan = simpulDisisipkan;
                    break;
                }
                else
                {
                    n = n->kanan;
                }
            }
        }
        simpulDisisipkan->induk = n;
    }
    sisipKasus1(t, simpulDisisipkan);
    verifikasiProperti(t);
}

/*
 * Penyisipan Kasus 1
 */
void PohonRB::sisipKasus1(pohonrbt t, simpul n)
{
    if (n->induk == NULL)
        n->warna = BLACK;
    else
        sisipKasus2(t, n);
}

/*
 * Penyisipan Kasus 2
 */
void PohonRB::sisipKasus2(pohonrbt t, simpul n)
{
    if (warnaSimpul(n->induk) == BLACK)
        return;
    else
        sisipKasus3(t, n);
}

/*
 * Penyisipan Kasus 3
 */
void PohonRB::sisipKasus3(pohonrbt t, simpul n)
{
    if (warnaSimpul(paman(n)) == RED)
    {
        n->induk->warna = BLACK;
        paman(n)->warna = BLACK;
        grandparent(n)->warna = RED;
        sisipKasus1(t, grandparent(n));
    }
    else
    {
        sisipKasus4(t, n);
    }
}

/*
 * Penyisipan Kasus 4
 */
void PohonRB::sisipKasus4(pohonrbt t, simpul n)
{
    if (n == n->induk->kanan && n->induk == grandparent(n)->kiri)
    {
        rotasiKiri(t, n->induk);
        n = n->kiri;
    }
    else if (n == n->induk->kiri && n->induk == grandparent(n)->kanan)
    {
        rotasiKanan(t, n->induk);
        n = n->kanan;
    }
    sisipKasus5(t, n);
}

/*
 * Penyisipan Kasus 5
 */
void PohonRB::sisipKasus5(pohonrbt t, simpul n)
{
    n->induk->warna = BLACK;
    grandparent(n)->warna = RED;
    if (n == n->induk->kiri && n->induk == grandparent(n)->kiri)
    {
        rotasiKanan(t, grandparent(n));
    }
    else
    {
        assert (n == n->induk->kanan && n->induk == grandparent(n)->kanan);
        rotasiKiri(t, grandparent(n));
    }
}

/*
 * Menghapus simpul dari PohonRBT
 */
void PohonRB::hapusPohonRBT(pohonrbt t, void* kunci, fungsiBanding banding)
{
    simpul anak;
    simpul n = cariSimpul(t, kunci, banding);
    if (n == NULL)
        return;
    if (n->kiri != NULL && n->kanan != NULL)
    {
        simpul pred = simpulMaksimum(n->kiri);
        n->kunci   = pred->kunci;
        n->nilai = pred->nilai;
        n = pred;
    }
    assert(n->kiri == NULL || n->kanan == NULL);
    anak = n->kanan == NULL ? n->kiri  : n->kanan;
    if (warnaSimpul(n) == BLACK)
    {
        n->warna = warnaSimpul(anak);
        hapusKasus1(t, n);
    }
    gantiSimpul(t, n, anak);
    free(n);
    verifikasiProperti(t);
}

/*
 * Menghasilkan simpul maksimum
 */
simpul PohonRB::simpulMaksimum(simpul n)
{
    assert (n != NULL);
    while (n->kanan != NULL)
    {
        n = n->kanan;
    }
    return n;
}

/*
 * Penghapusan Kasus 1
 */
void PohonRB::hapusKasus1(pohonrbt t, simpul n)
{
    if (n->induk == NULL)
        return;
    else
        hapusKasus2(t, n);
}

/*
 * Penghapusan Kasus 2
 */
void PohonRB::hapusKasus2(pohonrbt t, simpul n)
{
    if (warnaSimpul(sibling(n)) == RED)
    {
        n->induk->warna = RED;
        sibling(n)->warna = BLACK;
        if (n == n->induk->kiri)
            rotasiKiri(t, n->induk);
        else
            rotasiKanan(t, n->induk);
    }
    hapusKasus3(t, n);
}

/*
 * Penghapusan Kasus 3
 */
void PohonRB::hapusKasus3(pohonrbt t, simpul n)
{
    if (warnaSimpul(n->induk) == BLACK && warnaSimpul(sibling(n)) == BLACK &&
        warnaSimpul(sibling(n)->kiri) == BLACK && warnaSimpul(sibling(n)->kanan) == BLACK)
    {
        sibling(n)->warna = RED;
        hapusKasus1(t, n->induk);
    }
    else
        hapusKasus4(t, n);
}

/*
 * Penghapusan Kasus 4
 */
void PohonRB::hapusKasus4(pohonrbt t, simpul n)
{
    if (warnaSimpul(n->induk) == RED && warnaSimpul(sibling(n)) == BLACK &&
        warnaSimpul(sibling(n)->kiri) == BLACK &&  
        warnaSimpul(sibling(n)->kanan) == BLACK)
    {
        sibling(n)->warna = RED;
        n->induk->warna = BLACK;
    }
    else
        hapusKasus5(t, n);
}

/*
 * Penghapusan Kasus 5
 */
void PohonRB::hapusKasus5(pohonrbt t, simpul n)
{
    if (n == n->induk->kiri && warnaSimpul(sibling(n)) == BLACK &&
        warnaSimpul(sibling(n)->kiri) == RED &&
        warnaSimpul(sibling(n)->kanan) == BLACK)
    {
        sibling(n)->warna = RED;
        sibling(n)->kiri->warna = BLACK;
        rotasiKanan(t, sibling(n));
    }
    else if (n == n->induk->kanan && warnaSimpul(sibling(n)) == BLACK &&
             warnaSimpul(sibling(n)->kanan) == RED &&
             warnaSimpul(sibling(n)->kiri) == BLACK)
    {
        sibling(n)->warna = RED;
        sibling(n)->kanan->warna = BLACK;
        rotasiKiri(t, sibling(n));
    }
    hapusKasus6(t, n);
}

/*
 * Penghapusan Kasus 6
 */
void PohonRB::hapusKasus6(pohonrbt t, simpul n)
{
    sibling(n)->warna = warnaSimpul(n->induk);
    n->induk->warna = BLACK;
    if (n == n->induk->kiri)
    {
        assert (warnaSimpul(sibling(n)->kanan) == RED);
        sibling(n)->kanan->warna = BLACK;
        rotasiKiri(t, n->induk);
    }

    else
    {
        assert (warnaSimpul(sibling(n)->kiri) == RED);
        sibling(n)->kiri->warna = BLACK;
        rotasiKanan(t, n->induk);
    }
}

/*
 * Membandingkan dua simpul
 */
int IntSimpul(void* pKiri, void* pKanan)
{
    int kiri = (int)pKiri;
    int kanan = (int)pKanan;
    if (kiri < kanan)
        return -1;
    else if (kiri > kanan)
        return 1;
    else
    {
        assert (kiri == kanan);
        return 0;
    }
}
/*
 * Menampilkan Pohon RBT
 */
void tampilPohonRBT(simpul n, int indent)
{
    int i;
    if (n == NULL)
    {
        fputs("<pohon kosong>", stdout);
        return;
    }
    if (n->kanan != NULL)
    {
        tampilPohonRBT(n->kanan, indent + INDENT_STEP);
    }

    for(i = 0; i < indent; i++)
        fputs(" ", stdout);
    if (n->warna == BLACK)
        cout<<(int)n->kunci<<endl;
    else
        cout<<"<"<<(int)n->kunci<<">"<<endl;
    if (n->kiri != NULL)
    {
        tampilPohonRBT(n->kiri, indent + INDENT_STEP);
    }
}

void tampilPohon(pohonrbt t)
{
    tampilPohonRBT(t->akar, 0);
    puts("");
}

/*
 * Main
 */
int main()
{
    int i;
    PohonRB rbt;
    pohonrbt t = rbt.ciptakanPohonRBT();

    for (i = 0; i < 12; i++)
    {
        int x = rand() % 10;
        int y = rand() % 10;
        tampilPohon(t);
        cout<<"Penyisipan "<<x<<" -> "<<y<<endl<<endl;
        rbt.sisipPohonRBT(t, (void*)x, (void*)y, IntSimpul);
        assert(rbt.cariPohonRBT(t, (void*)x, IntSimpul) == (void*)y);
    }

    for (i = 0; i < 15; i++)
    {
        int x = rand() % 10;
        tampilPohon(t);
        cout<<"Penghapusan kunci "<<x<<endl<<endl;
        rbt.hapusPohonRBT(t, (void*)x, IntSimpul);
    }

    getch();
    return 0;
}

<pohon kosong>
Penyisipan 1 -> 7

1

Penyisipan 4 -> 0

    <4>
1

Penyisipan 9 -> 4
    <9>
4
    <1>

Penyisipan 8 -> 8
    9
        <8>
4
    1

Penyisipan 2 -> 4
    9
        <8>
4
        <2>
    1

Penyisipan 5 -> 5
        <9>
    8
        <5>
4
        <2>
    1

Penyisipan 1 -> 7
        <9>
    8
        <5>
4
        <2>
    1

Penyisipan 1 -> 1
        <9>
    8
        <5>
4
        <2>
    1

Penyisipan 5 -> 2
        <9>
    8
        <5>
4
        <2>
    1

Penyisipan 7 -> 6
        9
    <8>
            <7>
        5
4
        <2>
    1

Penyisipan 1 -> 4
        9
    <8>
            <7>
        5
4
        <2>
    1

Penyisipan 2 -> 3
        9
    <8>
            <7>
        5
4
        <2>
    1

Penghapusan kunci 2
        9
    <8>
            <7>
        5
4
    1

Penghapusan kunci 2
        9
    <8>
            <7>
        5
4
    1

Penghapusan kunci 1
    9
8
        7
    <5>
        4

Penghapusan kunci 6
    9
8
        7
    <5>
        4

Penghapusan kunci 8
    9
7
    5
        <4>

Penghapusan kunci 5
    <9>
7
    <4>

Penghapusan kunci 7
    <9>
4

Penghapusan kunci 6
    <9>
4

Penghapusan kunci 1
    <9>
4

Penghapusan kunci 8
    <9>
4

Penghapusan kunci 9
4

Penghapusan kunci 2
4

Penghapusan kunci 7
4

Penghapusan kunci 9
4

Penghapusan kunci 5



Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)