Pohon Biner Terurut

1. Introduction

Sebuah Pohon Biner Terurut (PBT atau biasa disebut Binary Search Tree, BST dalam Bahasa Inggris) adalah sebuah pohon biner di mana setiap simpul hanya memiliki tidak lebih dari 2 anak yang memenuhi properti BST. Semua simpul-simpul di sub-pohon kiri dari sebuah simpul harus memiliki nilai lebih kecil dibandingkan daripada simpul itu dan semua simpul-simpul di sub-pohon kanan dari sebuah simpul harus memiliki nilai lebih besar daripada simpul itu (kami berasumsi bahwa semua nilai yang dimasukkan pada visualisasi ini adalah bilangan-bilangan bulat yang unik dan perubahan kecil diperlukan untuk mendukung nilai yang tidak unik). Cobalah mengklik Search(7) untuk animasi contoh pencarian sebuah nilai acak ∈ [1..99] pada BST acak diatas.


Sebuah pohon Adelson-Velskii Landis (AVL) adalah BST yang dapat menyeimbangkan diri sendiri di mana tinggi pohon tersebut dapat selalu dibatasi oleh O(log N) dimana N adalah jumlah simpul-simpul didalam pohon AVL tersebut.

2. BST & BST Seimbang (Pohon AVL)

Untuk beralih antara Pohon Biner Terurut biasa dan Pohon AVL (dengan perilaku yang berbeda selama Pemasukkan dan Penghapusan dari sebuah bilangan bulat), pilihlah header masing-masing.


Kita juga memiliki shortcut URL untuk dengan cepat mengakses mode Pohon AVL, yaitu https://visualgo.net/en/avl (anda dapat mengganti 'en' ke dua karakter bahasa pilihan anda - jika tersedia).

3. Motivasi

BST (dan terutama BST yang seimbang seperti Pohon AVL) adalah struktur data efisien untuk mengimplementasikan tipe tertentu dari Struktur Data Abstrak (Abstract Data Type, ADT) Tabel (atau Map).


Sebuah ADT Tabel harus mendukung setidaknya tiga operasi-operasi berikut seefisien mungkin:

  1. Cari(v) — tentukan apakah v ada didalam ADT atau tidak,
  2. Masukkan(v) — masukkan v kedalam ADT,
  3. Hapus(v) — hapus v dari ADT.

Referensi: Lihat slide yang mirip dalam Kuliah Maya Tabel Hash.

3-1. ADT Table Seperti Apa?

Kami merujuk kepada ADT Tabel dimana kunci-kunci nya perlu diurutkan (dibandingkan dengan ADT Tabel dimana kunci-kuncinya tidak perlu terurut).


Kebutuhan spesial dari ADT Tabel ini akan diperjelas di beberapa slide-slide seterusnya.

3-2. Menggunakan Larik/Vector Tidak Terurut

Jika kita menggunakan larik/vector tidak-terurut untuk mengimplementasikan ADT Tabel, hal ini bisa tidak efisien:

  1. Cari(v) berjalan dalam O(N), karena kita bisa pada akhirnya mengeksplorasi semua N elemen-elemen dari ADT tersebut jika v sebenarnya tidak ada,
  2. Masukkan(v) bisa diimplementasikan dalam O(1), taruh saja v di sisi belakang larik,
  3. Hapus(v) berjalan dalam O(N) juga karena kita pertama harus mencari v yang sudah O(N) dan nantinya menutup bolong yang terjadi setelah penghapusan — juga dalam O(N).

3-3. Menggunakan Larik/Vector Terurut

Jika kita menggunakan larik/vector terurut untuk mengimplementasikan ADT Tabel, kita dapat memperbaiki performa Cari(v) tetapi melemahkan performa Masukkan(v):

  1. Cari(v) sekarang dapat diimplementasikan dalam O(log N), karena kita sekarang bisa menggunakan pencarian biner (binary search) pada larik terurut,
  2. Masukkan(v) sekarang berjalan dalam O(N) karena kita perlu mengimplementasikan strategi mirip insertion-sort untuk membuat larik tetap terurut,
  3. Hapus(v) berjalan dalam O(N) karena meskipun Cari(v) berjalan dalam O(log N), kita tetap perlu menutup bolong yang terjadi setelah penghapusan — yang adalah O(N).

3-4. Kompleksitas O(log N)?

Tunjuan dari Kuliah Maya ini adalah untuk memperkenalkan struktur data BST dan lalu BST yang seimbang (Pohon AVL) sehingga kita dapat mengimplementasikan operasi-operasi dasar dari ADT Tabel: Cari(v), Masukkan(v), Hapus(v), dan beberapa operasi-operasi ADT Tabel lainnya — lihat slide berikutnya — dalam waktu O(log N) — yang adalah jauh lebih kecil dari N.


Catatan: Beberapa dari pembaca yang lebih berpengalaman mungkin menyadari bahwa ∃ struktur data lain yang bisa mengimplementasikan kitiga operasi-operasi dasar ADT Tabel dengan lebih cepat, tapi lanjutkan baca terlebih dulu...


N≈ 1 000≈ 1 000 000≈ 1 000 000 000
log N10Only 20 :OOnly 30 :O:O

3-5. Operasi-Operasi ADT Tabel Lainnya

Diatas tiga operasi dasar, masih ada beberapa operasi-operasi ADT Tabel yang memungkinkan:

  1. Temukan elemen Min()/Maks(),
  2. Temukan elemen Penerus(v) — 'yang lebih besar selanjutnya'/Pendahulu(v) — 'yang lebih kecil sebelumnya',
  3. Daftarkan elemen-elemen dalam urutan terurut,
  4. Operasi X & Y - disembunyikan untuk alasan pedagogis di sebuah modul NUS,
  5. Masih ada beberapa operasi-operasi yang memungkinkan.

Diskusi: Apa implementasi terbaik untuk ketiga operasi-operasi tambahan pertama jika kita dibatasi hanya boleh menggunakan larik/Vector [terurut|tidak-terurut]?

3-6. Solusinya

[This is a hidden slide]

3-7. Bagaimana dengan Senarai Berantai?

Struktur data yang lebih sederhana yang dapat digunakan untuk mengimplementasikan ADT Tabel adalah Linked List.


Quiz: Can we perform all basic three Table ADT operations: Search(v)/Insert(v)/Remove(v) efficiently (read: faster than O(N)) using Linked List?

No
Yes


Diskusi: Kenapa?

3-8. Solusinya

[This is a hidden slide]

3-9. Bagaimana dengan Tabel Hash?

Struktur data lainnya yang dapat digunakan untuk mengimplementasikan ADT Tabel adalah Tabel Hash. Struktur data tersebut memiliki performa Cari(v), Masukkan(v), dan Hapus(v) yang sangat cepat (semua dalam waktu ekspektasi O(1)).


Quiz: So what is the point of learning this BST module if Hash Table can do the crucial Table ADT operations in unlikely-to-be-beaten expected O(1) time?

There are valid reasons, which are ____
There is no point, so this BST module can be ignored


Diskusikan jawaban diatas! Petunjuk: Kembali ke 4 slide sebelumnya.

3-10. Solusinya

[This is a hidden slide]

4. Visualisasi

Kita akan sekarang memperkenalkan struktur data BST. Lihat visualisasi dari BST contoh di atas!


Simpul akar tidak memiliki orangtua. Hanya boleh terdapat satu simpul akar dalam sebuah BST. Simpul daun tidak memiliki anak. Bisa terdapat lebih dari satu simpul daun dalam sebuah BST. Setiap simpul lainnya yang bukan merupakan akar ataupun daun dinamakan simpul dalam (internal vertices). Kadang-kadang simpul akar tidak dimasukkan sebagai definisi dari simpul dalam karena akar dari sebuah BST dengan hanya satu simpul sebenarnya bisa pas dalam definisi dari sebuah daun juga.

Pada contoh diatas, simpul 15 adalah simpul akar, simpul {5, 7, 50} adalah simpul-simpul daun, simpul {4, 6, 15 (juga adalah akar), 23, 71} adalah simpul-simpul dalam.

4-1. Atribut-Atribut Simpul BST

Setiap simpul memiliki setidaknya 4 atribut: orangtua, kiri, kanan, kunci/nilai/data (ada atribut-atribut potensial lainnya). Tidak semua atribut akan digunakan di semua simpul, misalkan simpul akar akan memiliki atribut orangtua = KOSONG (NULL). Beberapa implementasi lainnya memisahkan kunci (untuk mengurutkan simpul-simpul dalam BST) dengan data satelit (satellite data) sesungguhnya yang terasosiasi dengan kunci-kunci tersebut.


Anak kiri/kanan dari sebuah simpul (kecuali daun) masing-masing digambar pada sisi kiri/kanan dan dibawah simpul tersebut. Orangtua dari sebuah simpul (kecuali akar) digambar diatas simpul tersebut. Kunci (bilangan bulat) dari setiap simpul digambar didalam lingkaran yang merepresentasikan simpul tersebut. Didalam contoh diatas, (kunci) 15 memiliki 6 sebagai anak kirinya dan 23 sebagai anak kanannya. Sehingga orangtua dari 6 (dan 23) adalah 15.

4-2. Properti BST

Karena kami tidak mengijinkan bilangan bulat yang duplikat dalam visualisasi ini, properti BST adalah sebagai berikut: Untuk setiap simpul X, semua simpul-simpul di sub-pohon kiri dari X adalah secara ketat lebih kecil dari X dan semua simpul-simpul pada sub-pohon kanan dari X adalah secara ketat lebih besar dari X.


Didalam contoh diatas, simpul-simpul pada sub-pohon kiri dari akar 15: {4, 5, 6, 7} semuanya lebih kecil dari 15 dan simpul-simpul pada sub-pohon kanan dari akar 15: {23, 50, 71} semuanya lebih besar dari 15. Anda dapat mengecek properti BST secara rekursif pada simpul-simpul lainnya juga.


Untuk implementasi yang lebih komplet, kita harus memikirkan bilangan-bilangan bulat yang mungkin terduplikasi juga. Cara termudah untuk mendukung ini adalah untuk menambah satu lagi attribute pada setiap simpul: frekuensi kemunculan X (visualisasi ini akan dimutakhirkan dengan fitur ini segera).

5. Operasi-Operasi BST

Kami menyediakan visualisasi dari operasi-operasi umum BST/Pohon AVL:

  1. Operasi-operasi Pertanyaan (Query) (struktur BST tidak berubah):
    1. Cari(v),
    2. Pendahulu(v) (dan mirip dengannya Penerus(v)), dan
    3. Penjelajahan Inorder (kami akan menambah Penjelajahan Preorder dan Postorder segera),
  2. Operasi-operasi Pemutakhiran (Update) (struktur BST sangat mungkin berubah):
    1. Masukkan(v),
    2. Hapus(v), dan
    3. Buat BST (dengan berbagai kriteria).

5-1. Beberapa Operasi BST yang Lain

Ada beberapa operasi-operasi (Query) BST lainnya yang belum divisualisasikan di VisuAlgo:

  1. Ranking(v): Diberikan kunci v, tentukan apakah rankingnya (indeks berbasis-1) dalam urutan terurut dari elemen-elemen BST. Maksudnya, Ranking(TemukanMin()) = 1 dan Ranking(TemukanMaks()) = N. Jika v tidak ada, kita bisa melaporkan -1.
  2. Pilih(k): Diberikan sebuah ranking k, 1 ≤ kN, tentukan kunci v yang memiliki ranking k tersebut didalam BST. Atau dalam kata lain, temukan elemen terkecil ke-k didalam BST. Maksudnya, Pilih(1) = TemukanMin() dan Pilih(N) = TemukanMaks().

Detil-detil dari kedua operasi ini saat ini disembunyikan untuk alasan pedagogis di sebuah modul NUS.

5-2. Struktur Data Statis vs Dinamis

Struktur data yang hanya efisien jika tidak (atau jarang) ada pemutakhiran (update), terutama operasi pemasukkan dan/atau penghapusan disebut struktur data statis.


Struktur data yang efisien meskipun ada banyak operasi-operasi pemutakhiran disebut struktur data dinamis. BST dan terutama BST yang seimbang (contohnya Pohon AVL) ada didalam kategori ini.

6. Cari(v)

Dikarenakan cara data (bilangan-bilangan bulat unik di visualisasi ini) diorganisasikan didalam sebuah BST, kita dapat mencari secara biner (binary search) sebuah bilangan bulat v dengan efisien (maka namanya disebut Pohon Pencarian Biner/Pohon Biner Terurut/Binary Search Tree).


Pertama, kita set simpul sekarang = akar dan cek apakah simpul sekarang lebih kecil/sama/lebih besar dari bilangan bulat v yang kita cari. Kita lalu pergi ke sub-pohon kanan/berhenti/pergi ke sub-pohon kiri, sesuai dengan kondisi. Kita terus melakukan hal ini sampai kita menemukan simpul yang diperlukan atau tidak.

Pada contoh BST diatas, cobalah mengklik Search(23) (ditemukan setelah hanya 1 pembandingan), Search(7) (ditemukan setelah 3 pembandingan), Search(21) (tidak ditemukan setelah 3 pembandingan).

6-1. TemukanMin() dan TemukanMaks()

Sama juga, karena cara data diorganisasikan didalam sebuah BST, kita dapat menemukan elemen minimum/maksimum (sebuah bilangan bulat di visualisasi ini) dengan memulai dari akar dan terus pergi ke sub-pohon kiri/kanan.


Cobalah klik FindMin() dan FindMax() pada BST contoh yang ditunjukkan diatas. Jawaban-jawabannya harusnya 4 dan 71 (keduanya setelah 4 pembandingan).

6-2. Kompleksitas Waktu O(h)

Operasi-operasi Cari(v)/TemukanMin()/TemukanMaks() berjalan dalam O(h) dimana h adalah tinggi dari BST.


Tetapi catat bahwa h ini bisa setinggi O(N) pada sebuah BST normal seperti yang ditunjukkan pada contoh 'miring kanan' acak diatas. Coba Search(100) (nilai ini harusnya tidak ada karena kami hanya menggunakan bilangan-bilangan bulat acak diantara [1..99] untuk membuat BST acak ini sehingga rutin pencarian harusnya mengecek semua dari akar ke daun satu-satunya dalam waktu O(N) — tidak efisien.

7. Penerus(v)

Karena properti-properti BST, kita dapat mencari Penerus dari sebuah bilangan bulat v (kita berasumsi bahwa kita telah mengetahui dimana bilangan bulat v terletak dari panggilan Cari(v) sebelumnya) dengan cara berikut:

  1. Jika v memiliki sub-pohon sebelah kanan, bilangan bulat terkecil di sub-pohon kanan tersebut adalah penerus dari v. Cobalah Successor(23) (harusnya 50).
  2. Jika v tidak memiliki sub-pohon kanan tidak, kita perlu menelusuri pendahulu (ancestor) dari v hingga menemukan 'belokan ke kanan' ke simpul w (atau, sampai kita menemukan simpul pertama w yang lebih besar dibandingkan simpul v). Segera setelah kita menemukan simpul w, kita bisa melihat bahwa simpul v adalah nilai maksimum di sub-pohon sebelah kiri dari simpul w. Cobalah Successor(7) (harusnya 15).
  3. Jika v adalah bilangan bulat terbesar dalam BST, v tidak memiliki penerus. Cobalah Successor(71) (harusnya tidak ada).

7-1. Sebelum(v)

Operasi-operasi untuk Pendahulu dari sebuah bilangan bulat v didefinisikan secara mirip (hanya cerminan dari operasi-operasi Penerus).


Cobalah ketiga kasus sudut (corner cases) (tetapi mirrored): Predecessor(6) (harusnya 5), Predecessor(50) (harusnya 23), Predecessor(4) (harusnya tidak ada).


Pada point ini, berhenti sejenak dan At this point, stop and renungkan ketiga kasus-kasus Penerus(v)/Pendahulu(v) untuk memastikan bahwa anda mengerti konsep-konsep ini.

7-2. Kompleksitas Waktu O(h)

Operasi-operasi Pendahulu(v) dan Penerus(v) berjalan dalam O(h) dimana h adalah tinggi dari BST.


Tetapi ingatlah kembali bahwa h ini bisa setinggi O(N) didalam BST normal seperti yang ditunjukkan di contoh 'miring kanan' acak diatas. Jika kita memanggil Successor(FindMax()), kita akan naik keatas dari daun terakhir tersebut sampai kembali ke akar dalam waktu O(N) — tidak efisien.

8. Penjelajahan Inorder

Kita dapat melakukan sebuah Penjelajahan Inorder dari BST ini untuk mendapatkan bilangan-bilangan bulat yang terurut dalam BST ini (pada kenyataannya, jika kita 'meratakan' BST menjadi satu baris, kita akan melihat bahwa simpul-simpulnya terurut dari terkecil hingga terbesar).


Penjelajahan Inorder adalah metode rekursif dimana kita mengunjungi sub-pohon kiri dahulu, kemudian mengunjungi habis seluruh nilai di sub-pohon kiri tersebut, kemudian mengunjungi akar sekarang, sebelum menjelajahi dan mengunjungi habis seluruh nilai di sub-pohon kanan. Tanpa basa basi lagi, mari coba Inorder Traversal untuk melihat penjelajahan inorder bekerja pada BST contoh diatas.

8-1. Kompleksitas Waktu O(N)

Penjelajahan Inorder berjalan dalam O(N), terlepas dari tinggi BST.


Diskusi: Kenapa?


Catatan: Beberapa orang menamai pemasukkan dari N bilangan-bilangan bulat tak terurt kedalam sebuah BST dalam O(N log N) dan lalu melakukan Penjelajahan Inorder O(N) sebagai 'pengurutan BST'. Algoritma ini jarang digunakan karena ada beberapa algoritma-algoritma pengurutan (berbasis-pembandingan) yang lebih-mudah-dipakai daripada algoritma ini.

8-2. Solusinya

[This is a hidden slide]

8-3. Penjelajahan Preorder dan Postorder

Kami belum memasukkan animasi dari dua metode-metode penjelajahan pohon klasik ini, tetapi kami akan melakukannya segera.


Tetapi pada dasarnya, dalam Penjelajahan Preorder, kita mengunjungi akar yang sekarang sebelum pergi ke sub-pohon kiri dan lalu ke sub-pohon kanan. Untuk BST contoh yang ditunjukkan di latar belakang, kita memiliki: {{15}, {6, 4, 5, 7}, {23, 71, 50}}. Catatan: Apakah anda menyadari pola rekursifnya? akar, anggota-anggota dari sub-pohon kiri dari akar, anggota-anggota dari sub-pohon kanan dari akar.


Dalam Penjelajahan Postorder, kita mengunjungi sub-pohon kiri dan sub-pohon kanan terlebih dahulu, sebelum mengunjungi akar yang sekarang. Untuk BST contoh yang ditunjukkan di latar belakang, kita mempunyai: {{5, 4, 7, 6}, {50, 71, 23}, {15}}.

9. Masukkan(v)

Kita dapat memasukkan sebuah bilangan bulat kedalam BST dengan melakukan operasi yang mirip dengan Masukkan(v). Tetapi kali ini, daripada melaporkan bahwa bilangan bulat baru tersebut tidak ditemukan, kita menciptakan sebuah simpul baru pada titik masukan dan menaruh bilangan bulat baru tersebut disana. Cobalah Insert(60) pada contoh diatas.

9-1. Kompleksitas Waktu O(h)

Masukkan(v) berjalan dalam O(h) dimana h adalah tinggi dari BST.


Saat ini anda harusnya menyadari bahwa h ini bisa setinggi O(N) dalam sebuah BST normal seperti yang ditunjukkan dalam contoh 'miring kanan' acak diatas. Jika kita memanggil Insert(FindMax()+1), yaitu kita memasukkan sebuah bilangan bulat baru yang lebih besar dari nilai maks sekarang, kita akan berjalan turun dari akar ke daun terakhir lalu memasukkan bilangan bulat baru tersebut sebagai anak kanan dari daun terakhir tersebut dalam waktu O(N) — tidak efisien (catat bahawa kami hanya mengijinkan sampai h=9 dalam visualisasi ini).

9-2. Kuis Mini

Quiz: Inserting integers [1,10,2,9,3,8,4,7,5,6] one by one in that order into an initially empty BST will result in a BST of height:

9
The height cannot be determined
8
10


Tips-ahli: Anda dapat menggunakan 'mode Eksplorasi' untuk memverifikasi jawabannya.

10. Hapus(v) - Tiga Kasus yang Memungkinkan

Kita dapat menghapus sebuah bilangan bulat pada BST dengan melakukan operasi yang sama seperti Mencari(v).


Jika v tidak ditemukan didalam BST, kita tidak perlu melakukan apa-apa.


Jika v ditemukan didalam BST, kita tidak melaporkan bahwa bilangan bulat v yang eksis tersebut telah ditemukan, tetapi, kita melakukan salah satu dari tiga kasus penghapusan yang akan dijelaskan di tiga slide-slide terpisah (kami sarankan agar anda mencoba masing-masing satu per satu).

10-1. Hapus(v) - Kasus 1

Kasus pertama adalah yang termudah: Simpul v adalah salah satu daun dari BST


Penghapusan simpul daun sangatlah mudah: Kita cukup menghapus simpul daun tersebut — cobalah Remove(5) pada BST contoh diatas (pengklikan kedua setelah penghapusan pertama tidak akan melakukan apa-apa — silahkan refresh halaman ini atau pergi ke slide berikutnya dan kembali ke slide ini).


Bagian ini jelas O(1) — diatas dari usaha O(h) yang mirip dengan usaha pencarian.

10-2. Hapus(v) - Kasus 2

Kasus kedua juga tidak terlalu sulit: Simpul v adalah sebuah simpul (dalam/akar) dari BST tersebut dan hanya memiliki tepat satu anak. Menghapus v tanpa melakukan apa-apa yang lain akan memutuskan BST.


Penghapusan dari sebuah simpul dengan satu anak tidaklah sulit: Kita menghubungkan anak tunggal dari simpul tersebut dengan orangtua dari simpul tersebut — cobalah Remove(23) pada BST contoh diatas (pengklikan kedua dan seterusnya setelah penghapusan yang pertama tidak akan melakukan apa-apa — silahkan refresh halaman ini atau pergi ke slide lain dan kembali ke slide ini lagi).


Bagian ini juga jelas O(1) — diatas dari usaha O(h) mirip-pencarian sebelumnya.

10-3. Hapus(v) - Kasus 3

Kasus ketiga adalah yang paling kompleks diantara tiga kasus tersebut: Simpul v adalah sebuah simpul (dalam/akar) dari BST dan memiliki tepat dua anak-anak. Menghapus v tanpa melakukan apa-apa yang lain akan memutuskan BST.


Penghapusan sebuah simpul dengan dua anak-anak adalah sebagai berikut: Kita mengganti simpul tersebut dengan penerusnya, lalu kita menghapus penerus yang terduplikasi di sub-pohon kanannya — cobalah Remove(6) pada BST contoh diatas (pengklikan kedua dan selanjutnya setelah penghapusan yang pertama tidak akan melakukan apa-apa — silahkan refresh halaman ini atau pergi ke slide lain dan kembali ke slide ini lagi).


Bagian ini membutuhkan O(h) karena kita harus mencari simpul penerus — diatas dari usaha O(h) mirip-pencarian sebelumnya.

10-4. Hapus(v) - Diskusi Kasus 3

Kasus ke 3 ini membutuhkan diskusi-diskusi lebih lanjut:

  1. Mengapa mengganti sebuah simpul B yang memiliki dua anak dengan penerusnya C selalu adalah strategi yang valid?
  2. Bisakah kita mengganti simpul B yang memiliki dua anak dengan pendahulu A? Bisa atau tidak bisa?

10-5. Jawabannya

[This is a hidden slide]

10-6. Kompleksitas Waktu O(h)

Hapus(v) berjalan dalam O(h) dimana h adalah tinggi dari BST tersebut. Penghapusan kasus 3 (penghapusan dari sebuah simpul dengan dua anak adalah yang 'terberat' tetapi tetap tidak lebih dari O(h)).


Seperti yang anda harusnya mengerti sekarang, h bisa setinggi O(N) di BST normal seperti yang ditunjukkan di contoh 'miring kanan' diatas. Jika kita memanggil Remove(FindMax()), yaitu kita menghapus bilangan bulat terbesar sekarang, kita akan pergi dari akar kebawah ke daun terakhir dalam waktu O(N) sebelum kita menghapusnya — tidak efisien.

11. Buat BST

Untuk membuat hidup anda lebih mudah dalam 'Mode Eksplorasi', anda dapat membuat BST baru menggunakan beberapa opsi-opsi ini:

  1. BST kosong (anda kemudian dapat memasukkan beberapa bilangan-bilangan bulat satu per satu),
  2. Dua Contoh-Contoh Kuliah Maya yang anda telah lihat beberapa kali sejauh ini,
  3. BST acak (yang sangat tidak mungkin sangat tinggi),
  4. BST miring kiri/kanan (BST tinggi dengan N simpul dan N-1 edge seperti dalam senarai berantai, untuk menunjukkan performa terburuk dari operasi-operasi BST; opsi ini tidak tersedia dalam mode pohon AVL).

12. Selingan

Kita berada di posisi separuh dari penjelasan modul BST ini. Sejauh ini kita melihat bahwa banyak operasi-operasi ADT Tabel berjalan dalam O(h) dan h bisa setinggi N-1 sisi-sisi seperti contoh 'Skew Kiri' yang ditunjukkan diatas — ini tidak efisien :(...


Jadi, adakah cara untuk membuat BST-BST kita 'tidak terlalu tinggi'?


Catatan: Jika anda ingin mempelajari bagaimana operasi-operasi BST ini diimplementasikan dalam program nyata, anda dapat mengunduh BSTDemo.cpp ini.

12-1. Cobalah Mode Eksplorasi

Pada titik ini, kami mendorong anda untuk menekan tombol [Esc] atau mengklik tombol X di sisi bawah kanan dari slide Kuliah Maya untuk memasuki 'Mode Eskplorasi' dan mencoba berbagai operasi-operasi BST sendiri untuk memperkuat pemahaman anda tentang struktur data yang serba guna ini.


Ketika anda siap untuk melanjutkan dengan penjelasan dari BST yang seimbang (kami menggunakan Pohon AVL sebagai contoh), tekan tombol [Esc] lagi atau pindah mode kembali ke 'Mode Kuliah Maya' dari menu drop down di sisi kanan-atas. Lalu, gunakan daftar drop down pemilihan slide untuk melanjutkan dari slide 12-1 ini.

13. BST Seimbang

Kita telah melihat dari slide-slide sebelumnya bahwa kebanyakan dari operasi-operasi BST kita kecuali penjelajahan Inorder berjalan dalam O(h) dimana h adalah tinggi dari BST yang bisa setinggi N-1.


Kita akan melanjutkan diskusi kita dengan konsep BST yang seimbang sehingga h = O(log N).

13-1. Pohon AVL

Ada beberapa implementasi-implementasi yang diketahui tentang BST yang seimbang, terlalu banyak untuk divisualisasikan dan dijelaskan satu persatu di VisuAlgo.


Kami memfokuskan ke Pohon AVL (Adelson-Velskii & Landis, 1962) yang dinamai berdasarkan penemunya: Adelson-Velskii dan Landis.


Implementasi-implementasi BST yang seimbang lainnya (kurang lebih sama baiknya atau sedikit lebih baik performanya dalam faktor-konstan) adalah: Red-Black Tree, B-trees/2-3-4 Tree (Bayer & McCreight, 1972), Splay Tree (Sleator and Tarjan, 1985), Skip Lists (Pugh, 1989), Treaps (Seidel and Aragon, 1996), dsb.

13-2. Atribut BST Ekstra: tinggi(v)

Untuk memfasilitasi implementasi Pohon AVL, kita perlu mengaugmentasi — menambahkan informasi/atribut lebih — setiap simpul BST.


Untuk setiap simpul v, kita mendefinisikan tinggi(v): Jumlah sisi-sisi dari jalur mulai dari simpul v kebawah sampai daun yang terdalam. Atribut ini disimpan disetiap simpul sehingga kita dapat mengakses tinggi dari sebuah simpul dalam O(1) tanpa harus menghitung ulang nilai tersebut setiap kalinya.

13-3. Definisi Formal dari tinggi(v)

Secara formal:

v.height = -1 (jika v adalah pohon kosong)
v.height = max(v.left.height, v.right.height) + 1 (lainnya)
Tinggi dari BST adalah: root.height.


Pada BST contoh diatas, tinggi(11) = tinggi(32) = tinggi(50) = tinggi(72) = tinggi(99) = 0 (karena semuanya adalah dedaunan). tinggi(29) = 1 karena ada satu sisi yang menghubungkannya dengan daun satu-satunya 32.

13-4. Kuis Mini

Quiz: What are the values of height(20), height(65), and height(41) on the BST above?

height(41) = 3
height(20) = 2
height(65) = 2
height(41) = 4
height(65) = 3
height(20) = 3

13-5. Batas Bawah dari Tinggi BST

Jika kita memiliki N elemen/item/kunci-kunci dalam BST kita, batas bawah tinggi h > log2 N jika kita bisa memasukkan N elemen-elemen tersebut dalam urutan yang sempurna sehingga BSTnya seimbang dengan sempurna.


Lihat contoh diatas untuk N = 15 (sebuah BST sempurna yang sangat jarang bisa didapatkan dalam kehidupan nyata — coba masukkan bilangan bulat apapun dan BST tersebut tidak akan sempurna lagi).

13-6. Penurunan dari Batas Bawah

N ≤ 1 + 2 + 4 + ... + 2h
N ≤ 20 + 21 + 22 + … + 2h
N < 2h+1 (jumlah dari deret geometris)
log2 N < log2 2h+1
log2 N < (h+1) * log2 2 (log2 2 = 1)
h > (log2 N)-1 (manipulasi aljabar)
h > log2 N

13-7. Batas Atas dari Tinggi BST

Jika kita memiliki N element/item/kunci dalam BST kita, batas atas dari tinggi h < N jika kita memasukan elemen-elemen tersebut dalam urutan menaik (untuk mendapatkan BST miring kanan seperti yang ditunjukkan diatas).


Tinggi dari BST tersebut adalah h = N-1, jadi kita punya h < N.


Diskusi: Apakah anda tahu bagaimana caranya membuat BST miring kiri?

13-8. Solusinya

[This is a hidden slide]

13-9. Batasan Gabungan

Kita telah melihat bahwa kebanyakan operasi-operasi BST adalah dalam O(h) dan menggabungkan batas bawah dan batas atas dari h, kita mendapatkan log2 N < h < N.


Ada perbedaan yang dramatis diantara log2 N dan N dan kita telah melihat dari diskusi tentang batas bawah bahwa mendapatkan BST sempurna (pada setiap waktu) adalah hampir tidak mungkin...


Jadi bisakah kita mendapatkan BST yang memiliki tinggi lebih dekat ke log2 N, yaitu c * log2 N, untuk faktor konstanta kecil c? Jika kita bisa, maka operasi-operasi BST yang berjalan dalam O(h) sebenarnya berjalan dalam O(log N)...

14. Pohon AVL

Memperkenalkan Pohon AVL, ditemukan oleh dua orang penemu Rusia (Soviet): Georgy Adelson-Velskii dan Evgenii Landis, jauh di masa lalu, tahun 1962.


Dalam Pohon AVL, kita nantinya akan melihat bahwa tingginya h < 2 * log N (analisa yang lebih ketat ada, tetapi kita akan menggunakan analisa yang lebih mudah di VisuAlgo dimana c = 2). Oleh karena itu, hampir semua operasi-operasi Pohon AVL berjalan dalam waktu O(log N) — efisien.


Operasi-operasi pemutakhiran Masukkan(v) dan Hapus(v) mungkin merubah tinggi h dari Pohon AVL, tetapi kita akan melihat operasi-operasi rotasi untuk menjaga tinggi dari Pohon AVL tetap pendek.

14-1. Langkah 1: Menjaga tinggi(v) secara Efisien

Untuk mendapatkan performa yang efisien, kita tidak akan menjaga atribut tinggi(v) lewat metode rekursi O(N) setiap kali ada operasi pemutakhiran (Masukkan(v)/Hapus(v)).


Tetapi, kita menghitung dalam O(1): x.height = max(x.left.height, x.right.height) + 1 di akhir dari operasi Masukkan(v)/Hapus(v) karena hanya tinggi dari simpul-simpul sepanjang jalur pemasukkan/penghapusan mungkin terpengaruh. Sehingga, hanya O(h) simpul mungkin merubah atribut tinggy(v) dan dalam Pohon AVL, h < 2 * log N.


Coba Insert(37) pada contoh Pohon AVL (abaikan rotasi yang terjadi untuk saat ini, kita akan kembali ke topik itu di beberapa slide berikutnya). Sadarlah bahwa hanya sedikit simpul-simpul sepanjang jalur pemasukkan: {41,20,29,32} menambah tinggi mereka sebesar +1 dan semua simpul-simpul yang lain tidak merubah tinggi mereka.

14-2. Langkah 2: Definisikan Invarian Pohon AVL

Mari definisikan invarian (properti yang tidak akan berganti) Pohon AVL penting berikut: Sebuah simpul v dikatakan tinggi-seimbang jika |v.left.height - v.right.height| ≤ 1.


Sebuah BST dikatakan tinggi-seimbang sesuai invarian diatas jika semua simpul dalam BST adalah tinggi-seimbang. BST seperti itu disebut sebagai Pohon AVL, seperti pada contoh yang ditunjukkan diatas.


Ambil suatu waktu untuk berhenti disini dan cobalah masukkan beberapa simpul-simpul baru secara acak atau menghapus beberapa simpul-simpul yang sudah ada secara acak. Apakah BST yang dihasilkan tetap bisa dibilang tinggi-seimbang?

14-3. Pembuktian - 1

Adelson-Velskii dan Landis mengklaim bahwa dalam Pohon AVL (sebuah BST yang tinggi-seimbang yang memenuhi invarian Pohon AVL) dengan N simpul-simpul memiliki tinggi h < 2 * log2 N.


Pembuktiannya berdasarkan konsep dari Pohon AVL dengan ukuran-minimum dengan tinggi tertentu h.


Biarlah Nh adalah jumlah minimum dari simpul-simpul dari sebuah Pohon AVL yang tinggi-seimbang dengan tinggi h.


Beberapa nilai-nilai pertama dari Nh adalah N0 = 1 (sebuah simpul akar tunggal), N1 = 2 (sebuah simpul akar dengan satu anak kiri atau satu anak kanan saja), N2 = 4, N3 = 7, N4 = 12, N5 = 20 (lihat gambar latar belakang), dan selanjutnya (lihat dua slide selanjutnya).

14-4. Pembuktian - 2

Kita tahu bahwa pada Pohon AVL lainnya dengan N simpul (tidak harus yang berukuran paling-kecil), kita punya N ≥ Nh.


Proof-2

Pada gambar dibelakang, kita punya N5 = 20 simpul tetapi kita tahu bahwa kita dapat memasukkan 43 simpul lagi (sampai N = 63) sebelum kita memiliki pohon biner sempurna dengan tinggi h = 5.

14-5. Pembuktian - 3

Nh = 1 + Nh-1 + Nh-2 (formula untuk pohon AVL ukuran-minimum dengan tinggi h)
Nh > 1 + 2*Nh-2 (as Nh-1 > Nh-2)
Nh > 2*Nh-2 (tentu saja)
Nh > 4*Nh-4 (recursif)
Nh > 8*Nh-6 (langkah rekursif lainnya)
... (kita cuma bisa melakukan ini h/2 kali, asumsi h awal adalah genap)
Nh > 2h/2*N0 (kita mencapai kasus dasar)
Nh > 2h/2 (karena N0 = 1)
Proof-3

14-6. Pembuktian - 4

N ≥ Nh > 2h/2 (menggabungkan dua slide sebelumnya)
N > 2h/2
log2(N) > log2(2h/2) (log2 di kedua sisi)
log2(N) > h/2 (penyederhanaan formula)
2 * log2(N) > h or h < 2 * log2(N)
h = O(log(N)) (kesimpulan final)
Proof-4

14-7. Langkah 3: Menjaga Invarian

Lihat BST contoh kembali. Lihatlah bahwa semua simpul-simpul adalah tinggi-seimbang, sebuah Pohon AVL.


Untuk dengan cepat mendeteksi apabila sebuah simpul v adalah tinggi seimbang atau tidak, kita memodifikasi invarian Pohon AVL (yang memiliki fungsi absolut didalamnya) menjadi: bf(v) = v.left.height - v.right.height.


Sekarang cobalah Insert(37) pada contoh Pohon AVL lagi. Beberapa simpul-simpul sepanjang jalur pemasukkan: {41,20,29,32} menambah tinggi mereka sebesar +1. Simpul-simpul {29,20} tidak akan lagi tinggi-seimbang setelah pemasukkan ini (dan akan dirotasi nantinya — akan dibahas di beberapa slide selanjutnya), yaitu bf(29) = -2 dan bf(20) = -2 juga. Kita perlu untuk mengembalikan keseimbangan.

14-8. Memperkenalkan Rotasi Pohon

Tree Rotation

Lihatlah gambar diatas. Memanggil rotateRight(Q) pada gambar dikiri akan menghasilkan gambar dikanan. Memanggil rotateLeft(P) pada gambar dikanan akan menghasilkan gambar dikiri lagi.


rotateRight(T)/rotateLeft(T) hanya bisa dipanggil jika T masing-masing memiliki anak kiri/kanan.


Rotasi Pohon menjaga properti BST. Sebelum rotasi, P ≤ B ≤ Q. Setelah rotasi, lihatlah bahwa sub-pohon yang berakar pada B (jika ada) berpindah orangtua, tetapi P ≤ B ≤ Q tidak berubah.

14-9. Pseudo-code Rotasi Pohon O(1) yang Tidak-Trivial

BSTVertex rotateLeft(BSTVertex T) // pra-syarat: T.right != null
BSTVertex w = T.right // rotateRight adalah kopi terbalik dari ini
w.parent = T.parent // metode ini susah bagi pemula
T.parent = w
T.right = w.left
if (w.left != null) w.left.parent = T
w.left = T
// mutakhirkan tinggi dari T dan lalu w disini
return w

14-10. Empat Kasus-Kasus Penyeimbangan

Four Cases

Pada dasarnya, hanya ada empat kasus tidak seimbang ini. Kita menggunakan Rotasi(-rotasi) Pohon untuk berurusan dengan keempat kasus tersebut.

14-11. Masukkan(v) dalam Pohon AVL

  1. Masukkan v seperti di BST normal,
  2. Jalan keatas di Pohon AVL dari titik pemasukkan kembali ke akar dan pada setiap langkah, kita memutakhirkan tinggi dan faktor keseimbangan dari simpul-simpul yang bersangkutan:
    1. Berhenti pada simpul pertama yang tidak-seimbang (+2 atau -2), jika ada,
    2. Gunakan satu dari keempat kasus-kasus rotasi pohon untuk menyeimbangkannya lagi, contoh: cobalah Insert(37) pada contoh diatas dan sadari bahwa ketika kita memanggil rotateLeft(29) sekali, kita akan membereskan isu ketidak-seimbangan.

Diskusi: Apakah ada kasus-kasus rotasi pohon lainnya untuk operasi Masukkan(v) pada Pohon AVL?

14-12. Jawabannya

[This is a hidden slide]

14-13. Hapus(v) dalam Pohon AVL

  1. Cukup hapus v seperti dalam BST normal (satu dari tiga kasus-kasus penghapusan),
  2. Jalan keatas Pohon AVL dari titik penghapusan kembali ke akar dan pada setiap langkah, kita memutakhirkan tinggi dan faktor keseimbangan dari setiap simpul-simpul yang terpengaruh:
    1. Sekarang untuk setiap simpul yang diluar-keseimbangan (+2 atau -2), kita menggunakan satu dari keempat kasus-kasus rotasi pohon untuk menyeimbangkan simpul-simpul tersebut (bisa lebih dari satu) lagi.

Perbedaan utama dibandingkan dengan Masukkan(v) dalam pohon AVL adalah kita mungkin men-trigger satu dari empat kasus-kasus penyeimbangan yang mungkin beberapa kali, tetapi tidak lebih dari h = O(log N) kali :O, cobalah Remove(7) pada contoh diatas untuk melihat dua reaksi berantai rotateRight(6) dan lalu rotateRight(16)+rotateLeft(8).

14-14. Kesimpulan Pohon AVL

[This is a hidden slide]

15. Tambahan-Tambahan

Kami akan mengakhiri modul ini dengan beberapa hal-hal yang lebih menarik tentang BST dan BST yang seimbang (terutama Pohon AVL).

15-1. Dua Operasi BST Extra Tersebut

[This is a hidden slide]