Insersi
Untuk memastikan bahwa pohon yang diberikan tetap AVL setelah setiap penyisipan, kita harus menambah operasi penyisipan BST standar untuk melakukan penyeimbangan ulang. Berikut ini adalah dua operasi dasar yang dapat dilakukan untuk menyeimbangkan kembali BST tanpa melanggar properti BST (kunci (kiri) <kunci (root) <kunci (kanan)).
1) Rotasi Kiri
2) Rotasi Kanan
T1, T2 dan T3 adalah sub pohon
di-root dengan y (di sebelah kiri) atau x (di
sisi kanan)
y x
/ \ Rotasi Kanan / \
x T3 - - - - - - -> T1 y
/ \ <- - - - - - / / \
T1 T2 Putaran Kiri T2 T3
Kunci di kedua pohon di atas mengikuti
mengikuti pesanan
kunci (T1) <kunci (x) <kunci (T2) <kunci (y) <kunci (T3)
Jadi properti BST tidak dilanggar di mana pun.
Langkah-langkah yang harus diikuti untuk pemasangan
Biarkan simpul yang baru dimasukkan menjadi w
1) Lakukan insert BST standar untuk w.
2) Mulai dari w, naik dan temukan simpul tidak seimbang pertama. Biarkan z menjadi simpul tidak seimbang pertama, y menjadi anak dari z yang datang di jalan dari w ke z dan x menjadi cucu dari z yang datang di jalur dari w ke z.
3) Seimbangkan kembali pohon dengan melakukan rotasi yang sesuai pada subtree yang di-root dengan z. Ada 4 kemungkinan kasus yang perlu ditangani karena x, y dan z dapat diatur dalam 4 cara. Berikut ini adalah 4 pengaturan yang mungkin:
a) y adalah anak kiri dari z dan x adalah anak kiri dari y (Kasing Kiri Kiri)
b) y adalah anak kiri z dan x adalah anak kanan y (Left Right Case)
c) y adalah anak kanan z dan x adalah anak kanan y (Right Right Case)
d) y adalah anak kanan z dan x adalah anak kiri y (Kasus Kiri Kanan)
B-Tree adalah pohon pencarian self-balancing. Di sebagian besar pohon pencarian self-balancing lainnya (seperti AVL dan Red-Black Trees), diasumsikan bahwa semuanya ada dalam memori utama. Untuk memahami penggunaan B-Trees, kita harus memikirkan sejumlah besar data yang tidak dapat ditampung dalam memori utama. Ketika jumlah kunci tinggi, data dibaca dari disk dalam bentuk blok. Waktu akses disk sangat tinggi dibandingkan dengan waktu akses memori utama. Gagasan utama menggunakan B-Trees adalah untuk mengurangi jumlah akses disk. Sebagian besar operasi pohon (pencarian, masukkan, hapus, maks, min, ..etc) memerlukan O (h) akses disk di mana h adalah ketinggian pohon. B-tree adalah pohon yang gemuk. Ketinggian B-Trees dijaga tetap rendah dengan meletakkan kunci maksimum yang mungkin dalam simpul B-Tree. Secara umum, ukuran simpul B-Tree dijaga sama dengan ukuran blok disk. Karena h rendah untuk B-Tree, akses disk total untuk sebagian besar operasi berkurang secara signifikan dibandingkan dengan Binary Search Trees yang seimbang seperti AVL Tree, Red-Black Tree, ..etc.
Properti B-Tree
1) Semua daun berada pada level yang sama.
2) B-Tree didefinisikan dengan istilah tingkat minimum ‘t ’. Nilai t tergantung pada ukuran blok disk.
3) Setiap node kecuali root harus mengandung setidaknya kunci t-1. Root mungkin berisi kunci minimal 1.
4) Semua node (termasuk root) dapat berisi maksimal 2t - 1 kunci.
5) Jumlah anak-anak dari sebuah simpul sama dengan jumlah kunci di dalamnya ditambah 1.
6) Semua kunci simpul diurutkan dalam urutan yang meningkat. Anak antara dua tombol k1 dan k2 berisi semua kunci dalam kisaran dari k1 dan k2.
7) B-Tree tumbuh dan menyusut dari akar yang tidak seperti Binary Search Tree. Binary Search Trees tumbuh ke bawah dan juga menyusut dari bawah.
8) Seperti Pohon Penelusuran Biner seimbang lainnya, kompleksitas waktu untuk mencari, menyisipkan, dan menghapus adalah O (Logn).
Tidak ada komentar:
Posting Komentar