>

>
1x
go to beginning previous frame pause play next frame go to end

A Binary Search Tree (BST) is a specialized type of binary tree in which each vertex can have up to two children. This structure adheres to the BST property, stipulating that every vertex in the left subtree of a given vertex must carry a value smaller than that of the given vertex, and every vertex in the right subtree must carry a value larger. This visualization implements 'multiset' property: Although all keys remain distinct integers, information of duplicated integers are stored as a frequency attribute (only shown for keys that appear more than once). For a demonstration, use the Search(7) function to animate the search for a random value within the range of 1 to 99 in the randomly generated BST above.


An Adelson-Velskii Landis (AVL) tree is a self-balancing BST that maintains its height within a logarithmic order (O(log N)) relative to the number of vertices (N) present in the AVL tree.


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.

🕑

To switch between the standard Binary Search Tree and the AVL Tree (which primarily differs during the insertion and removal of an integer), please select the corresponding header.


We also provide a URL shortcut for quick access to the AVL Tree mode, available at https://visualgo.net/en/avl. The 'en' in the URL can be replaced with the two-character code of your preferred language, if available.


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.

🕑

A BST, particularly a balanced BST such as an AVL Tree, is an effective data structure for implementing a certain type of Table (or Map) Abstract Data Type (ADT).


A Table ADT should efficiently support at least the following three operations:

  1. Search(v) — ascertain whether v exists within the ADT,
  2. Insert(v) — add v into the ADT,
  3. Remove(v) — eliminate v from the ADT.

For a similar discussion, refer to the Hash Table e-Lecture slides.


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.

🕑

We are referring to a particular type of Table ADT where the keys must be ordered. This contrasts with other types of Table ADTs that allow for unordered keys.


The specific requirements of this Table ADT type will be clarified in the subsequent slides.


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.

🕑

Using an unsorted array or vector to implement a Table ADT can result in inefficiencies:

  1. Search(v) operates in O(N) time complexity because we may need to traverse all N elements of the ADT if v doesn't exist,
  2. Insert(v) can be implemented with O(1) time complexity, by simply appending v at the end of the array,
  3. Remove(v) also runs in O(N) time complexity, as we first need to search for v (which is already O(N)), and then close the gap resulting from the deletion — also an O(N) operation.
🕑

Implementing a Table ADT with a sorted array or vector can enhance the performance of Search(v), but this comes at the expense of Insert(v) performance:

  1. Search(v) can now be implemented with a time complexity of O(log N), as we can employ a binary search strategy on the sorted array,
  2. Insert(v) now operates with a time complexity of O(N), as we need to use an insertion-sort-like strategy to ensure the array remains sorted,
  3. Remove(v) still runs in O(N) time complexity. Although Search(v) operates in O(log N), we still have to close the gap resulting from the deletion, which runs in O(N).
🕑

The objective of this e-Lecture is to introduce the BST and the balanced BST data structure, namely the AVL Tree, which enable us to implement basic Table ADT operations like Search(v), Insert(v), and Remove(v) — along with a few other Table ADT operations (refer to the next slide) — in O(log N) time. This time complexity is significantly smaller than N. Please try the interactive slider below to feel the significant difference.



log N = 20, N = 1048576.


PS: More experienced readers may note the existence of another data structure that can perform these three basic Table ADT operations more swiftly. But, keep reading...

🕑

In addition to the basic three operations, there are several other Table ADT operations:

  1. Find the Min()/Max() element,
  2. Find the Successor(v), or the 'next larger' element, and Predecessor(v), or the 'previous smaller' element,
  3. List elements in sorted order,
  4. Rank(v) & Select(k),
  5. There are other possible operations as well.

Discussion: Given the constraint of using either a sorted or unsorted array/vector, what would be the optimal implementation for the first three additional operations above?

🕑

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.

🕑

Another data structure that can be used to implement Table ADT is Hash Table. It has very fast Search(v), Insert(v), and Remove(v) performance (all in expected O(1) time).


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 ____


Discuss the answer above! Hint: Go back to the previous 4 slides ago.

🕑

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.

🕑

We will now introduce the BST data structure. Refer to the visualization of an example BST provided above!


In a BST, the root vertex is unique and has no parent. Conversely, a leaf vertex, of which there can be several, has no children. Vertices that aren't leaves are known as internal vertices. Occasionally, the root vertex isn't included in the definition of an internal vertex as a BST with only one vertex (that root vertex) could technically fit the definition of a leaf as well.


In the illustrated example, vertex 15 is the root, vertices 5, 7, and 50 are the leaves, and vertices 4, 6, 15 (which is also the root), 23, and 71 are the internal vertices.

🕑

Each vertex has several key attributes: pointer to the left child, pointer to the right child, pointer to the parent vertex, key/value/data, and special for this visualization that implements 'multiset': frequency of each key (there are potential other attributes). Not all attributes will be used for all vertices, e.g., the leaf vertex will have both their left and right child attributes = NULL. Some other implementation separates key (for ordering of vertices in the BST) with the actual satellite data associated with the keys.


The left/right child of a vertex (except leaf) is drawn on the left/right and below of that vertex, respectively. The parent of a vertex (except root) is drawn above that vertex. The (integer) key of each vertex is drawn inside the circle that represent that vertex and if there are duplicated insertion of the same (integer) key, there will be an additional hyphen '-' and the actual frequency (≥ 2) of that key. In the example above, (key) 15 has 6 as its left child and 23 as its right child. Thus the parent of 6 (and 23) is 15. Some keys may have '-' (actual frequency) in random fashion.


Discussion: It is actually possible to omit the parent pointer from each vertex. How?

🕑

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.

🕑

We allow duplicate integers in this visualization by keeping the N (integer) keys distinct, but any duplication of an existing key will be stored as 'frequency' attribute of that key (visualized as '-' (actual frequency, but only if it is ≥ 2)). Thus we can use the simple BST property as follow: For every vertex X, all vertices on the left subtree of X are strictly smaller than X and all vertices on the right subtree of X are strictly greater than X.


In the example above, the vertices on the left subtree of the root 15: {4, 5, 6, 7} are all smaller than 15 and the vertices on the right subtree of the root 15: {23, 50, 71} are all greater than 15. You can recursively check BST property on other vertices too.


In this visualization, we allow the keys to be in range of [-99..99].

🕑

We provide visualization for the following common BST/AVL Tree operations:

  1. Query operations (the BST structure remains unchanged):
    1. Search(v) (or LowerBound(v)),
    2. Predecessor(v) (and similarly Successor(v)), and
    3. Inorder/Preorder/Postorder Traversal,
  2. Update operations (the BST structure (most likely) change):
    1. Create BST (several criteria),
    2. Insert(v), and
    3. Remove(v).
🕑

There are a few other BST (Query) operations that have not been visualized in VisuAlgo:

  1. Rank(v): Given a key v, determine what is its rank (1-based index) in the sorted order of the BST elements. That is, Rank(FindMin()) = 1 and Rank(FindMax()) = N. If v does not exist, we can report -1.
  2. Select(k): Given a rank k, 1 ≤ kN, determine the key v that has that rank k in the BST. Or in another word, find the k-th smallest element in the BST. That is, Select(1) = FindMin() and Select(N) = FindMax().

The details of these two operations are currently hidden for pedagogical purpose in a certain NUS course.

🕑

Data structure that is only efficient if there is no (or rare) update, especially the insert and/or remove operation(s) is called static data structure.


Data structure that is efficient even if there are many update operations is called dynamic data structure. BST and especially balanced BST (e.g., AVL Tree) are in this category.

🕑

Because of the way data (distinct integers for this visualization) is organised inside a BST, we can binary search for an integer v efficiently (hence the name of Binary Search Tree).


First, we set the current vertex = root and then check if the current vertex is smaller/equal/larger than integer v that we are searching for. We then go to the right subtree/stop/go the left subtree, respectively. We keep doing this until we either find the required vertex or we don't.


On the example BST above, try clicking Search(23) (found after 2 comparisons), Search(7) (found after 3 comparisons), Search(21) (not found after 2 comparisons — at this point we will realize that we cannot find 21).

🕑

Note that this term is based on the definition given in C++ std::set::lower_bound. Other programming languages, e.g., Java TreeSet has a similar method "higher()".


If v exists in the BST, then lower_bound(v) is the same as Search(v). But, if v does not exist in the BST, lower_bound(v) will find the smallest value in the BST that is strictly larger than v (unless v > the largest element in the BST). This is the location of this currently non-existent v if it is later inserted into this BST.

🕑

Similarly, because of the way data is organised inside a BST, we can find the minimum/maximum element (an integer in this visualization) by starting from root and keep going to the left/right subtree, respectively.


Try clicking SearchMin() and SearchMax() on the example BST shown above. The answers should be 4 and 71 (both after comparing against 3 integers from root to leftmost vertex/rightmost vertex, respectively).

🕑

Search(v)/lower_bound(v)/SearchMin()/SearchMax() operations run in O(h) where h is the height of the BST.


But note that this h can be as tall as O(N) in a normal BST as shown in the random 'skewed right' example above. Try Search(100) (this value should not exist as we only use random integers between [1..99] to generate this random BST and thus the Search routine should check all the way from root to the only leaf in O(N) time — not efficient.

🕑

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.

🕑

We have included the animation for both Preorder and Postorder tree traversal methods.


Basically, in Preorder Traversal, we visit the current root before going to left subtree and then right subtree. For the example BST shown in the background, we have: {{15}, {6, 4, 5, 7}, {23, 71, 50}}. PS: Do you notice the recursive pattern? root, members of left subtree of root, members of right subtree of root.


In Postorder Traversal, we visit the left subtree and right subtree first, before visiting the current root. For the example BST shown in the background, we have: {{5, 4, 7, 6}, {50, 71, 23}, {15}}.


Discussion: Given a Preorder Traversal of a BST, e.g., [15, 6, 4, 5, 7, 23, 71, 50], can you use it to recover the original BST? Similar question for Postorder is also possible.

🕑

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.

🕑

We can insert a new integer into BST by doing similar operation as Search(v). But this time, instead of reporting that the new integer is not found, we create a new vertex in the insertion point and put the new integer there. Try Insert(60) on the example above (the first insertion will create a new vertex, but see below).


Since we now implement 'multiset', we can insert a duplicate element, e.g., try Insert(7) on the example above (multiple times) or click Insert(60) again (the duplicate(s)).

🕑

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


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

🕑

We can remove an integer in BST by performing similar operation as Search(v).


If v is not found in the BST, we simply do nothing.


If v is found in the BST, we do not report that the existing integer v is found, but instead, we do the following checks. If the frequency of v is ≥ 2, we simply decrease its frequency by one without doing anything else. However, if the frequency of v is exactly 1, we perform one of the three possible removal cases that will be elaborated in three separate slides (we suggest that you try each of them one by one).

🕑

The first case is the easiest: Vertex v is currently one of the leaf vertex of the BST.


Deletion of a leaf vertex is very easy: We just remove that leaf vertex — try Remove(5) on the example BST above (if the randomization causes vertex 5 to have more than one copy, just click that button again).


This part is clearly O(1) — on top of the earlier O(h) search-like effort.

🕑

The second case is also not that hard: Vertex v is an (internal/root) vertex of the BST and it has exactly one child. Removing v without doing anything else will disconnect the BST.


Deletion of a vertex with one child is not that hard: We connect that vertex's only child with that vertex's parent — try Remove(23) on the example BST above (if the randomization causes vertex 23 to have more than one copy, just click that button again).


This part is also clearly O(1) — on top of the earlier O(h) search-like effort.

🕑

The third case is the most complex among the three: Vertex v is an (internal/root) vertex of the BST and it has exactly two children. Removing v without doing anything else will disconnect the BST.


Deletion of a vertex with two children is as follow: We replace that vertex with its successor, and then delete its duplicated successor in its right subtree — try Remove(6) on the example BST above (if the randomization causes vertex 6 to have more than one copy, just click that button again).


This part requires O(h) due to the need to find the successor vertex — on top of the earlier O(h) search-like effort.

🕑

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.

🕑

Remove(v) runs in O(h) where h is the height of the BST. Removal case 3 (deletion of a vertex with two children is the 'heaviest' but it is not more than O(h)).


As you should have fully understand by now, h can be as tall as O(N) in a normal BST as shown in the random 'skewed right' example above. If we call Remove(FindMax()), i.e. we remove the current max integer, we will go from root down to the last leaf in O(N) time before removing it (when its frequency is 1) — not efficient.

🕑

To make life easier in 'Exploration Mode', you can create a new BST using these options:

  1. Empty BST (you can then insert a few integers one by one),
  2. A few e-Lecture Examples that you may have seen several times so far,
  3. Random BST (which is unlikely to be extremely tall — the expected height of a randomly built BST is still O(log N)),
  4. Skewed Left/Right BST (tall BST with N vertices and N-1 linked-list like edges, to showcase the worst case behavior of BST operations; disabled in AVL Tree mode).
🕑

We are midway through the explanation of this BST module. So far we notice that many basic Table ADT operations run in O(h) and h can be as tall as N-1 edges like the 'skewed left' example shown — inefficient :(...


So, is there a way to make our BSTs 'not that tall'?


PS: If you want to study how these basic BST operations are implemented in a real program, you can download this BSTDemo.cpp | py | java.

🕑

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) = 2
height(65) = 3
height(20) = 3
height(41) = 3
height(20) = 2
height(41) = 4
🕑

If we have N elements/items/keys in our BST, the lower bound height h = Ω(log2 N) (the detailed formula in the next slide) if we can somehow insert the N elements in perfect order so that the BST is perfectly balanced.


See the example shown above for N = 15 (a perfect BST which is rarely achievable in real life — try inserting any other (distinct) integer and it will not be perfect anymore).

🕑
N ≤ 1 + 2 + 4 + ... + 2h
N ≤ 20 + 21 + 22 + … + 2h
N ≤ 2h+1-1 (sum of geometric progression)
N+1 ≤ 2h+1 (apply +1 on both sides)
log2 (N+1) ≤ log2 2h+1 (apply log2 on both sides)
log2 (N+1) ≤ (h+1) * log2 2 (bring down the exponent)
log2 (N+1) ≤ h+1 (log2 2 is 1)
h+1 ≥ log2 (N+1) (flip the direction)
h ≥ log2 (N+1)-1 (apply -1 on both sides)
🕑

If we have N elements/items/keys in our BST, the upper bound height h = O(N) if we insert the elements in ascending order (to get skewed right BST as shown above).


The height of such BST is h = N-1, so we have h < N.


Discussion: Do you know how to get skewed left BST instead?

🕑

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 for minimum-size AVL tree of height h)
Nh > 1 + 2*Nh-2 (as Nh-1 > Nh-2)
Nh > 2*Nh-2 (obviously)
Nh > 4*Nh-4 (recursive)
Nh > 8*Nh-6 (another recursive step)
... (we can only do this h/2 times, assuming initial h is even)
Nh > 2h/2*N0 (we reach base case)
Nh > 2h/2 (as N0 = 1)
Proof-3
🕑
N ≥ Nh > 2h/2 (combining the previous two slides)
N > 2h/2
log2(N) > log2(2h/2) (log2 on both sides)
log2(N) > h/2 (formula simplification)
2 * log2(N) > h or h < 2 * log2(N)
h = O(log(N)) (the final conclusion)
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

See the picture above. Calling rotateRight(D) on the left picture will produce the right picture. Calling rotateLeft(B) on the right picture will produce the left picture again.


rotateRight(T)/rotateLeft(T) can only be called if T has a left/right child, respectively.


Tree Rotation preserves BST property.
Before rotation, A < B < C < D < E.
After rotation, notice that subtree rooted at C (if it exists) changes parent,
but the order of A < B < C < D < E does not change.

🕑
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

There are only these four cases:

  1. Left Left Case: bf(F) = +2 and bf(D) = +1, solution: rotateRight(F)
  2. Left Right Case: bf(F) = +2 and bf(B) = -1, solution: rotateLeft(B) first to transform this case into Left Left Case again, then go to step 1
  3. Right Right Case: bf(B) = -2 and bf(D) = -1, solution: rotateLeft(B)
  4. Right Left Case: bf(B) = -2 and bf(F) = +1, solution: rotateRight(F) first to transform this case into Right Right Case again, then go to step 3
🕑
  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).

🕑

We have now see how AVL Tree defines the height-balance invariant, maintain it for all vertices during Insert(v) and Remove(v) update operations, and a proof that AVL Tree has h < 2 * log N.


Therefore, all BST operations (both update and query operations except Inorder Traversal) that we have learned so far, if they have time complexity of O(h), they have time complexity of O(log N) if we use AVL Tree version of BST.


This marks the end of this e-Lecture, but please switch to 'Exploration Mode' and try making various calls to Insert(v) and Remove(v) in AVL Tree mode to strengthen your understanding of this data structure.


PS: If you want to study how these seemingly complex AVL Tree (rotation) operations are implemented in a real program, you can download this AVLDemo.cpp | java (must be used together with this BSTDemo.cpp | java).

🕑

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.

🕑

For a few more interesting questions about this data structure, please practice on BST/AVL training module (no login is required).


However, for registered users, you should login and click the training icon from the homepage to officially clear this module and such achievement will be recorded in your user account.

🕑

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.

🕑

Toggle BST Layout

Buat

Masukkan(v)

Hapus(v)

Predec-/Succ-essor(v)

Select(k)

Traverse(root)

>

Kosong

Examples

N =

Acak

Skewed

v =

Lakukan

v =

Lakukan

v =

Cari Pendahulu

Cari Penerus

k =

Lakukan

Inorder(root)

Preorder(root)

Postorder(root)

Tentang Tim Syarat Guna Kebijakan Privasi

Tentang

Initially conceived in 2011 by Associate Professor Steven Halim, VisuAlgo aimed to facilitate a deeper understanding of data structures and algorithms for his students by providing a self-paced, interactive learning platform.

Featuring numerous advanced algorithms discussed in Dr. Steven Halim's book, 'Competitive Programming' — co-authored with Dr. Felix Halim and Dr. Suhendry Effendy — VisuAlgo remains the exclusive platform for visualizing and animating several of these complex algorithms even after a decade.

While primarily designed for National University of Singapore (NUS) students enrolled in various data structure and algorithm courses (e.g., CS1010/equivalent, CS2040/equivalent (including IT5003), CS3230, CS3233, and CS4234), VisuAlgo also serves as a valuable resource for inquisitive minds worldwide, promoting online learning.

Initially, VisuAlgo was not designed for small touch screens like smartphones, as intricate algorithm visualizations required substantial pixel space and click-and-drag interactions. For an optimal user experience, a minimum screen resolution of 1366x768 is recommended. However, since April 2022, a mobile (lite) version of VisuAlgo has been made available, making it possible to use a subset of VisuAlgo features on smartphone screens.

VisuAlgo remains a work in progress, with the ongoing development of more complex visualizations. At present, the platform features 24 visualization modules.

Equipped with a built-in question generator and answer verifier, VisuAlgo's "online quiz system" enables students to test their knowledge of basic data structures and algorithms. Questions are randomly generated based on specific rules, and students' answers are automatically graded upon submission to our grading server. As more CS instructors adopt this online quiz system worldwide, it could effectively eliminate manual basic data structure and algorithm questions from standard Computer Science exams in many universities. By assigning a small (but non-zero) weight to passing the online quiz, CS instructors can significantly enhance their students' mastery of these basic concepts, as they have access to an almost unlimited number of practice questions that can be instantly verified before taking the online quiz. Each VisuAlgo visualization module now includes its own online quiz component.

VisuAlgo has been translated into three primary languages: English, Chinese, and Indonesian. Additionally, we have authored public notes about VisuAlgo in various languages, including Indonesian, Korean, Vietnamese, and Thai:

id, kr, vn, th.

Tim

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

Murid-Murid S1 Peniliti 1
CDTL TEG 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
Jun 2013-Apr 2014 Rose Marie Tan Zhao Yun, Ivan Reinaldo

Murid-Murid S1 Peniliti 2
CDTL TEG 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 2
Jun 2014-Apr 2015: Erin Teo Yi Ling, Wang Zi
Jun 2016-Dec 2017: Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir
Aug 2021-Apr 2023: Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long, Ting Xiao, Lim Dewen Aloysius

Murid-Murid S1 Peniliti 3
Optiver: Aug 2023-Oct 2023: Bui Hong Duc, Oleh Naver, Tay Ngan Lin

Murid-Murid Proyek Tahun Terakhir/UROP 3
Aug 2023-Apr 2024: Xiong Jingya, Radian Krisno, Ng Wee Han

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

Ucapan Terima Kasih
NUS CDTL gave Teaching Enhancement Grant to kickstart this project.

For Academic Year 2023/24, a generous donation from Optiver will be used to further develop VisuAlgo.

Syarat Guna

VisuAlgo is generously offered at no cost to the global Computer Science community. If you appreciate VisuAlgo, we kindly request that you spread the word about its existence to fellow Computer Science students and instructors. You can share VisuAlgo through social media platforms (e.g., Facebook, YouTube, Instagram, TikTok, Twitter, etc), course webpages, blog reviews, emails, and more.

Data Structures and Algorithms (DSA) students and instructors are welcome to use this website directly for their classes. If you capture screenshots or videos from this site, feel free to use them elsewhere, provided that you cite the URL of this website (https://visualgo.net) and/or the list of publications below as references. However, please refrain from downloading VisuAlgo's client-side files and hosting them on your website, as this constitutes plagiarism. At this time, we do not permit others to fork this project or create VisuAlgo variants. Personal use of an offline copy of the client-side VisuAlgo is acceptable.

Please note that VisuAlgo's online quiz component has a substantial server-side element, and it is not easy to save server-side scripts and databases locally. Currently, the general public can access the online quiz system only through the 'training mode.' The 'test mode' offers a more controlled environment for using randomly generated questions and automatic verification in real examinations at NUS.

List of Publications

This work has been presented 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).

Bug Reports or Request for New Features

VisuAlgo is not a finished project. Associate Professor 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 Associate Professor Steven Halim. His contact is the concatenation of his name and add gmail dot com.

Kebijakan Privasi

Version 1.2 (Updated Fri, 18 Aug 2023).

Since Fri, 18 Aug 2023, we no longer use Google Analytics. Thus, all cookies that we use now are solely for the operations of this website. The annoying cookie-consent popup is now turned off even for first-time visitors.

Since Fri, 07 Jun 2023, thanks to a generous donation by Optiver, anyone in the world can self-create a VisuAlgo account to store a few customization settings (e.g., layout mode, default language, playback speed, etc).

Additionally, for NUS students, by using a VisuAlgo account (a tuple of NUS official email address, student name as in the class roster, and a password that is encrypted on the server side — no other personal data is stored), you are giving a consent for your course lecturer to keep track of your e-lecture slides reading and online quiz training progresses that is needed to run the course smoothly. Your VisuAlgo account will also be needed for taking NUS official VisuAlgo Online Quizzes and thus passing your account credentials to another person to do the Online Quiz on your behalf constitutes an academic offense. Your user account will be purged after the conclusion of the course unless you choose to keep your account (OPT-IN). Access to the full VisuAlgo database (with encrypted passwords) is limited to Prof Halim himself.

For other CS lecturers worldwide who have written to Steven, a VisuAlgo account (your (non-NUS) email address, you can use any display name, and encrypted password) is needed to distinguish your online credential versus the rest of the world. Your account will have CS lecturer specific features, namely the ability to see the hidden slides that contain (interesting) answers to the questions presented in the preceding slides before the hidden slides. You can also access Hard setting of the VisuAlgo Online Quizzes. You can freely use the material to enhance your data structures and algorithm classes. Note that there can be other CS lecturer specific features in the future.

For anyone with VisuAlgo account, you can remove your own account by yourself should you wish to no longer be associated with VisuAlgo tool.