Tuesday, December 20, 2016

Bab 11. Java Struktur Data dan Pemrograman GUI



Bab.11 Pohon Pencarian Biner

Tujuan Instruksional
·         Mendesain dan mengimplementasikan suatu pohon pencarian biner.
·         Merepresentasikan pohon pencarian biner menggunakan struktur data berantai.
·         Mencari suatu elemen di dalam suatu pohon pencarian biner.
·         Menjelajah elemen-elemen di dalam suatu pohon pencarian biner.
·         Menghapus elemen dari suatu pohon pencarian biner.
·         Menampilkan suatu pohon biner secara grafikal.
·         Menciptakan suatu iterator untuk menjelajah suatu pohon biner.


11.1 Introduksi
Pohon merupakan suatu struktur data klasik yang memiliki banyak terapan penting. Pohon menyediakan suatu organisasi hirarkis dimana di dalamnya data disimpan di dalam simpul-simpul. Bab ini akan mengintroduksi beberapa pohon pencarian biner. Anda telah menggunakan beberapa iterator di dalam JCF. Bab ini juga akan mendemonstrasikan bagaimana mengimplementasikan iterator untuk menjelajah elemen-elemen di dalam suatu pohon biner.


11.2 Pohon Pencarian Biner
Ingat bahwa list, tumpukan, atau antrian merupakan suatu struktur linier yang memuat seruntun elemen. Pohon biner merupakan suatu struktur hirarkis. Pohon biner bisa saja kosong atau bisa juga memuat suatu elemen yang disebut dengan akar. Suatu pohon biner memuat dua pohon biner lainnya yang disebut dengan subpohon kiri dan subpohon kanan. Dua contoh pohon biner ditampilkan pada Gambr 11.1.


Gambar 11.1 Setiap simpul di dalam suatu pohon biner bisa tidak memiliki, memiliki satu, atau memiliki dua subpohon


Panjang suatu jalur merupakan jumlah tepi di dalam jalur. Kedalaman suatu simpul adalah panjang jalur dari akar ke simpul tersebut. Sekumpulan simpul pada kedalaman tertentu disebut dengan suatu level pohon. Sibling atau saudara merupakan simpul yang memiliki simpul orangtua yang sama. Akar subpohon kiri (kanan) suatu simpul disebut dengan anak kiri (kanan) simpul. Suatu simpul tanpa anak disebut dengan daun. Tinggi suatu pohon kosong adalah 0. Tinggi suatu pohon tak-kosong adalah panjang jalur dari simpul akar ke daun terjauh + 1. Perhatikan pohon pada Gambar 11.1a. Panjang jalur dari simpul 60 ke 45 adalah 2. Kedalaman simpul 60 adalah 0, kedalaman simpul 55 adalah 1, dan kedalaman simpul 45 adalah 2. Tinggi pohon tersebut adalah 3. Simpul 45 dan 57 adalah saudara. Simpul 45, 57, 67, dan 107 berada pada level yang sama.

Suatu pohon biner spesial disebut dengan pohon pencarian biner (binary search tree, BST). BST (tanpa elemen-elemen duplikat) memiliki watak bahwa untuk setiap simpul di dalam pohon, nilai sembarang simpul pada subpohon kirinya lebih kecil dari nilai simpul, dan nilai sembarang simpul pada subpohon kanannya lebih besar dari nilai simpul tersebut. Kedua pohon pada Gambar 11.1 merupakan BST. Bagian ini akan dikhususkan untuk membahas tentang BST. Anda bisa melihat visualisasi BST secara online seperti terlihat pada Gambar 11.2.



Gambar 11.2 Perangkat animasi memampukan Anda untuk menyisipkan, menghapus, dan mencari elemen secara visual


11.2.1 Merepresentasikan Pohon Pencarian Biner
Suatu pohon pencarian biner dapat direpresentasikan menggunakan sehimpunan simpul berantai. Setiap simpul memuat suatu nilai dan dua rantai kiri dan rantai kanan yang merujuk pada anak kiri dan anak kanan, seperti ditunjukkan pada Gambar 11.3.



Gambar 11.3 Suatu pohon biner dapat direpresentasikan dengan sehimpunan simpul berantai


Suatu simpul dapat didefinisikan sebagai berikut:

class TreeNode<E> {
  E elemen;
  TreeNode<E> kiri;
  TreeNode<E> kanan;
 
  public TreeNode(E e) {
    elemen = e;
  }
}

Variabel akar berkaitan dengan simpul akar dari pohon. Jika pohon kosong, maka akar adalah null. Kode berikut menciptakan tiga simpul pertama dari pohon pada Gambar 11.3.

// Menciptakan simpul akar
TreeNode<Integer> akar = new TreeNode<Integer>(new Integer(60));

// Menciptakan simpul anak kiri
akar.kiri = new TreeNode<Integer>(new Integer(55));

// Menciptakan simpul anak kanan
akar.kanan = new TreeNode<Integer>(new Integer(100));


11.2.2 Mencari Elemen
Untuk mencari suatu elemen di dalam BST, Anda memulainya dari akar dan menjelajah ke bawah sampai kecocokan ditemukan atau sampai ditemukannya subpohon kosong. Algoritma ini dideskripsikan pada kode11.1. Dimisalkan bahwa sekarang menunjuk ke akar (baris 2). Langkah-langkah berikut diulangi sampai sekarang bernilai null (baris 4) atau elemen cocok dengan sekarang.elemen (baris 12).
·         Jika elemen kurang dari sekarang.elemen, maka sekarang.kiri ditugaskan kepada sekarang (baris 6).
·         Jika elemen lebih dari sekarang.elemen, maka sekarang.kanan ditugaskan kepada sekarang (baris 9).
·         Jika elemen sama dengan sekarang.elemen, nilai balik true (baris 12).
Jika sekarang adalah null, maka subpohon kosong dan elemen tidak berada di dalam pohon (baris 14).

Kode11.1 Mencari Elemen Di Dalam BST

1   public boolean search(E elemen) {
2     TreeNode<E> sekarang = akar; // Mulai dari akar
3
4     while (sekarang != null)
5       if (elemen < sekarang.elemen) {
6         sekarang = sekarang.kiri; // Menjelajah ke kiri
7       }
8       else if (elemen > sekarang.elemen) {
9         sekarang = sekarang.kanan; // Menjelajah ke kanan
10      }
11      else // Elemen cocok dengan sekarang.elemen
12        return true; // Elemen ditemukan
13
14    return false; // Elemen tidak ada di dalam pohon
15  }



11.2.3 Menyisipkan Elemen
Untuk menyisipkan suatu elemen ke dalam BST, Anda perlu menempatkan dimana menyisipkannya di dalam pohon tersebut. Idenya adalah mengetahui lokasi simpul orangtua untuk simpul baru itu. Kode11.2 menyajikan algoritma ini.

Kode11.2 Menyisipkan Elemen Di Dalam BST

1   boolean insert(E e) {
2   if (pohon kosong)
3     // Menciptakan simpul untuk e sebagai akar;
4   else {
5     // Menentukan lokasi simpul orangtua
6     orangtua = sekarang = akar;
7     while (sekarang != null)
8       if (e < nilai di dalam sekarang.elemen) {
9         orangtua = sekarang; // Simpan orangtua
10        sekarang = sekarang.kiri; // Menjelajah ke kiri
11      }
12      else if (e > nilai di dalam sekarang.elemen) {
13        orangtua = sekarang; // Simpan orangtua
14        sekarang = sekarang.kanan; // Menjelajah ke kanan
15      }
16      else
17        return false; // Simpul duplikat, tidak disisipkan
18
19      // Menciptakan suatu simpul baru untuk e dan menempelkannya ke orangtua
20
21      return true; // Elemen disisipkan
22    }
23  }

Jika pohon kosong, maka suatu simpul akar diciptakan dengan elemen baru (baris 2-3). Sebaliknya, simpul orangtua dicari untuk menempatkan simpul elemen baru (baris 6-17). Kemudian suatu simpul baru untuk elemen diciptakan dan simpul tersebut dihubungkan dengan simpul orangtuanya. Jika elemen baru kurang dari elemen orangtua, maka simpul untuk elemen baru akan menjadi anak kiri dari orangtuanya. Jika elemen baru lebih dari elemen orangtua, maka simpul untuk elemen baru akan menjadi anak kanan dari orangtuanya.

Sebagai contoh, dalam menyisipkan 101 ke dalam pohon pada Gambar 11.4, setelah loop while pada algoritma selesai dijalankan, orangtua akan menunjuk ke simpul 107, seperti tertampil pada Gambar 11.4a. Simpul baru untuk 101 menjadi anak kiri dari orangtuanya. Dalam menyisipkan 59 ke dalam pohon BST, setelah loop while pada algoritma selesai dijalankan, orangtua akan menunjuk ke simpul 57, seperti tertampil pada Gambar 11.4b. Simpul baru untuk 59 menjadi anak kanan dari orangtuanya.



Gambar 11.4 Dua elemen baru disisipkan ke dalam pohon BST


11.2.4 Menjelajah Pohon
Penjelajahan pohon adalah proses proses pengunjungan setiap simpul di dalam pohon yang dilakukan hanya sekali. Ada beberapa cara untuk menjelajah pohon. Bagian ini akan mengenalkan penjelajahan inorder, preorder, postorder, depth-first, dan breadth-first.

Dengan penjelajahan inorder, subpohon kiri dari simpul sekarang pertama-tama dikunjungi secara rekursif, kemudian simpul sekarang, dan terakhir subpohon kanan dari simpul sekarang dikunjungi secara rekursif. Penjelajahan inorder menampilkan semua simpul di dalam BST dengan urutan menaik.

Dengan penjelajahan postorder, subpohon kiri dari simpul sekarang pertama-tama dikunjungi secara rekursif, kemudian subpohon kanan dari simpul sekarang dikunjungi secara rekursif, dan terakhir simpul sekarang itu sendiri. Aplikasi dari postorder ini adalah menemukan kapasitas direktori di dalam suatu sistem file. Seperti ditampilkan pada Gambar 11.5, setiap direktori merupakan suatu simpul internal dan file merupakan suatu simpul daun. Anda bisa menerapkan penjelajahan postorder untuk mendapatkan kapasitas setiap file dan subdirektori sebelum menemukan ukuran dari direktori akar.

Dengan penjelajahan preorder, simpul sekarang dikunjungi pertama kali, kemudian subpohon kiri dari simpul sekarang dikunjungi secara rekursif, terakhir subpohon kanan dari simpul sekarang dikunjungi secara rekursif. Penjelajahan depth-first sama dengan penjelajahan preorder. Aplikasi dari penjelajahan preorder adalah mencetak suatu dokumen terstruktur. Seperti tertampil pada Gambar 11.6, Anda bisa mencetak tabel isi di dalam suatu buku menggunakan penjelajahan preorder.

Dengan penjelajahan breadth-first, simpul-simpul dikunjungi level demi level. Pertama-tama akar dikunjungi, kemudian semua anak dari akar tersebut dari kiri ke kanan, dan kemudian cucu dari akar dari kiri ke kanan, dan seterusnya.


Gambar 11.5 Suatu direktori memuat file-file dan sub-subdirektori




Gambar 11.6 Pohon dapat digunakan untuk merepresentasikan suatu dokumen terstruktur seperti buku, bab, dan bagian


Sebagai contoh, di dalam pohon pada Gambar 11.4b, penjelajahan inorder adalah

45 55 57 59 60 67 100 101 107

Penjelajahan postorder adalah

45 59 57 55 67 101 107 100 60

Penjelajahan preorder adalah
60 55 45 57 59 100 67 107 101

Penjelajahan breadth-first adalah

60 55 100 45 57 67 107 59 101




Gambar 11.7 Antarmuka Tree mendefinisikan beberapa operasi umum untuk pohon, dan kelas AbstractTree secara parsial mengimplementasikan Tree



11.2.5 Kelas BinaryTree
Dengan mengikuti pola perancangan JCF API, berikut digunakan suatu antarmuka yang dinamai Tree untuk mendefinisikan beberapa operasi umum untuk pohon dan menyediakan suatu kelas abstrak yang dinamai AbstractTree yang secara parsial mengimplementasikan Tree, seperti ditampilkan pada Gambar 11.7. Kelas konkrit BinaryTree dapat didefinisikan untuk mewarisi AbstractTree, seperti tertampil pada Gambar 11.8.

Kode11.3, kode11.4, dan kode11.5 menyajikan implementasi Tree, AbstractTree, dan BinaryTree.


Gambar 11.8 Kelas BinaryTree mendefinisikan suatu BST konkrit


Kode11.3 Tree.java

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
public interface Tree<E extends Comparable<E>> {
  /** Mengembalikan true jika elemen berada di dalam pohon */
  public boolean search(E e);

  /** Menyisipkan elemen e ke dalam BST
    * Mengembalikan true jika elemen disisipkan dengan sukses */
  public boolean insert(E e);

  /** Menghapus elemen tertentu dari pohon
    * Mengembalikan true jika elemen dihapus dengan sukses */
  public boolean delete(E e);

  /** Penjelajahan inorder dari akar*/
  public void inorder();

  /** Penjelajahan postorder dari akar */
  public void postorder();

  /** Penjelajahan preorder dari akar */
  public void preorder();

  /** Mendapatkan jumlah simpul di dalam pohon */
  public int getSize();

  /** Mengembalikan true jika pohon kosong */
  public boolean isEmpty();

  /** Mengembalikan suatu iterator untuk menjelajahi elemen-elemen di dalam pohon */
  public java.util.Iterator iterator();
}

Kode11.4 AbstractTree.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public abstract class AbstractTree<E extends Comparable<E>>
     implements Tree<E> {
  /** Penjelajahan inorder dari akar */
  public void inorder() {
  }

  /** Penjelajahan postorder dari akar */
  public void postorder() {
  }

  /** Penjelajahan preorder dari akar */
  public void preorder() {
  }

  /** Mengembalikan true jika pohon kosong */
  public boolean isEmpty() {
    return getSize() == 0;
  }

  /** Mengembalikan suatu iterator untuk menjelajahi elemen-elemen di dalam pohon */
  public java.util.Iterator iterator() {
    return null;
  }
}

Kode11.5 BinaryTree.java

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
public class BinaryTree<E extends Comparable<E>>
    extends AbstractTree<E> {
  protected TreeNode<E> akar;
  protected int size = 0;

  /** Menciptakan suatu pohon biner default */
  public BinaryTree() {
  }

  /** Menciptakan suatu pohon pencarian biner dari array objek */
  public BinaryTree(E[] objek) {
    for (int i = 0; i < objek.length; i++)
      insert(objek[i]);
  }

  /** Mengembalikan true jika elemen berada di dalam pohon */
  public boolean search(E e) {
    TreeNode<E> sekarang = akar; // Memulai dari akar

    while (sekarang != null) {
      if (e.compareTo(sekarang.elemen) < 0) {
        sekarang = sekarang.kiri;
      }
      else if (e.compareTo(sekarang.elemen) > 0) {
        sekarang = sekarang.kanan;
      }
      else // elemen cocok dengan sekarang.elemen
        return true; // Elemen ditemukan
    }

    return false;
  }

  /** Menyisipkan elemen e ke BST
    * Mengembalikan true jika elemen disisipkan dengan sukses */
  public boolean insert(E e) {
    if (akar == null)
      akar = createNewNode(e); // Menciptakan suatu akar baru
    else {
      // Mencari lokasi simpul orangtua
      TreeNode<E> orangtua = null;
      TreeNode<E> sekarang = akar;
      while (sekarang != null)
        if (e.compareTo(sekarang.elemen) < 0) {
          orangtua = sekarang;
          sekarang = sekarang.kiri;
        }
        else if (e.compareTo(sekarang.elemen) > 0) {
          orangtua = sekarang;
          sekarang = sekarang.kanan;
        }
        else
          return false; // Simpul duplikat tidak disisipkan

      // Menciptakan suatu simpul baru dan menempelkannya ke simpul orangtua
      if (e.compareTo(orangtua.elemen) < 0)
        orangtua.kiri = createNewNode(e);
      else
        orangtua.kanan = createNewNode(e);
    }

    size++;
    return true; // Elemen disisipkan
  }

  protected TreeNode<E> createNewNode(E e) {
    return new TreeNode<E>(e);
 }

  /** Penjelajahan inorder dari akar */
  public void inorder() {
    inorder(akar);
  }

  /** Penjelajahan inorder dari suatu subpohon */
  protected void inorder(TreeNode<E> akar) {
    if (akar == null) return;
    inorder(akar.kiri);
    System.out.print(akar.elemen + " ");
    inorder(akar.kanan);
  }

  /** Penjelajahan postorder dari akar */
  public void postorder() {
    postorder(akar);
  }

  /** Penjelajahan postorder dari suatu subpohon */
  protected void postorder(TreeNode<E> akar) {
    if (akar == null) return;
    postorder(akar.kiri);
    postorder(akar.kanan);
    System.out.print(akar.elemen + " ");
  }

  /** Penjelajahan preorder dari akar */
  public void preorder() {
    preorder(akar);
  }

  /** Penjelajahan preorder dari suatu subpohon */
  protected void preorder(TreeNode<E> akar) {
    if (akar == null) return;
    System.out.print(akar.elemen + " ");
    preorder(akar.kiri);
    preorder(akar.kanan);
  }

  /** Kelas inner simpul pohon */
  public static class TreeNode<E extends Comparable<E>> {
    E elemen;
    TreeNode<E> kiri;
    TreeNode<E> kanan;

    public TreeNode(E e) {
      elemen = e;
    }
  }

  /** Mendapatkan jumlah simpul di dalam pohon */
  public int getSize() {
    return size;
  }

  /** Mengembalikan akar pohon */
  public TreeNode getRoot() {
    return akar;
  }

  /** Mengembalikan suatu jalur dari akar sampai elemen tertentu */
  public java.util.ArrayList<TreeNode<E>> path(E e) {
    java.util.ArrayList<TreeNode<E>> list =
      new java.util.ArrayList<TreeNode<E>>();
    TreeNode<E> sekarang = akar; // Mulai dari akar

    while (sekarang != null) {
      list.add(sekarang); // Menambah simpul ke dalam list
      if (e.compareTo(sekarang.elemen) < 0) {
        sekarang = sekarang.kiri;
      }
      else if (e.compareTo(sekarang.elemen) > 0) {
        sekarang = sekarang.kanan;
      }
      else
        break;
    }

    return list; // Mengembalikan suatu array simpul
  }

  /** Menghapus suatu elemen dari pohon pencarian biner.
    * Mengembalikan true jika elemen dihapus dengan sukses
    * Mengembalikan false jika elemen tidak berada di dalam pohon */
  public boolean delete(E e) {
    // Mencari lokasi simpul yang akan dihapus dan juga mencari simpul orangtuanya
    TreeNode<E> orangtua = null;
    TreeNode<E> sekarang = akar;
    while (sekarang != null) {
      if (e.compareTo(sekarang.elemen) < 0) {
        orangtua = sekarang;
        sekarang = sekarang.kiri;
      }
      else if (e.compareTo(sekarang.elemen) > 0) {
        orangtua = sekarang;
        sekarang = sekarang.kanan;
      }
      else
        break; // Elemen berada di dalam pohon ditunjuk oleh sekarang
    }

    if (sekarang == null)
      return false; // Elemen tidak berada di dalam pohon

    // Kasus 1: sekarang tidak memiliki anak kiri
    if (sekarang.kiri == null) {
      // Menghubungkan orangtua dengan anak kanan dari simpul sekarang
      if (orangtua == null) {
        akar = sekarang.kanan;
      }
      else {
        if (e.compareTo(orangtua.elemen) < 0)
          orangtua.kiri = sekarang.kanan;
        else
          orangtua.kanan = sekarang.kanan;
        }
      }
    else {
      // Kasus 2: Simpul sekarang memiliki suatu anak kiri
      // Menempatkan simpul palingKanan di dalam subpohon kiri dari
      // simpul sekarang dan juga orangtuanya
      TreeNode<E> orangtuaPalingKanan = sekarang;
      TreeNode<E> palingKanan = sekarang.kiri;

      while (palingKanan.kanan != null) {
        orangtuaPalingKanan = palingKanan;
        palingKanan = palingKanan.kanan; // Terus ke kanan
      }

      // Mengganti elemen di dalam sekarang dengan elemen di dalam palingKanan
      sekarang.elemen = palingKanan.elemen;

      // Menghapus simpul paling kanan
      if (orangtuaPalingKanan.kanan == palingKanan)
        orangtuaPalingKanan.kanan = palingKanan.kiri;
      else
        // Kasus spesial: orangtuaPalingKanan == sekarang
        orangtuaPalingKanan.kiri = palingKanan.kiri;
    }

    size--;
    return true; // Elemen disisipkan
  }

  /** Mendapatkan suatu iterator. Menggunakan inorder. */
  public java.util.Iterator iterator() {
    return inorderIterator();
  }

  /** Mendapatkan iterator inorder */
  public java.util.Iterator inorderIterator() {
    return new InorderIterator();
  }

  // Kelas inner InorderIterator
  class InorderIterator implements java.util.Iterator {
    // Menyimpan elemen di dalam suatu list
    private java.util.ArrayList<E> list =
        new java.util.ArrayList<E>();
    private int sekarang = 0; // Menunjuk ke elemen sekarang di dalam list

    public InorderIterator() {
      inorder(); // Menjelajah pohon biner dan menyimpan elemen di dalam list
    }

    /** Penjelajahan inorder dari akar*/
    private void inorder() {
      inorder(akar);
    }

    /** Penjelajahan inorder dari suatu subpohon */
    private void inorder(TreeNode<E> akar) {
      if (akar == null) return;
      inorder(akar.kiri);
      list.add(akar.elemen);
      inorder(akar.kanan);
    }

    /** Elemen berikutnya untuk dijelajah */
    public boolean hasNext() {
      if (sekarang < list.size())
        return true;

      return false;
    }

    /** Mendapatkan elemen sekarang dan menggeser kursor ke simpul berikutnya */
    public Object next() {
      return list.get(sekarang++);
    }

    /** Menghapus elemen sekarang dan merefresh list */
    public void remove() {
      delete(list.get(sekarang)); // Menghapus elemen sekarang
      list.clear(); // Membersihkan list
      inorder(); // Membangung-ulang list
    }
  }

  /** Menghapus semua elemen dari pohon */
  public void clear() {
    akar = null;
    size = 0;
  }
}

Metode insert(E e) pada baris 36-64 menciptakan suatu simpul untuk elemen e dan menyisipkannya ke dalam pohon. Jika pohon kosong, maka simpul tersebut menjadi akar. Sebaliknya, metode ini akan mencari suatu orangtua yang sesuai. Jika elemen telah ada di dalam pohon, maka metode akan memberikan nilai balik false; sebaliknya memberikan true.

Metode inorder() pada baris 71-81 memanggil metode inorder(akar) untuk menjelajah seluruh pohon. Metode inorder(TreeNode akar) menjelajah pohon dengan akar tertentu. Metode ini adalah metode rekursif, karena secara rekursif menjelajah subpohon kiri, kemudian akhir, dan terakhir subpohon kanan. Penjelajahan berakhir ketika pohon kosong.

Metode postorder() pada baris 84-94 dan metode preorder() pada baris 97-107 diimplementasikan serupa dengan rekursi.

Metode path(E e) pada baris 131-149 mengembalikan atau menjadikan sebagai nilai balik suatu jalur simpul di dalam suatu list array. Sebagai contoh, pada Gambar 11.4a, path(45) memuat simpul-simpul untuk elemen-elemen 60, 55, dan 45, dan path(58) memuat simpul-simpul untuk elemen-elemen 60, 55, dan 57.

Implementasi dari delete() dan iterator() pada baris 151-267 akan didiskusikan selanjutnya.

Kode11.6 menyajikan suatu contoh yang menciptakan suatu pohon pencarian biner menggunakan BinaryTree (baris 4). Program menambahkan beberapa string ke dalam pohon (baris 5-11), menjelajah pohon dengan inorder, postorder, dan preorder (baris 14-20), mencari suatu elemen (baris 24), dan mendapatkan suatu jalur dari simpul yang memuat Aurora sampai ke akar (baris 28-31).

Kode11.6 UjiPohonBiner.java

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
public class UjiPohonBiner {
  public static void main(String[] args) {
    // Menciptakan suatu pohon biner
    BinaryTree<String> pohon = new BinaryTree<String>();
    pohon.insert("Gaby");
    pohon.insert("Marolop");
    pohon.insert("Taruli");
    pohon.insert("Adam");
    pohon.insert("Joni");
    pohon.insert("Poltak");
    pohon.insert("Dani");

    // Menjelajah pohon
    System.out.print("Inorder (terurut): ");
    pohon.inorder();
    System.out.print("\nPostorder: ");
    pohon.postorder();
    System.out.print("\nPreorder: ");
    pohon.preorder();
    System.out.print("\nJumlah simpul " + pohon.getSize());

    // Mencari suatu elemen
    System.out.print("\nApakah Poltak di dalam pohon? " +
      pohon.search("Poltak"));

    // Mendapatkan suatu jalur dari akar ke Poltak
    System.out.print("\nSuatu jalur dari akar ke Aurora adalah: ");
    java.util.ArrayList<BinaryTree.TreeNode<String>> jalur
        = pohon.path("Poltak");
    for (int i = 0; jalur != null && i < jalur.size(); i++)
      System.out.print(jalur.get(i).elemen + " ");

    Integer[] angka = {2, 4, 3, 1, 8, 5, 6, 7};
    BinaryTree<Integer> pohonInt = new BinaryTree<Integer>(angka);
    System.out.print("\nInorder (terurut): ");
    pohonInt.inorder();
  }
}

Keluaran

Inorder (terurut): Adam Dani Gaby Joni Marolop Poltak Taruli
Postorder: Dani Adam Joni Poltak Taruli Marolop Gaby
Preorder: Gaby Adam Dani Marolop Joni Taruli Poltak
Jumlah simpul 7
Apakah Poltak di dalam pohon? true
Suatu jalur dari akar ke Poltak adalah: Gaby Marolop Taruli Poltak
Inorder (terurut): 1 2 3 4 5 6 7 8

Program memeriksa apakah jalur != null pada baris 30 untuk memastikan bahwa jalur tidak null sebelum memanggil path.get(i). Hal ini merupakan contoh pemrograman defensif untuk menghindari error runtime yang potensial.

Program menciptakan suatu pohon lain untuk menyimpan nilai-nilai int (baris 34). Setelah semua elemen disisipkan ke dalam pohon, pohon akan tampak seperti pada Gambar 11.9.



Gambar 11.9 BST digambarkan setelah diciptakan


11.3 Menghapus Elemen di Dalam BST
Metode insert(elemen) disajikan pada 11.2.3. Seringkali, Anda perlu menghapus suatu elemen dari pohon pencarian biner. Melakukannya jauh lebih kompleks daripada menambah suatu elemen ke pohon tersebut.

Untuk menghapus suatu elemen dari pohon pencarian biner, Anda pertama-tama perlu mencar lokasi simpul yang memuat elemen tersebut dan juga simpul orangtuanya. Dimisalkan sekarang menunjuk ke simpul yang memuat elemen yang akan dihapus di dalam pohon pencarian biner dan orangtua menunjuk ke orangtua dari simpul sekarang. Simpul sekarang bisa jadi suatu anak kiri atau anak kanan dari simpul orangtua. Ada dua kasus yang perlu dipertimbangkan:

Kasus 1: Simpul sekarang tidak memiliki suatu anak kiri, seperti ditampilkan pada Gambar 11.10a. Yang perlu dilakukan hanyalah menghubungkan orangtua dengan anak kanan dari simpul sekarang, seperti tertampil pada Gambar 11.10b. Sebagai contoh, menghapus simpul 10 pada Gambar 11.11a. Orangtua dari simpul 10 dihubungkan dengan anak kanan dari simpul 10, seperti tertampil pada Gambar 11.11b.


Gambar 11.10 Kasus 1: Simpul sekarang tidak memiliki anak kiri


Gambar 11.11 Kasus 1: Menghapus simpul 10 dari (a) menghasilkan (b)


Kasus 2: Simpul sekarang memiliki suatu anak kiri. Dimisalkan bahwa palingKiri menunjuk ke simpul yang memuat elemen terbesar di dalam subpohon kiri dari simpul sekarang dan orangtuaPalingKanan menunjuk ke simpul orangtua dari simpul palingKanan, seperti tertampil pada Gambar 11.12a. Perhatikan bahwa simpul palingKanan tidak bisa memiliki suatu anak kanan tetapi masih mungkin memiliki anak kiri. Pada kasus ini, nilai elemen di dalam simpul sekarang diganti dengan nilai elemen di dalam simpul palingKanan, simpul orangtuaPalingKanan dihubungkan dengan anak kiri dari simpul palingKanan, dan terakhir simpul palingKanan dihapus, seperti tertampil pada Gambar 11.12b.


Gambar 11.12 Kasus 2: Simpul sekarang memiliki anak kiri


Gambar 11.13 Kasus 2: Menghapus 20 dari (a) menghasilkan (b)


Sebagai contoh, pertimbangkan penghapusan simpul 20 pada Gambar 11.13a. Simpul palingKanan memiliki nilai elemen 16. Nilai elemen 20 diganti dengan 16 di dalam simpul sekarang dan menjadikan simpul 10 sebagai orangtua untuk simpul 14, seperti ditunjukkan pada Gambar 11.13b.

Algoritma untuk menghapus suatu elemen dari suatu pohon pencarian biner dapat dideskripsikan pada kode11.7.

Kode11.7 Menghapus Suatu Elemen Dari BST

1   boolean delete(E e) {
2     Mencari lokasi elemen e di dalam pohon;
3     if elemen e tidak ditemukan
4       return true;
5
6     Dimisalkan sekarang adalah simpul yang memuat e dan and parent be
7       orangtua sebagai orangtua dari sekarang;
8
9     if (sekarang tidak memiliki anak kiri) // Kasus 1
10      Hubungkan anak kanan dari
11        sekarang dengan orangtua; sekarang tidak lagi direferensi, jadi
12      dihapus;
13    else // Kasus 2
14    Mencari lokasi simpul paling kanan di dalam subpohon kiri dari sekarang.
15    Menyalin nilai elemen di simpul paling kanan ke sekarang.
16    Menghubungkan orangtua dari simpul paling kanan ke anak kiri dari
17      simpul paling kanan;
18
19    return true; // Elemen dihapus
20 }

Implementasi utuh dari metode delete diberikan pada baris 154-212 pada kode11.5. Metode ini mencari lokasi simpul (dinamai sekarang) yang akan dihapus dan mencari lokasi orangtuanya (dinamai orangtua) pada baris 158-169. Jika sekarang bernilai null, maka elemen yang dicari tidak berada di dalam pohon. Jadi, metode akan memberikan nilai balik false (baris 172). Perhatikan bahwa jika sekarang adalah akar, maka orangtua adalah null. Jika pohon kosong, maka keduanya orangtua maupun sekarang adalah null.

Kasus 1 dari algoritma ini dirangkum pada baris 175-186. Pada kasus ini, simpul sekarang tidak memiliki anak kiri (yaitu, sekarang.kiri == null). Jika orangtua adalah null, maka sekarang.kanan ditugaskan kepada akar (baris 177-179). Sebaliknya, sekarang.kanan ditugaskan kepada orangtua.kiri atau orangtua.kanan tergantung dari apakah sekarang adalah anak kiri atau anak kanan dari orangtua (baris 181-184).

Kasus 2 dari algoritma ini dirangkum pada baris 187-208. Pada kasus ini, simpul sekarang memiliki anak kiri. Algoritma kemudian mencari lokasi simpul paling kanan (dinamai palingKanan) di dalam subpohon kiri dari simpul sekarang dan juga orangtuanya (dinamai orangtuaPalingKanan) (baris 194-197). Elemen di dalam sekarang diganti dengan elemen di dalam palingKanan (baris 200); palingKanan.kiri ditugaskan kepada orangtuaPalingKanan.kanan atau orangtuaPalingKanan.kiri (baris 203-207) tergantung dari apakah palingKanan adalah anak kanan atau anak kiri dari orangtuaPalingKanan.

Kode11.8 menyajikan suatu program uji yang menghapus elemen-elemen dari pohon pencarian biner.

Kode11.8 UjiHapusPohonBiner.java

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
public class UjiHapusPohonBiner {
  public static void main(String[] args) {
    BinaryTree<String> pohon = new BinaryTree<String>();
    pohon.insert("Gaby");
    pohon.insert("Marolop");
    pohon.insert("Taruli");
    pohon.insert("Adam");
    pohon.insert("Joni");
    pohon.insert("Poltak");
    pohon.insert("Dani");
    printTree(pohon);

    System.out.println("\nSetelah menghapus Gaby:");
    pohon.delete("Gaby");
    printTree(pohon);

    System.out.println("\nSetelah menghapus Adam:");
    pohon.delete("Adam");
    printTree(pohon);

    System.out.println("\nSetelah menghapus Marolop:");
    pohon.delete("Marolop");
    printTree(pohon);
  }

  public static void printTree(BinaryTree pohon) {
    // Menjelajah pohon
    System.out.print("Inorder (terurut): ");
    pohon.inorder();
    System.out.print("\nPostorder: ");
    pohon.postorder();
    System.out.print("\nPreorder: ");
    pohon.preorder();
    System.out.print("\nJumlah simpul adalah " + pohon.getSize());
    System.out.println();
  }
}

Keluaran

Inorder (terurut): Adam Dani Gaby Joni Marolop Poltak Taruli
Postorder: Dani Adam Joni Poltak Taruli Marolop Gaby
Preorder: Gaby Adam Dani Marolop Joni Taruli Poltak
Jumlah simpul adalah 7

Setelah menghapus Gaby:
Inorder (terurut): Adam Dani Joni Marolop Poltak Taruli
Postorder: Adam Joni Poltak Taruli Marolop Dani
Preorder: Dani Adam Marolop Joni Taruli Poltak
Jumlah simpul adalah 6

Setelah menghapus Adam:
Inorder (terurut): Dani Joni Marolop Poltak Taruli
Postorder: Joni Poltak Taruli Marolop Dani
Preorder: Dani Marolop Joni Taruli Poltak
Jumlah simpul adalah 5

Setelah menghapus Marolop:
Inorder (terurut): Dani Joni Poltak Taruli
Postorder: Poltak Taruli Joni Dani
Preorder: Dani Joni Taruli Poltak
Jumlah simpul adalah 4

Gambar 11.14 sampai Gambar 11.16 menunjukkan bagaimana pohon berevolusi akibat penghapusan elemen-elemen.


Gambar 11.14 Penghapusan Gaby termasuk Kasus 2


Gambar 11.15 Penghapusan Adam termasuk Kasus 1




Gambar 11.16 Penghapusan Marolop termasuk Kasus 2



11.4 Visualisasi Pohon
Bagaimana Anda menampilkan pohon biner secara visual? Anda dapat menampilkan akar, kemudian dua subpohon secara rekursif. Teknik untuk menampilkan segitiga Sierpinski dapat dipakai untuk menampilkan suatu pohon biner. Agar lebih sederhana, diasumsikan bahwa kunci adalah integer positif kurang dari 100. Kode11.9 dan kode11.10 menyajikan program, dan Gambar 11.17 menunjukkan dua contoh keluaran program.



Gambar 11.17 Suatu pohon biner ditampilkan secara grafikal



Kode11.9 TampilPohonBiner.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.awt.*;
import javax.swing.*;

public class TampilPohonBiner extends JFrame {
  public TampilPohonBiner() {
    add(new KendaliPohon(new BinaryTree<Integer>()));
  }

  public static void main(String[] args) {
    KendaliPohon frame = new KendaliPohon(new BinaryTree<Integer>());
    frame.setTitle("TampilPohonBiner");
    frame.setSize(300, 350);
    frame.setLocationRelativeTo(null); // Pusat frame
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.setVisible(true);
  }
}

Kode11.10 KendaliPohon.java

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
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class KendaliPohon extends JFrame {
  private BinaryTree<Integer> pohon; // Suatu pohon biner ditampilkan
  private JTextField jtfKunci = new JTextField(5);
  private TampilPohon view = new TampilPohon();
  private JButton jbtSisip = new JButton("Sisip");
  private JButton jbtHapus = new JButton("Hapus");

  /** Menciptakan suatu view untuk pohon biner */
  public KendaliPohon(BinaryTree<Integer> pohon) {
    this.pohon = pohon; // Menetapkan pohon biner untuk ditampilkan
    setUI();
  }

  /** Menginisialiasai UI untuk pohon biner */
  private void setUI() {
    this.setLayout(new BorderLayout());
    add(view, BorderLayout.CENTER);
    JPanel panel = new JPanel();
    panel.add(new JLabel("Masukkan suatu kunci: "));
    panel.add(jtfKunci);
    panel.add(jbtSisip);
    panel.add(jbtHapus);
    add(panel, BorderLayout.SOUTH);

    // Listener untuk tombol Sisip
    jbtSisip.addActionListener(new ActionListener() {
      public void actionPerformed(ActionEvent e) {
        int kunci = Integer.parseInt(jtfKunci.getText());
        if (pohon.search(kunci)) { // kunci sudah ada di dalam pohon
          JOptionPane.showMessageDialog(null,
            kunci + " sudah ada di dalam pohon");
        }
        else {
          pohon.insert(kunci); // Sisipkan suatu kunci
          view.repaint(); // Menampilkan kembali pohon
        }
      }
    });

    // Listener untuk tombol Hapus
    jbtHapus.addActionListener(new ActionListener() {
      public void actionPerformed(ActionEvent e) {
        int kunci = Integer.parseInt(jtfKunci.getText());
        if (!pohon.search(kunci)) { // kunci tidak ada di dalam pohon
          JOptionPane.showMessageDialog(null,
            kunci + " tidak ada di dalam pohon");
        }
        else {
          pohon.delete(kunci); // Hapus kunci
          view.repaint(); // Menampilkan-ulang pohon
        }
      }
    });
  }

  // Kelas inner TampilPohon untuk menampilkan suatu pohon pada panel
  class TampilPohon extends JPanel {
    private int radius = 20; // radius simpul pohon
    private int vGap = 50; // Jarak antara dua level di dalam suatu pohon

    protected void paintComponent(Graphics g) {
      super.paintComponent(g);

      if (pohon.getRoot() != null) {
        // Menampilkan pohon secara rekursif
        tampilPohon(g, pohon.getRoot(), getWidth() / 2, 30,
        getWidth() / 4);
      }
    }

    /** Menampilkan suatu subpohon yang berakar pada posisi (x, y) */
    private void tampilPohon(Graphics g, BinaryTree.TreeNode akar,
        int x, int y, int hGap) {
      // Menampilkan akar
      g.drawOval(x - radius, y - radius, 2 * radius, 2 * radius);
      g.drawString(akar.elemen + "", x - 6, y + 4);

      if (akar.kiri != null) {
        // Menggambar suatu garis ke simpul kiri
        hubungAnakKiri(g, x - hGap, y + vGap, x, y);
        // Menggambar subpohon kiri secara rekursif
        tampilPohon(g, akar.kiri, x - hGap, y + vGap, hGap / 2);
      }

      if (akar.kanan != null) {
        // Menggambar suatu garis ke simpul kanan
        hubungAnakKanan(g, x + hGap, y + vGap, x, y);
        // Menggambar subpohon kanan secara rekursif
        tampilPohon(g, akar.kanan, x + hGap, y + vGap, hGap / 2);
      }
    }

    /** Menghubungkan suatu orangtua pada (x2, y2) dengan
      * anak kirinya pada (x1, y1) */
    private void hubungAnakKiri(Graphics g,
        int x1, int y1, int x2, int y2) {
      double d = Math.sqrt(vGap * vGap + (x2 - x1) * (x2 - x1));
      int x11 = (int)(x1 + radius * (x2 - x1) / d);
      int y11 = (int)(y1 - radius * vGap / d);
      int x21 = (int)(x2 - radius * (x2 - x1) / d);
      int y21 = (int)(y2 + radius * vGap / d);
      g.drawLine(x11, y11, x21, y21);
    }

    /** Menghubungkan suatu orangtua pada (x2, y2) dengan
    * anak kanannya pada (x1, y1) */
    private void hubungAnakKanan(Graphics g,
        int x1, int y1, int x2, int y2) {
      double d = Math.sqrt(vGap * vGap + (x2 - x1) * (x2 - x1));
      int x11 = (int)(x1 - radius * (x1 - x2) / d);
      int y11 = (int)(y1 - radius * vGap / d);
      int x21 = (int)(x2 + radius * (x1 - x2) / d);
      int y21 = (int)(y2 + radius * vGap / d);
      g.drawLine(x11, y11, x21, y21);
    }
  }
}

Setelah suatu kunci disisipkan ke dalam pohon (baris 38), pohon digambar-ulang (baris 39) untuk merefleksikan perubahan yang terjadi. Setelah suatu kunci dihapus (baris 53), pohon juga digambar-ulang (baris 54) untuk merefleksikan perubahan yang terjadi.

Simpul ditampilkan sebagai suatu lingkaran dengan radius 20 (baris 62). Jarak antar dua level di dalam pohon didefinisikan vGap 50 (baris 63). hGap (baris 77) mendefinisikan jarak antar dua simpul secara horisontal. Nilai tersebut tereduksi setengahnya (hGap/2) pada level berikutnya ketika metode tampilPohon dipanggil secara rekursif (baris 86, 93). Perhatikan bahwa vGap tidak berubah.

Pemanggilan hubungAnakKiri menghubungkan suatu orangtua dengan anak kirinya. Anda perlu mencari dua titik ujung (x11, y11) dan (x21, y21) untuk menghubungkan dua simpul, seperti ditampilkan pada Gambar 11.18. Kalkulasi matematik untuk mencari dua titik ujung tersebut diilustrasikan pada Gambar 11.18. Perhatikan bahwa




Pemanggilan hubungAnakKanan menghubungkan suatu orangtua dengan anak kanannya. Kalkulasinya sama dengan kasus hubungAnakKiri.


Gambar 11.18 Anda perlu mencari posisi dua titik ujung untuk menghubungkan dua simpul


11.5 Iterator
Metode-metode inorder(), preorder(), dan postorder() menampilkan elemen-elemen di dalam suatu pohon dengan penjelajahan inorder, preorder, dan postorder. Metode-metode ini terbatas hanya untuk menampilkan elemen-elemen di dalam suatu pohon. Jika Anda menginginkan untuk memproses elemen-elemen di dalam suatu pohon biner (bukan untuk menampilkannnya), metode-metode tersebut tidak bisa digunakan.


Gambar 11.19 Antarmuka Iterator mendefinisikan suatu cara seragam untuk menjelajahi elemen-elemen di dalam suatu kontainer



Pendekatan yang bisa dilakukan adalah menyediakan suatu iterator. Iterator merupakan suatu objek yang menyediakan suatu cara seragam dalam menjelajah elemen-elemen di dalam suatu kontainer, seperti list, set, ataupun pohon biner.

JAVA menyediakan antarmuka java.util.Iterator (lihat Gambar 11.19), yang mendefinisikan beberapa fitur umum dari iterator. Semua kontainer (set, list, dan map) di dalam JCF mendukung keberadaan iterator.

Agar iterator dapat digunakan di dalam sejumlah aplikasi, Anda harus mendefinisikan kelas iterator sebagai suatu subtipe dari java.util.Iterator. Anda bisa menjelajah suatu pohon biner secara inorder, preorder, maupun postorder. Jadi, Anda bisa mendefinisikan tiga kelas iterator, yang dinamai InorderIterator, PreorderIterator, dan PostorderIterator. Karena ketiga kelas ini bergantung pada kelas BinaryTree, maka sangat cocok untuk menempatkan ketiganya sebagai kelas-kelas inner di dalam BinaryTree. Dan adalah hal perlu untuk menambahkan tiga metode yang dinamai inorderIterator(),preorderIterator(), dan postorderIterator() untuk mengembalikan objek-objek iterator.

Implementasi dari inorderIterator() diberikan pada kode11.5. Implementasi dari preorderIterator() dan postorderIterator() ditinggalkan sebagai latihan bagi pembaca.

Konstruktor InorderIterator memanggil metode inorder. Metode inorder(akar) pada baris 241-246 menyimpan semua elemen dari pohon ke dalam list. Elemen-elemen dijelajahi dengan gaya inorder.

Begitu suatu objek Iterator diciptakan, Nilai sekarang diinisialisasi dengan 0 (baris 229), yang menunjuk ke elemen pertama di dalam list. Pemanggilan metode next() akan mengembalikan elemen sekarang dan memindahkan sekarang untuk menunjuk ke elemen berikutnya di dalam list (baris 258).

Metode hasNext() memeriksa apakah sekarang masih berada di dalam rentang list (baris 250).

Metode remove() menghapus elemen sekarang dari pohon (baris 263). Setelah itu, suatu list baru diciptakan (baris 264-265). Perhatikan bahwa sekarang tidak perlu diubah.

Kode11.11 memberikan suatu program uji yang menyimpan beberapa string di dalam suatu BST dan menampilkan semua string dalam huruf besar.

Kode11.11 UjiPohonBinerDenganIterator.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class UjiPohonBinerDenganIterator {
  public static void main(String[] args) {
    BinaryTree<String> pohon = new BinaryTree<String>();
    pohon.insert("Gaby");
    pohon.insert("Marolop");
    pohon.insert("Taruli");
    pohon.insert("Adam");
    pohon.insert("Joni");
    pohon.insert("Poltak");
    pohon.insert("Dani");

    java.util.Iterator iterator = pohon.inorderIterator();
    while(iterator.hasNext()) {
      System.out.println(((String)(iterator.next())).toUpperCase());
    }
  }
}

Keluaran

ADAM
DANI
GABY
JONI
MAROLOP
POLTAK
TARULI





Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)