Ø APA ITU BST?
Jika kita ingin mengurutkan suatu data, maka kita harus memikirkan cara yang efektif agar permasalahan yang kita hadapi cepat selesai. Salah satu caranya dengan menggunakan metode “Binary Search Trees”. Ini merupakan suatu cara pengurutan data dengan membagi data menjadi dua dan mencari titik tengan sebagai patokannya.
Misal kita ingin mengurutkan suatu data tentang ketinggian sekelompok orang. Jika secara konvensional akan menghabiskan waktu yang lama, maka digunakanlah metode ini. Cara pengurutannya terserah kita mau dari pendek ke tinggi maupun sebaliknya. Pertama kita kumpulkan daftar ketinggian dari sekelompok orang. Lalu pilih titik tengah sebagai acuan(missal dengan ketinggian 5 kaki, 6 inchi). Kita bandingkan tinggi acuan dengan tinggi orang pertama. Misal kita menggunakan pengurutan dari pendek ke tinggi. Jika lebih tinggi dari acuan maka akan bergeser ke kanan, jika lebih pendek akan bergeser ke kiri acuan.
Ø MENGINPUTKAN DATA KE BST
Disini merupakan penggabungan antara queue dan binary search trees. Dimana yang kita tahu bahwa queue merupakan antrian yang bersifat FIFO (First In First Out). Data yang pertama kali masuk merupakan data yang pertama kali keluar. Jika digabungkan dengan metode binary search tree, data yang pertama masuk menjadi data yang pertama keluar. Kemudian data yang keluar ini akan menjadi root pada tree. Begitu juga selanjutnya data yang keluar akan dijadikan subpohon dari root tersebut. Jika data yang keluar selanjutnya lebih kecil dari root akan diletakkan di sebelah kiri root, jika lebih besar akan diletakkan di sebelah kanan root. Jangan lupa bahwa root akan selalu bergeser sesuai dengan bertambahnya data yang masuk dan binary tree hanya memiliki 2 subpohon setiap root.
Contoh penggabungan queue dengan binary search trees :
ØMENEMUKAN DATA DI BST
Setelah data masuk kedalam tree, selanjutkan kita pikirkan bagaimana cara menemukan data secara cepat. Disini menggunakan algoritma search untuk mempercepat pencarian. Misal dari data di atas kita ingin mencari angka 3. Pertama kita bandingkan data 3 dengan 4. Ternyata lebih kecil sehingga begeser ke kiri. Rootnya bergeser menjadi 2. Kita bandingkan data 3 dengan 2. Ternyata lebih besar, maka bergeser ka kanan. Rootnya bergeser menjadi 3. Kemudian kita bandingkan data 3 dengan 3. Ternyata data di temukan.
Ø MENGHAPUS DATA DARI BST
Prinsip kerjanya sama dengan pencarian data. Kalau pencarian setelah ketemu di tampilkan bahwa data ditemukan, kalau removing setelah data ditemukan berarti itu data yang dihapus.
Ø ATURAN DALAM BST
1. Setiap node yang terletak di sebelah kiri nilainya harus lebih kecil dari root
2. Setiap node yang terletak di sebelah kanan nilainya harus lebih besar dari root
Kamu dapat melihat kembali dari fungsi rekursif dan dapat diterapkan pada seiap node pada tree.
Ø MENGOPTIMALKAN TREES
Jika ternyata tree yang kita kita buat membentuk suatu urutan angka contoh 1,2,3,4,5, maka terlihat seperti sebuah linked list.
Kondisi ini menyebabkan tree tidak memiliki subpohon karena berbentuk linier. Ini merupakan kondisi yang tidak wajar. Ada AVL trees, splay trees, dan red-black trees yang merupakan aplikasi special di BSTs yang dapat menunjukkan perputaran node ketika mereke menambahkan data agar susunan tree lebih seimbang,
Ø MENDEMONSTRASIKAN GRAFIK: BSTs
Ini merupakan suatu aplikasi untuk mendemonstrasikan suatu BST. Dengan aplikasi ini kita dapat membuat simulasi tentang tree.demontrasi ini menggunakan SDLGUI Library untuk membuat menu-menu yang dibutuhkan untuk mendemonstrasikan tree.
Ø MENGKODEKAN BST
STRUKTUR
BST menggunakan binary tree sebagai struktur dasarnya, tetapi hanya berisi pointer untuk root dan fungsi pembanding.
template
class BinarySearchTree
{
public:
typedef BinaryTree Node;
Node* m_root;
int (*m_compare)(DataType, DataType);
};
FUNGSI PEMBANDINGAN
Definisi dari fungsi pembandingan adalah memiliki 2 tipe parameter yaitu tipe data dan integer. Integer memiliki 3 kondisi.
- Jika angka negative, maka parameter sebelah kiri lebih kecil dari sebelah kanan.
- Jika angka benilai 0, maka memiliki 2 parameter yang sama
- Jika angka positif, maka parameter sebelah kiri lebih besar dari sebelah kanan
Contohnya :
int CompareInts( int left, int right )
{
return left - right;
}
KONSTRUKTOR
Konstruktor merupakan fungsi dasar dari fungsi pembanding yaitu sebagai parameter dan mengarahkan root ke NULL.
BinarySearchTree( int
(*p_compare)(DataType, DataType) )
{
m_root = 0;
m_compare = p_compare;
};
DESTRUKTOR
Destruktor secara sederhana berfungsi menghapus root.
~BinarySearchTree()
{
if( m_root != 0 )
delete m_root;
}
FUNGSI INPUT
Ada dua jurusan kamu dapat memasukkan node kedalam tree biner,sesuatu adalah berulang, dan yang lain adalah iterative.Fungsi rekursif dalam hal ini adalah tanpa makna sebab ini adalah tidak terlalu satu algoritma berulang. Sehingga daripada recursion, Aku mempergunakan algoritma iterative. Aku memisahkan ini menaiki kedalam beberapa segmen juga yang ini lebih mudah untuk pahami.
void Insert( DataTypep_data )
{
Node* current = m_root;
if(m_root == 0 )
m_root = new Node(p_data );
Ini segmen pertama mengambil masing-masing data sebagai satu parameter dan menciptakan satu iterator disebutkan saat ini, yang titikke root dari tree. Kalauakaradalahkosong, fungsi
ciptakansatubengkakuratakarbaru. Kalautidak, fungsiberlanjut:
else
{
while( current != 0 )
{
Awalsegmeninisementarasimpal.Bepergianfungsimemutuskan treesementara
iteratoradalahsah, dansecepatfungsimemasukkansatu node kedalam tree, setelaniniiterator untukmemasuki loop akankeluar.
if(m_compare( p_data, current->m_data ) < 0 )
{
if( current->m_left == 0 )
{
current->m_left = new Node( p_data );
current->m_left->m_parent = current;
current = 0;
}
else
current = current->m_left;
}
Segmensebelumnyadarikodelakukanbeberapahal.Inibandingkanpertama data pada
nodesaatinidengan data yang kamumaumemasukkankedalam tree. Kalauhasildarim_comparefungsiadalahkurangdarimemasuki, kamumaumemasukkaninikedalamanaksebelahkiri.Berikutnyalangkahadalahuntukmencekkalauanaksebelahkiriberada.Kalautidak, ciptakansatuanaksebelahkiribarudansetelansaatinike 0. kemudiangerakkanponteri kesebelahkiri..Kodeberikutnyainimembagilakukanhal yang sama, tapikehaksaatini:
else
{
if( current->m_right == 0 )
{
current->m_right = new Node( p_data );
current->m_right->m_parent = current;
current = 0;
}
else
current = current->m_right;
}
}
}
}
FUNGSI PENCARIAN
Fungsi ini adalah hamper sama halnya Lampiran berfungsi mengecuali bahwa ini baru kembalikan Pointer ke node kalau ini temukan data pada tree.
Node* Find(DataTypep_data )
{
Node* current = m_root;
int temp;
while( current != 0 )
{
temp = m_compare( p_data, current->m_data );
if( temp == 0 )
return current;
if( temp < 0 )
current = current->m_left;
else
current = current->m_right;
}
return 0;
}
CONTOH 13-1 : MENGGUNAKAN KELAS BST
IniadalahContoh 13 - 1, pertunjukkan yang bagaimana caranya mempergunakan Binary Search Tree kelas dengan bilangan bulat. Program source untuk contoh ini berada di atas CD pada direktori\BinerPencarian examples\ch13\01 Trees\.Contoh mempergunakan Compare Ints berfungsi menampilkan lebih awal kebilangan bulat di simpan pada BST:
void main()
{
BinarySearchTreetree(CompareInts );
BinaryTree* node;
// insert data
tree.Insert( 8 );
tree.Insert( 4 );
tree.Insert( 12 );
tree.Insert( 2 );
tree.Insert( 6 );
tree.Insert( 10 );
tree.Insert( 14 );
// these searches are successful
node = tree.Find( 8 );
node = tree.Find( 2 );
node = tree.Find( 14 );
node = tree.Find( 10 );
// these searches return 0
node = tree.Find( 1 );
node = tree.Find( 3 );
node = tree.Find( 5 );
node = tree.Find( 7 );
}
Ø APLIKASI : PENYIMPAAN, SUMBER, KUNJUNGAN
v CLASS SUMBER
Kamu mungkin telah memperhatikan bahwa penggunaan BST sedikit berbeda dibandingkan menggunakan tabel hash; Dimana tabel hash menggunakan kunci / menyimpan dan mendapatkan kembali data, kelas BST tidak melakukan itu. Sebagai ganti, ini hanya menyimpan data yang benar dalam tree. Dalam keterangan ini melakukan sebab implementasi ke kode demo sedikit berbeda.
Pertama-tama, Aku menciptakan Resource class , yang akan punya dua hal,
String dan SDL_Surface pointer:
class Resource
{
public:
char m_string[64];
SDL_Surface* m_surface;
};
FUNGSI PERBANDINGAN
Hal berikutnya yang aku perlu kulakukan adalah menciptakan fungsi perbandingan. Karena kamu mau mencari tree untuk string, kamu akan mempergunakan standar C strcmp function
untuk membandingkan string.
int ResourceCompare( Resource p_left, Resource p_right )
{
return strcmp( p_left.m_string, p_right.m_string );
}
Sungguh beruntung, strcmp berfungsi kembali satu angka negatif kalau string sebelah kiri adalah kurang dari string kanan, 0 jika mereka seimbang, angka positif kalau sebelah kiri adalah lebih besar dibandingkan kanan!
Sehingga fungsi compares resource ini berlandaskan sebutkan hanyalah, tidak berlandaskan nyata bitmap bahwa Resource kelas berisi. Ini adalah penting ketika kamu cari-cari
apapun pada tree.
MEMASUKKAN RESOURCES
Memasukkan resource ke dalam tree adalah serupa dengan memasukkan mereka ke dalam satu tabel hash kecuali yang dari pada memasukkan string / pasangan permukaan ke dalam tree, kamu menciptakan satu struktur resource yang pertama.
Resource res;
res.m_surface = SDL_LoadBMP( “sky.bmp” );
strcpy( res.m_string, “sky” );
g_tree.Insert( res );
Strcpy berfungsi menyalin string ke dalam namanya ke dalam resource. Langkah ini akan diulangi setiap resource pada demo.
MENEMUKAN RESOURCE
Untuk mencari sumber kamu membutuhkan sumber dummy, dimana yang tidak terdiri dari bidang, tetapi hanya string
Resource res;
strcpy( res.m_string, g_name );
g_name variabel adalah satu string yang berisi nama dari resource untuk mencari. m_surface variabel dari res ditinggalkan kosong.
Setelah tersebut, kamu mengumumkan satu binary tree node pointer, yang akan menggenggam node kembali dari BST ‘s Find berfungsi:
BinaryTree* node = 0;
node = g_tree.Find( res );
Sekarang BST akan membandingkan resource imitasi nama dengan nama dari Resource pada BST, dan kalau ini menemukan satu cocok, ini akan kembali ke node yang berisi resource. Ketika node dikembalikan, semua yang perlu kamu lakukan adalah menentukan apakah
ini sah kemudian dapat digunakan:
if( node != 0 )
g_resource = node->m_data.m_surface;
else
g_resource = 0;
Ø KESIMPULAN
BTS tidak hanya digunakan untuk hash table saja. Dimana pencarian hash table berakhir ke O(c),pencarian best-case memakan waktu lebih cepat dari hash table, pada O(log2n).
Maka BST memperkenalkan konsep rekursif data. Konsep ini sangat penting digunakan dalam pemrograman game, seperti Binary Space Partition (BSP) tree. BSPs memiliki susunan yang rapi seperti polygon yang terbagi di 3D (atau 2D menurut John Carmack yang menggunakan DOOM) dunia sehingga kamu dapat lebih mudah menentukan tempat yang terlihat. Konsep dari BSP tree sama dengan konsep BST’s.
0 komentar:
Posting Komentar