7    VisuAlgo.net / /bst Login Pohon Biner Terurut Pohon AVL
Mode Eksplorasi ▿

>

>
pelan
cepat
go to beginning previous frame pause play next frame go to end

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.


Klik 'Berikut' (di sisi kanan atas)/tekan 'Page Down' untuk berpindah ke e-Lecture slide berikutnya, gunakan daftar drop down/tekan tombol 'Space' untuk meloncat ke slide tertentu, atau Klik 'X' (di sisi bawah kanan)/tekan 'Esc' untuk pergi ke mode Penjelajahan.


Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
Please login if you are a repeated visitor or register for an (optional) free account first.

X Esc
Berikut PgDn

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).


Pro-tip: Since you are not logged-in, you may be a first time visitor who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown] to advance to the next slide, [PageUp] to go back to the previous slide, [Esc] to toggle between this e-Lecture mode and exploration mode.

X Esc
Sebelum PgUp
Berikut PgDn

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.


Another pro-tip: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2017). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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).
X Esc
Sebelum PgUp
Berikut PgDn

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).
X Esc
Sebelum PgUp
Berikut PgDn

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
X Esc
Sebelum PgUp
Berikut PgDn

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]?

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

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?

Yes
No


Diskusi: Kenapa?

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

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 is no point, so this BST module can be ignored
There are valid reasons, which are ____


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

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

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.
X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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 dan kita harus secara konsisten menaruh bilangan-bilangan bulat yang sama nilainya dengan X ke satu sub-pohon saja (tidak secara sembarangan).

X Esc
Sebelum PgUp
Berikut PgDn

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).
X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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(15) (ditemukan setelah hanya 1 pembandingan), Search(7) (ditemukan setelah 3 pembandingan), Search(21) (tidak ditemukan setelah 3 pembandingan).

X Esc
Sebelum PgUp
Berikut PgDn

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).

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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).
X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

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}}.

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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).

X Esc
Sebelum PgUp
Berikut PgDn

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:

The height cannot be determined
8
9
10


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

X Esc
Sebelum PgUp
Berikut PgDn

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).

X Esc
Sebelum PgUp
Berikut PgDn

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 usah O(h) yang mirip dengan usaha pencarian.

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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?
X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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).
X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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


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

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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) = 3
height(65) = 2
height(20) = 3
height(41) = 4
X Esc
Sebelum PgUp
Berikut PgDn

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).

X Esc
Sebelum PgUp
Berikut PgDn
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
X Esc
Sebelum PgUp
Berikut PgDn

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?

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

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)...

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn

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?

X Esc
Sebelum PgUp
Berikut PgDn

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).

X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn
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
X Esc
Sebelum PgUp
Berikut PgDn
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
X Esc
Sebelum PgUp
Berikut PgDn

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.

X Esc
Sebelum PgUp
Berikut PgDn
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.

X Esc
Sebelum PgUp
Berikut PgDn
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
X Esc
Sebelum PgUp
Berikut PgDn
Four Cases

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

X Esc
Sebelum PgUp
Berikut PgDn
  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?

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn
  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).

X Esc
Sebelum PgUp
Berikut PgDn

Sekarang kita telah melihat bagaimana Pohon AVL mendefinisikan invarian tinggi-seimbang, menjaganya untuk semua simpul-simpul pada operasi-operasi pemutakhiran Masukkan(v) dan Hapus(v), dan sebuah pembuktian bahwa Pohon AVL memiliki h < 2 * log N.


Oleh karena itu, semua operasi-operasi BST (baik operasi-operasi pemutakhiran dan pertanyaan kecuali Penjelajahan Inorder) yang telah kita pelajari selama ini, jika mereka memiliki kompleksitas waktu sebesar O(h), mereka memiliki kompleksitas waktu sebesar O(log N) jika kita menggunakan versi Pohon AVL dari BST.


Ini adalah akhir dari Kuliah Maya ini, tetapi silahkan pindah ke 'Mode Eksplorasi' dan cobalah memanggil beberapa Masukkan(v) dan Hapus(v) dalam mode Pohon AVL untuk memperkuat pengertian anda tentang struktur data ini.


Catatan: Jika anda mau mempelajari bagaimana operasi-operasi Pohon AVL (rotasi) yang sepertinya kompleks diimplementasikan dalam sebuah program nyata, anda dapat mengunduh AVLDemo.cpp ini (harus digunakan bersama dengan BSTDemo.cpp).

X Esc
Sebelum PgUp
Berikut PgDn

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

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn

Untuk berbagai pertanyaan-pertanyaan lebih lanjut tentang struktur data ini, silahkan latihan pada modul latihan BST/AVL (tidak perlu login).


Tetapi, untuk pengguna-pengguna yang telah teregistrasi, anda sebaiknya login dan lalu pergi ke Halaman Latihan Utama untuk secara ofisial menyelesaikan modul ini dan keberhasilan tersebut akan dicatat dalam akun pengguna anda.

X Esc
Sebelum PgUp
Berikut PgDn

Kami juga memiliki beberapa masalah-masalah pemrograman yang sepertinya membutuhkan penggunaan struktur data BST yang seimbang ini (seperti Pohon AVL): Kattis - compoundwords dan Kattis - baconeggsandspam.


Cobalah mereka untuk mengkonsolidasikan dan mengembangkan pemahaman anda tentang struktur data ini. Anda diijinkan untuk menggunakan C++ STL map/set atau Java TreeMap/TreeSet jika itu mempermudah implementasi anda.

X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn
Selagi aksi dijalankan, tiap langkahnya akan dijelaskan pada panel status.
X Esc
Sebelum PgUp
Berikut PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Sebelum PgUp
Berikut PgDn
Kendalikan animasi dengan tombol kendali! Terdapat pula shortcut melalui keyboard:
Spasi: play/pause/replay
Panah kanan/kiri: maju ke depan/belakang
-/+: turunkan/tingkatkan kecepatan

X Esc
Sebelum PgUp
Berikut PgDn
Kembali ke 'Mode Eksplorasi' untuk memulai eksplorasi!

Harap diingat bahwa jika anda menemukan bug pada visualisasi ini atau bila anda ingin meminta fitur / visualisasi baru, jangan segan-segan untuk menghubungi pemimpin proyek ini: Dr Steven Halim melalui alamat emailnya: stevenhalim at gmail dot com.
X Esc
Sebelum PgUp

Buat

Masukkan(v)

Hapus(v)

Pen-erus/dahulu(v)

Traversal Inorder

>

Kosong

Unbalanced Example

Balanced Example

Acak

Miring ke Kiri

Miring ke Kanan

v =

Lakukan

v =

Lakukan

v =

Cari Pendahulu

Cari Penerus

Tentang Tim Syarat Guna

Tentang

VisuAlgo digagas pada tahun 2011 oleh Dr Steven Halim sebagai alat untuk membantu murid-muridnya mengerti struktur data dan algoritma dengan memampukan mereka untuk mempelajari dasar-dasar struktur data dan algoritma secara otodidak dan dengan kecepatan mereka sendiri.


VisuAlgo mempunya banyak algoritma-algoritma tingkat lanjut yang dibahas didalam buku Dr Steven Halim ('Competitive Programming', yang ditulis bersama adiknya Dr Felix Halim) dan lebih lagi. Hari ini, beberapa dari visualisasi/animasi algoritma-algoritma tingkat lanjut ini hanya ditemukan di VisuAlgo.


Meskipun pada khususnya didesain untuk murid-murid National University of Singapore (NUS) yang mengambil berbagai kelas-kelas struktur data dan algoritma (contoh: CS1010, CS1020, CS2010, CS2020, CS3230, dan CS3233), sebagai pendukung pembelajaran online, kami berharap bahwa orang-orang di berbagai belahan dunia menemukan visualisasi-visualisasi di website ini berguna bagi mereka juga.


VisuAlgo tidak didesain untuk layar sentuh kecil (seperti smartphones) dari awalnya karena kami harus membuat banyak visualisasi-visualisasi algoritma kompleks yang membutuhkan banyak pixels dan gestur klik-dan-tarik untuk interaksinya. Resolusi layar minimum untuk pengalaman pengguna yang lumayan adalah 1024x768 dan hanya halaman utama VisuAlgo yang secara relatif lebih ramah dengan layar kecil.


VisuAlgo adalah proyek yang sedang terus berlangsung dan visualisasi-visualisasi yang lebih kompleks sedang dibuat.


Perkembangan yang paling menarik adalah pembuatan pertanyaan otomatis (sistem kuis online) yang bisa dipakai oleh murid-murid untuk menguji pengetahuan mereka tentang dasar-dasar struktur data dan algoritma. Pertanyaan-pertanyaan dibuat secara acak dengan semacam rumus dan jawaban-jawaban murid-murid dinilai secara instan setelah dikirim ke server penilai kami. Sistem kuis online ini, saat sudah diadopsi oleh banyak dosen Ilmu Komputer diseluruh dunia, seharusnya bisa menghapuskan pertanyaan-pertanyaan dasar tentang struktur data dan algoritma dari ujian-ujian di banyak Universitas. Dengan memberikan bobot kecil (tapi tidak kosong) supaya murid-murid mengerjakan kuis online ini, seorang dosen Ilmu Komputer dapat dengan signifikan meningkatkan penguasaan materi dari murid-muridnya tentang pertanyaan-pertanyaan dasar ini karena murid-murid mempunyai kesempatan untuk menjawab pertanyaan-pertanyaan ini yang bisa dinilai secara instan sebelum mereka mengambil kuis online yang resmi. Mode latihan saat ini mempunyai pertanyaan-pertanyaan untuk 12 modul visualisasi. Kami akan segera menambahkan pertanyaan-pertanyaan untuk 8 modul visualisasi lainnya sehingga setiap every modul visualisasi di VisuAlgo mempunyai komponen kuis online.


Cabang pengembangan aktif lainnya adalah sub-proyek penerjemahan dari VisuAlgo. Kami mau menyiapkan basis data kosa kata Ilmu Komputer dalam bahasa Inggris yang digunakan di sistem VisuAlgo. Ini adalah pekerjaan besar yang membutuhkan crowdsourcing. Saat sistem tersebut siap, kami akan mengundang beberapa dari anda untuk berkontribusi, terutama bila bahasa Inggris bukan bahasa ibu anda. Saat ini, kami juga telah menulis catatan-catatan publik tentang VisuAlgo dalam berbagai bahasa:
zh, id, kr, vn, th.

Tim

Pemimpin & Penasihat Proyek (Jul 2011-sekarang)
Dr Steven Halim, Senior Lecturer, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Software Engineer, Google (Mountain View)

Murid-Murid S1 Peniliti 1 (Jul 2011-Apr 2012)
Koh Zi Chun, Victor Loh Bo Huai

Murid-Murid Proyek Tahun Terakhir/UROP 1 (Jul 2012-Dec 2013)
Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy

Murid-Murid Proyek Tahun Terakhir/UROP 2 (Jun 2013-Apr 2014)
Rose Marie Tan Zhao Yun, Ivan Reinaldo

Murid-Murid S1 Peniliti 2 (May 2014-Jul 2014)
Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

Murid-Murid Proyek Tahun Terakhir/UROP 3 (Jun 2014-Apr 2015)
Erin Teo Yi Ling, Wang Zi

Murid-Murid Proyek Tahun Terakhir/UROP 4 (Jun 2016-Dec 2017)
Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir

List of translators who have contributed ≥100 translations can be found at statistics page.

Ucapan Terima Kasih
Proyek ini dimungkinkan karena Hibah Pengembangan Pengajaran dari NUS Centre for Development of Teaching and Learning (CDTL).

Syarat Guna

VisuAlgo bebas biaya untuk komunitas Ilmu Komputer di dunia. Jika anda menyukai VisuAlgo, satu-satunya pembayaran yang kami minta dari anda adalah agar anda menceritakan keberadaan VisuAlgo kepada murid-murid/dosen-dosen Ilmu Komputer yang anda tahu =) lewat Facebook, Twitter, situs mata kuliah, ulasan di blog, email, dsb.


Jika anda adalah murid/dosen struktur data dan algoritma, anda diijinkan untuk menggunakan situs ini secara langsung di kelas-kelas anda. Jika anda mengambil screen shots (video-video) dari situs ini, anda dapat menggunakan screen shots (video-video) tersebut ditempat lain asalkan anda menyebut URL dari situs ini (http://visualgo.net) dan/atau daftar publikasi dibawah ini sebagai referensi. Tetapi, anda TIDAK diijinkan untuk mengunduh berkas-berkas VisuAlgo (sisi-klien) dan memasangnya di situs anda sendiri karena itu dikategorikan sebagai plagiat. Saat ini, kami TIDAK mengijinkan orang lain untuk membuat cabang/varian dari proyek VisuAlgo ini. Menggunakan kopi offline (sisi-klien) dari VisuAlgo untuk kepentingan pribadi diijinkan.


Ingat bahwa komponen kuis online dari VisuAlgo secara natur membutuhkan sisi-server dan tidak bisa dengan mudah disimpan di komputer lokal. Saat ini, publik hanya bisa menggunkaan 'mode latihan' untuk mengakses sistem kuis online. Saat ini, 'mode ujian' adalah sistem untuk mengakses pertanyaan-pertanyaan acak ini yang digunakan untuk ujian resmi di NUS. Dosen-dosen Ilmu Komputer yang lain harus menghubungi Steven jika anda mau mencoba 'mode ujian' tersebut.


Dafatar Publikasi


Karya ini telah dipresentasikan singkat pada CLI Workshop sewaktu ACM ICPC World Finals 2012 (Poland, Warsaw) dan pada IOI Conference di IOI 2012 (Sirmione-Montichiari, Italy). Anda bisa mengklik link ini untuk membaca makalah kami tahun 2012 tentang sistem ini (yang belum disebut sebagai VisuAlgo pada tahun 2012 tersebut).


Karya ini dibuat denbgan bantuan bekas murid-murid saya. Laporan-laporan proyek yang cukup mutakhir bisa dibaca disini: Erin, Wang Zi, Rose, Ivan.


Laporan Bug atau Meminta Fitur Baru


VisuAlgo bukanlah proyek yang sudah selesai. Dr Steven Halim masih aktif dalam mengembangkan VisuAlgo. Jika anda adalah pengguna VisuAlgo dan menemukan bug di halaman visualisasi/sistem kuis online atau jika anda mau meminta fitur baru, silahkan hubungi Dr Steven Halim. Alamat emailnya adalah gabungan dari namanya dan tambahkan gmail titik com.