>

>
1x
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.

Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.

🕑

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 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.

🕑

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.


Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). 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.

🕑

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.


Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, / to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.

🕑

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

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

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
🕑

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

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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.

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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

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.

🕑

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

🕑

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

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.

🕑

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.

🕑

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

🕑

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

🕑

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.

🕑

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

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.

🕑

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.

🕑

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.

🕑

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.

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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

🕑

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.

🕑

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

🕑

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
9
10
8


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

🕑

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

🕑

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.

🕑

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.

🕑

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.

🕑

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

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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.

🕑

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

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.

🕑

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.

🕑

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

🕑

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.

🕑

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.

🕑

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.

🕑

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

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

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

🕑
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
🕑

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?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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

🕑

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.

🕑

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.

🕑

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?

🕑

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

🕑

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.

🕑
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
🕑
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
🕑

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.

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

🕑
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
🕑
Four Cases

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

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

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

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

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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.

🕑

Kami juga memiliki beberapa masalah-masalah pemrograman yang agak 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, Java TreeMap/TreeSet, atau OCaml Map/Set jika itu mempermudah implementasi anda (catat bahwa Python tidak mempunyai implementasi built-in dari BST seimbang).

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.


You have reached the last slide. Return to 'Exploration Mode' to start exploring!

Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.

🕑

Buat

Masukkan

Hapus

Predec-/Succ-essor

Tree Traversal

>

Kosong

Unbalanced Example

Balanced Example

Acak

Miring ke Kiri

Miring ke Kanan

v =

Lakukan

v =

Lakukan

v =

Cari Pendahulu

Cari Penerus

Inorder

Preorder

Postorder

We use cookies to improve our website.
By clicking ACCEPT, you agree to our use of Google Analytics for analysing user behaviour and improving user experience as described in our Privacy Policy.
By clicking reject, only cookies necessary for site functions will be used.

ACCEPT REJECT
Tentang Tim Syarat Guna Kebijakan Privasi

Tentang

VisuAlgo digagas pada tahun 2011 oleh Dr Steven Halim sebagai alat untuk membantu murid-muridnya mengerti struktur-struktur data dan algoritma-algoritma, dengan memampukan mereka untuk mempelajari dasar-dasarnya 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 temannya Dr Suhendry Effendy) 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/setara, CS2040/setara, CS3230, CS3233, dan CS4234), 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. Tetapi, kami sedang bereksperimen dengan versi mobil (kecil) dari VisuAlgo yang akan siap pada April 2022.


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 struktur-struktur data dan algoritma-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 12 modul visualisasi yang lainnya sehingga setiap setiap modul visualisasi di VisuAlgo mempunyai komponen kuis online.


Kami telah menerjemahkan halaman-halaman VisuALgo ke tiga bahasa-bahasa utama: Inggris, Mandarin, dan Indonesia. Saat ini, kami juga telah menulis catatan-catatan publik tentang VisuAlgo dalam berbagai bahasa:

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, Senior 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

Murid-Murid Proyek Tahun Terakhir/UROP 5 (Aug 2021-Dec 2022)
Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long

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 is free of charge for Computer Science community on earth. If you like VisuAlgo, the only "payment" that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Facebook/Twitter/Instagram/TikTok posts, course webpages, blog reviews, emails, etc.

If you are a data structure and algorithm student/instructor, you are allowed to use this website directly for your classes. If you take screen shots (videos) from this website, you can use the screen shots (videos) elsewhere as long as you cite the URL of this website (https://visualgo.net) and/or list of publications below as reference. However, you are NOT allowed to download VisuAlgo (client-side) files and host it on your own website as it is plagiarism. As of now, we do NOT allow other people to fork this project and create variants of VisuAlgo. Using the offline copy of (client-side) VisuAlgo for your personal usage is fine.

Note that VisuAlgo's online quiz component is by nature has heavy server-side component and there is no easy way to save the server-side scripts and databases locally. Currently, the general public can only use the 'training mode' to access these online quiz system. Currently the 'test mode' is a more controlled environment for using these randomly generated questions and automatic verification for real examinations in NUS.

List of Publications

This work has been presented briefly at the CLI Workshop at the ICPC World Finals 2012 (Poland, Warsaw) and at the IOI Conference at IOI 2012 (Sirmione-Montichiari, Italy). You can click this link to read our 2012 paper about this system (it was not yet called VisuAlgo back in 2012) and this link for the short update in 2015 (to link VisuAlgo name with the previous project).

This work is done mostly by my past students. 

Bug Reports or Request for New Features

VisuAlgo is not a finished project. Dr Steven Halim is still actively improving VisuAlgo. If you are using VisuAlgo and spot a bug in any of our visualization page/online quiz tool or if you want to request for new features, please contact Dr Steven Halim. His contact is the concatenation of his name and add gmail dot com.

Kebijakan Privasi

Versi 1.1 (Dimutakhirkan Jum, 14 Jan 2022).

Pemberitahuan kepada semua pengunjung: Kami saat ini menggunakan Google Analytics untuk mendapatkan pengertian garis besar tentang pengunjung-pengunjung situs kami. Kami sekarang memberikan opsi kepada pengguna untuk Menerima atau Menolak pelacak ini.

Sejak Rabu, 22 Des 2021, hanya staff-staff/murid-murid National University of Singapore (NUS) dan dosen-dosen Ilmu Komputer diluar dari NUS yang telah menulis kepada Steven dapat login ke VisuAlgo, orang-orang lain di dunia harus memakai VisuAlgo sebagai pengguna anonim yang tidak benar-benar terlacak selain apa yang dilacak oleh Google Analytics.

Untuk murid-murid NUS yang mengambil mata kuliah yang menggunakan VisuAlgo: Dengan menggunakan akun VisuAlgo (sebuah tupel dari alamat email NUS resmi, nama murid resmi NUS seperti dalam daftar kelas, dan sebuah kata sandi yang dienkripsi pada sisi server — tidak ada data personal lainnya yang disimpan), anda memberikan ijin kepada dosen modul anda untuk melacak pembacaan slide-slide kuliah maya dan kemajuan latihan kuis online yang dibutuhkan untuk menjalankan modul tersebut dengan lancar. Akun VisuAlgo anda akan juga dibutuhkan untuk mengambil kuis-kuis VisuAlgo online resmi sehingga memberikan kredensial akun anda ke orang lain untuk mengerjakan Kuis Online sebagai anda adalah pelanggaran akademis.. Akun pengguna anda akan dihapus setelah modul tersebut selesai kecuali anda memilih untuk menyimpan akun anda (OPT-IN). Akses ke basis data lengkap dari VisuAlgo (dengan kata-kata sandi terenkripsi) dibatasi kepada Steven saja.

Untuk murid-murid NUS lainnya, anda dapat mendaftarkan sendiri sebuah akun VisuAlgo (OPT-IN).

Untuk dosen-dosen Ilmu Komputer di seluruh dunia yang telah menulis kepada Steven, sebuah akun VisuAlgo (alamat email (bukan-NUS), anda dapat menggunakan nama panggilan apapun, dan kata sandi terenkripsi) dibutuhkan untuk membedakan kredensial online anda dibandingkan dengan orang-orang lain di dunia. Akun anda akan dilacak seperti seorang murid NUS biasa diatas tetapi akun anda akan mempunya fitur-fiture spesifik untuk dosen-dosen Ilmu Komputer, yaitu kemampuan untuk melihat slide-slide tersembunyi yang berisi jawaban-jawaban (menarik) dari pertanyaan-pertanyaan yang dipresentasikan di slide-slide sebelumnya sebelum slide-slide tersembunyi tersebut. Anda juga dapat mengakses setingan Susah dari Kuis-Kuis Online VisuAlgo. Anda dapat dengan bebas menggunakan materi-materia untuk memperkaya kelas-kelas struktur-struktur data dan algoritma-algoritma anda. Catatan: Mungkin ada fitur-fitur khusus tambahan untuk dosen Ilmu Komputer di masa mendatang.

Untuk siapapun dengan akun VisuAlgo, anda dapat membuang akun anda sendiri bila anda tidak mau lagi diasosiasikan dengan tool VisuAlgo ini.