7    VisuAlgo.net / /bst Login Binärer Suchbaum AVL-Baum
Erkundungsmodus

>

>
langsam
schnell
go to beginning previous frame pause play next frame go to end

A Binary Search Tree (BST) is a binary tree in which each vertex has only up to 2 children that satisfies BST property: All vertices in the left subtree of a vertex must hold a value smaller than its own and all vertices in the right subtree of a vertex must hold a value larger than its own (we have assumption that all values are distinct integers in this visualization and small tweak is needed to cater for duplicates/non integer). Try clicking Search(7) for a sample animation on searching a random value ∈ [1..99] in the random BST above.


An Adelson-Velskii Landis (AVL) tree is a self-balancing BST that maintains it's height to be O(log N) when having N vertices in the AVL tree.


Click 'Next' (on the top right)/press 'Page Down' to advance this e-Lecture slide, use the drop down list/press 'Space' to jump to a specific slide, or Click 'X' (on the bottom right)/press 'Esc' to go to Exploration mode.


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

X Esc
Weiter
PgDn

To toggle between the standard Binary Search Tree and the AVL Tree (only different behavior during Insertion and Removal of an Integer), select the respective header.


We also have URL shortcut to quickly access the AVL Tree mode, which is https://visualgo.net/en/avl (you can change the 'en' to your two characters preferred language - if available).


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

X Esc
Zurück
PgUp
Weiter
PgDn

BST (and especially balanced BST like AVL Tree) is an efficient data structure to implement a certain kind of Table (or Map) Abstract Data Type (ADT).


A Table ADT must support at least the following three operations as efficient as possible:

  1. Search(v) — determine if v exists in the ADT or not,
  2. Insert(v) — insert v into the ADT,
  3. Remove(v) — remove v from the ADT.

Reference: See similar slide in Hash Table e-Lecture.


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

X Esc
Zurück
PgUp
Weiter
PgDn
Wir referieren auf einen Tabellen ADT wo die Schlüssel geordnet sein müssen (im Vergleich zu einer Tabellen ADT wo die Schlüssel nicht ungeordnet sein müssen).
Die besonderen Bedingungen einer Tabellen ADT werden in den nächsten paar Folien klarer gemacht.
X Esc
Zurück
PgUp
Weiter
PgDn

If we use unsorted array/vector to implement Table ADT, it can be inefficient:

  1. Search(v) runs in O(N), as we may end up exploring all N elements of the ADT if v actually does not exist,
  2. Insert(v) can be implemented in O(1), just put v at the back of the array,
  3. Remove(v) runs in O(N) too as we have to first search for v which is already O(N) and later close the resulting gap after deletion — also in O(N).
X Esc
Zurück
PgUp
Weiter
PgDn

If we use sorted array/vector to implement Table ADT, we can improve the Search(v) performance but weakens the Insert(v) performance:

  1. Search(v) can now be implemented in O(log N), as we can now use binary search on the sorted array,
  2. Insert(v) now runs in O(N) as we need to implement an insertion-sort like strategy to make the array remains sorted,
  3. Remove(v) runs in O(N) because even if Search(v) runs in O(log N), we still need to close the gap after deletion — which is in O(N).
X Esc
Zurück
PgUp
Weiter
PgDn

The goal for this e-Lecture is to introduce BST and then balanced BST (AVL Tree) data structure so that we can implement the basic Table ADT operations: Search(v), Insert(v), Remove(v), and a few other Table ADT operations — see the next slide — in O(log N) time — which is much smaller than N.


PS: Some of the more experienced readers may notice that ∃ another data structure that can implement the three basic Table ADT operations in faster time, but read on...


N≈ 1 000≈ 1 000 000≈ 1 000 000 000
log N10Only 20 :OOnly 30 :O:O
X Esc
Zurück
PgUp
Weiter
PgDn

On top of the basic three, there are a few other possible Table ADT operations:

  1. Find the Min()/Max() element,
  2. Find the Successor(v) — 'next larger'/Predecessor(v) — 'previous smaller' element,
  3. List elements in sorted order,
  4. Operation X & Y - hidden for pedagogical purpose in an NUS module,
  5. There are others possible operations.

Discussion: What are the best possible implementation for the first three additional operations if we are limited to use [sorted|unsorted] array/vector?

X Esc
Zurück
PgUp
Weiter
PgDn

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

X Esc
Zurück
PgUp
Weiter
PgDn

The simpler data structure that can be used to implement Table ADT is 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


Discussion: Why?

X Esc
Zurück
PgUp
Weiter
PgDn

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

X Esc
Zurück
PgUp
Weiter
PgDn

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


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

X Esc
Zurück
PgUp
Weiter
PgDn

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

X Esc
Zurück
PgUp
Weiter
PgDn

We will now introduce BST data structure. See the visualization of an example BST above!


Root vertex does not have a parent. There can only be one root vertex in a BST. Leaf vertex does not have any child. There can be more than one leaf vertex in a BST. Vertices that are not leaf are called the internal vertices. Sometimes root vertex is not included as part of the definition of internal vertex as the root of a BST with only one vertex can actually fit into the definition of a leaf too.


In the example above, vertex 15 is the root vertex, vertex {5, 7, 50} are the leaves, vertex {4, 6, 15 (also the root), 23, 71} are the internal vertices.

X Esc
Zurück
PgUp
Weiter
PgDn

Each vertex has at least 4 attributes: parent, left, right, key/value/data (there are potential other attributes). Not all attributes will be used for all vertices, e.g. the root vertex will have its parent attribute = 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. 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.

X Esc
Zurück
PgUp
Weiter
PgDn

As we do not allow duplicate integer in this visualization, the BST property is 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.


For more complete implementation, we should consider duplicate integers too and we must consistently place integers that are equal to X to one subtree only (not arbitrary).

X Esc
Zurück
PgUp
Weiter
PgDn

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

  1. Query operations (the BST structure remains unchanged):
    1. Search(v),
    2. Predecessor(v) (and similarly Successor(v)), and
    3. Inorder Traversal (we will add Preorder and Postorder Traversal soon),
  2. Update operations (the BST structure may likely change):
    1. Insert(v),
    2. Remove(v), and
    3. Create BST (several criteria).
X Esc
Zurück
PgUp
Weiter
PgDn

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

X Esc
Zurück
PgUp
Weiter
PgDn

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.

X Esc
Zurück
PgUp
Weiter
PgDn
Wegen der Art und Weise wie Daten (eindeutige Integer für diese Visualisierung) in einem BST organisiert sind, könne wir binär und effektiv nach einem Integer v suchen (deswegen der Name Binärer Suchbaum).
Zuerst setzen wir den aktuellen Knoten = Wurzel und prüfen ob der aktuelle Knoten kleiner/gleich/größer als der Integer v ist nachdem wir suchen. Wir gehen dann zum rechten Teilbaum/stoppen/gehen zum linken Teilbaum. Damit machen wir weiter bis wir entweder den gesuchten Knoten finden oder auch nicht.
Bei dem Beispiel Suchbaum, versuche auf Search(15) (gefunden nach nur einem Vergleich), Search(7) (gefunden nach 3 Vergleichen), Search(21) (nicht gefunden nach 3 Vergleichen) zu klicken
X Esc
Zurück
PgUp
Weiter
PgDn
Ähnlich, wegen der Art und Weise wie Daten in einem BST organisiert sind, können wir das maximale/minimale Element (einen Integer in dieser Visualisierung) finden indem wir bei der Wurzel anfangen und in den immer weiter in den linken beziehungsweise rechten Teilbaum gehen. Versuche FindMin() und FindMax() auf den Beispiel BST der hier gezeigt wird. Die Antworten sollten 4 und 71 sein (beide nach 4 Vergleichen).
X Esc
Zurück
PgUp
Weiter
PgDn

Search(v)/FindMin()/FindMax() 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.

X Esc
Zurück
PgUp
Weiter
PgDn

Because of the BST properties, we can find the Successor of an integer v (assume that we already know where integer v is located from earlier call of Search(v)) as follows:

  1. If v has a right subtree, the minimum integer in the right subtree of v must be the successor of v. Try Successor(23) (should be 50).
  2. If v does not have a right subtree, we need to traverse the ancestor(s) of v until we find 'a right turn' to vertex w (or alternatively, until we find the first vertex w that is greater than vertex v). Once we find vertex w, we will see that vertex v is the maximum element in the left subtree of w. Try Successor(7) (should be 15).
  3. If v is the maximum integer in the BST, v does not have a successor. Try Successor(71) (should be none).
X Esc
Zurück
PgUp
Weiter
PgDn

The operations for Predecessor of an integer v are defined similarly (just the mirror of Successor operations).


Try the same three corner cases (but mirrored): Predecessor(6) (should be 5), Predecessor(50) (should be 23), Predecessor(4) (should be none).


At this point, stop and ponder these three Successor(v)/Predecessor(v) cases to ensure that you understand these concepts.

X Esc
Zurück
PgUp
Weiter
PgDn

Predecessor(v) and Successor(v) operations run in O(h) where h is the height of the BST.


But recall that this h can be as tall as O(N) in a normal BST as shown in the random 'skewed right' example above. If we call Successor(FindMax()), we will go up from that last leaf back to the root in O(N) time — not efficient.

X Esc
Zurück
PgUp
Weiter
PgDn

We can perform an Inorder Traversal of this BST to obtain a list of sorted integers inside this BST (in fact, if we 'flatten' the BST into one line, we will see that the vertices are ordered from smallest/leftmost to largest/rightmost).


Inorder Traversal is a recursive method whereby we visit the left subtree first, exhausts all items in the left subtree, visit the current root, before exploring the right subtree and all items in the right subtree. Without further ado, let's try Inorder Traversal to see it in action on the example BST above.

X Esc
Zurück
PgUp
Weiter
PgDn

Inorder Traversierung hat eine Laufzeit von O(N), unabhängig von der Höhe des BST.


Diskussion: Warum?


PS: Manche Leute nennen das Einfügen von N unsortierten Integer in einen BST mit einer Laufzeit von O(N log N) und einer anschließenden Inorder Traversierung 'BST sort'. Diese Methode wird allerdings selten genutzt da es einfachere (Vergleich-basierte) Sortier Algorithmen gibt als diese.

X Esc
Zurück
PgUp
Weiter
PgDn

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

X Esc
Zurück
PgUp
Weiter
PgDn

We have not included the animation of these two other classic tree traversal methods, but we will do so very soon.


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

X Esc
Zurück
PgUp
Weiter
PgDn

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.

X Esc
Zurück
PgUp
Weiter
PgDn
Insert(v) hat eine Laufzeit von O(h) wenn h die Höhe des BST ist.
Mittlerweile solltest du dir bewusst sein das dieses h so hoch wie O(N) sein kann in einem normalen BST wie im zufälligen 'skewed right' Beispiel. Wenn wir Insert(FindMax()+1) aufrufen, d.h. wir fügen einen neuen Integer ein des größer als unser aktuelles Maximum ist, werden von der Wurzel bis zum letzten Blatt runter gehen und dann den Integer als neues Kind des letzten Blattes mit einer Laufzeit O(N) einfügen - nicht effektiv (beachte das wir in dieser Visualisierung nur höchstens h=9 erlauben).
X Esc
Zurück
PgUp
Weiter
PgDn

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

8
The height cannot be determined
9
10
Pro-Tip: Du kannst den "Erkundungs-Modus" nutzen um deine Antworten zu verifizieren.
X Esc
Zurück
PgUp
Weiter
PgDn

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

X Esc
Zurück
PgUp
Weiter
PgDn

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 (second click onwards after the first removal will do nothing — please refresh this page or go to another slide and return to this slide instead).


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

X Esc
Zurück
PgUp
Weiter
PgDn

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 (second click onwards after the first removal will do nothing — please refresh this page or go to another slide and return to this slide instead).


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

X Esc
Zurück
PgUp
Weiter
PgDn

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 (second click onwards after the first removal will do nothing — please refresh this page or go to another slide and return to this slide instead).


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

X Esc
Zurück
PgUp
Weiter
PgDn

This case 3 warrants further discussions:

  1. Why replacing a vertex B that has two children with its successor C is always a valid strategy?
  2. Can we replace vertex B that has two children with its predecessor A instead? Why or why not?
X Esc
Zurück
PgUp
Weiter
PgDn

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

X Esc
Zurück
PgUp
Weiter
PgDn

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 — not efficient.

X Esc
Zurück
PgUp
Weiter
PgDn

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. The two e-Lecture Examples that you may have seen several times so far,
  3. Random BST (which unlikely to be extremely tall),
  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).
X Esc
Zurück
PgUp
Weiter
PgDn

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.

X Esc
Zurück
PgUp
Weiter
PgDn
An diesem Punkt, regen wir dazu an [Esc] oder den X Knopf in der oberen rechten Ecke diese e-Lektüre zu drücken um in den "Erkundungs Modus" zu kommen und selber ein paar BST Operationen aus zu probieren um diese vielseitige Datenstruktur besser zu verstehen.
Wenn du bereit bist mit der Erklärung des balanzierten BST (wir nutzen den AVL Baum als unser Beispiel) weiter zu machen, drücke [Esc] oder wechsle zurück zum "e-Lektüren Modus" im Drop Down Menü in der oberen rechten Ecke. Benutze dann die Folien Auswahl Drop Down Liste um mit dieser Folie 12-1 weiter zu machen.
X Esc
Zurück
PgUp
Weiter
PgDn
Wir haben auf vorherigen Folien gesehen das die meisten unserer BST Operationen, außer Inorder Traversierung, in O(h) laufen wo h die Höhe des BST ist, welcher bis N-1 hoch sein kann.
Wir werden unsere Diskussion weiter führen mit dem Konzept eines balanzierten BST sodass h = O(log N) ist.
X Esc
Zurück
PgUp
Weiter
PgDn

There are several known implementations of balanced BST, too many to be visualized and explained one by one in VisuAlgo.


We focus on AVL Tree (Adelson-Velskii & Landis, 1962) that is named after its inventor: Adelson-Velskii and Landis.


Other balanced BST implementations (more or less as good or slightly better in terms of constant-factor performance) are: 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), etc.

X Esc
Zurück
PgUp
Weiter
PgDn

To facilitate AVL Tree implementation, we need to augment — add more information/attribute to — each BST vertex.


For each vertex v, we define height(v): The number of edges on the path from vertex v down to its deepest leaf. This attribute is saved in each vertex so we can access a vertex's height in O(1) without having to recompute it every time.

X Esc
Zurück
PgUp
Weiter
PgDn

Formal:

v.height = -1 (if v is an empty tree)
v.height = max(v.left.height, v.right.height) + 1 (otherwise)
Die Höhe des BST ist also: root.height.


Bei dem Beispiel BST, height(11) = height(32) = height(50) = height(72) = height(99) = 0 (alle sind Blätter). height(29) = 1 das es eine Kante gibt die es mit seinem einzigen Blatt 32 verbindet.

X Esc
Zurück
PgUp
Weiter
PgDn

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

height(20) = 2
height(65) = 3
height(65) = 2
height(20) = 3
height(41) = 4
height(41) = 3
X Esc
Zurück
PgUp
Weiter
PgDn
Wenn wir N Elemente/Gegenstände/Schlüssel in unserem BST haben, können wir eine unter Kanten Höhe von h > log2 erreichen wenn wir es hinbekommen die N Elemente in der perfekten Reihenfolge einzufügen sodass der BST perfekt aus balanciert ist.
Schaue dir das oben angegebene Beispiel für N = 15 an (ein perfekter BST was in echt selten zu erreichen ist — fügst du irgendeinen anderen Integer hinzu wird er nicht mehr perfekt sein).
X Esc
Zurück
PgUp
Weiter
PgDn
N ≤ 1 + 2 + 4 + ... + 2h
N ≤ 20 + 21 + 22 + … + 2h
N < 2h+1 (sum of geometric progression)
log2 N < log2 2h+1
log2 N < (h+1) * log2 2 (log2 2 is 1)
h > (log2 N)-1 (algebraic manipulation)
h > log2 N
X Esc
Zurück
PgUp
Weiter
PgDn
Wenn wir N Elemente/Gegenstände/Schlüssel in unserem BST haben, können wir eine obere Kanten Höhe von h < N erreichen wenn wir die Elemente in absteigender Reihenfolge (um den oben gezeigten rechts schiefen BST zu bekommen).
Die Höhe eines solchen BST ist h = N-1, also haben wir h < N.
Diskussion: Weist du wie man stattdessen einen links schiefen BST bekommt? 
X Esc
Zurück
PgUp
Weiter
PgDn

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

X Esc
Zurück
PgUp
Weiter
PgDn
Wir haben gesehen, dass die meisten BST Operationen in O(h) laufen und kombinieren wir die obere und untere Kante von h, haben wir log2 N < h < N.
Es gibt einen dramatischen Unterschied zwischen log2 N und N und wir haben bei der Diskussion gesehen, dass es fast unmöglich ist einen (dauerhaft) perfekten BST zu haben...
Können wir also einen BST haben dessen Höhe nah an log2 N ist, z.B.  c * log2 N, wobei c ein kleiner konstanter Faktor ist? Wenn wir das können, dann laufen die BST Operationen welche normalerweise eine Laufzeit von O(h) haben, in O(log N)... 
X Esc
Zurück
PgUp
Weiter
PgDn
Einführung des AVL Baum, erfunden von zwei Russischen (Soviet) Erfinder: Georgy Adelson-Velskii und Evgenii Landis in 1962.
Beim AVL Baum werden wir später sehen das seine Höhe  h < 2 * log N ist (genauere Analyse existieren, wir werden allerdings einfachere Analysen in VisuAlgo nutzen wo  c = 2). Folgendermaßen laufen die meisten AVL Baum Operatoren in O(log N) Laufzeit —effizient.
Einfügen(v) und Entfernen(v) verändern möglicherweise die Höhe h des AVL Baums, wir werden die rotations Operationen sehen, die dafür sorgen das die Höhe des AVL Baums niedrig bleibt.
X Esc
Zurück
PgUp
Weiter
PgDn

To have efficient performance, we shall not maintain height(v) attribute via the O(N) recursive method every time there is an update (Insert(v)/Remove(v)) operation.


Instead, we compute O(1): x.height = max(x.left.height, x.right.height) + 1 at the back of our Insert(v)/Remove(v) operation as only the height of vertices along the insertion/removal path may be affected. Thus, only O(h) vertices may change its height(v) attribute and in AVL Tree, h < 2 * log N.


Try Insert(37) on the example AVL Tree (ignore the resulting rotation for now, we will come back to it in the next few slides). Notice that only a few vertices along the insertion path: {41,20,29,32} increases their height by +1 and all other vertices will have their heights unchanged.

X Esc
Zurück
PgUp
Weiter
PgDn

Let's define the following important AVL Tree invariant (property that will never change): A vertex v is said to be height-balanced if |v.left.height - v.right.height| ≤ 1.


A BST is called height-balanced according to the invariant above if every vertex in the BST is height-balanced. Such BST is called AVL Tree, like the example shown above.


Take a moment to pause here and try inserting a few new random vertices or deleting a few random existing vertices. Will the resulting BST still considered height-balanced?

X Esc
Zurück
PgUp
Weiter
PgDn
Ein AVL Baum (ein balancierter BST der die AVL Baum Eigenschaften erfüllt) mit N Scheitelpunkten hat die Höhe h < 2 * log2N.
Der Beweiß beruht auf dem Konzept eines minimaler-höhe AVL Baums einer bestimmten Höhe h.
Lass Nh die minimale Anzahl an Knoten in einem höhen-balanzierten AVL Baum der Höhe h sein. Die ersten paar Werte von Nh sind N0 = 1 (ein einzelner Knoten),   N1 = 2 (ein Knoten mit entweder einem linken Kind oder einem rechten Kind), N2 = 4N3 = 7N4 = 12N5 = 20 (siehe das Hintergrundbild), und so weiter (siehe die nächsten beiden Folien).
X Esc
Zurück
PgUp
Weiter
PgDn

We know that for any other AVL Tree of N vertices (not necessarily the minimum-size one), we have N ≥ Nh.


Proof-2

In the background picture, we have N5 = 20 vertices but we know that we can squeeze 43 more vertices (up to N = 63) before we have a perfect binary tree of height h = 5.

X Esc
Zurück
PgUp
Weiter
PgDn
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
X Esc
Zurück
PgUp
Weiter
PgDn
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
X Esc
Zurück
PgUp
Weiter
PgDn

Look at the example BST again. See that all vertices are height-balanced, an AVL Tree.


To quickly detect if a vertex v is height balanced or not, we modify the AVL Tree invariant (that has absolute function inside) into: bf(v) = v.left.height - v.right.height.


Now try Insert(37) on the example AVL Tree again. A few vertices along the insertion path: {41,20,29,32} increases their height by +1. Vertices {29,20} will no longer be height-balanced after this insertion (and will be rotated later — discussed in the next few slides), i.e. bf(29) = -2 and bf(20) = -2 too. We need to restore the balance.

X Esc
Zurück
PgUp
Weiter
PgDn
Tree Rotation

See the picture above. Calling rotateRight(Q) on the left picture will produce the right picture. Calling rotateLeft(P) 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, P ≤ B ≤ Q. After rotation, notice that subtree rooted at B (if it exists) changes parent, but P ≤ B ≤ Q does not change.

X Esc
Zurück
PgUp
Weiter
PgDn
BSTVertex rotateLeft(BSTVertex T) // pre-req: T.right != null
BSTVertex w = T.right // rotateRight is the mirror copy of this
w.parent = T.parent // this method is hard to get right for newbie
T.parent = w
T.right = w.left
if (w.left != null) w.left.parent = T
w.left = T
// update the height of T and then w here
return w
X Esc
Zurück
PgUp
Weiter
PgDn
Im Wesentlichen gibt es nur diese vier Fälle von Unausgeglichenheit. Wir nutzen Baum Rotation(en) um mit diesen fertig zu werden.
X Esc
Zurück
PgUp
Weiter
PgDn
  1. Just insert v as in normal BST,
  2. Walk up the AVL Tree from the insertion point back to the root and at every step, we update the height and balance factor of the affected vertices:
    1. Stop at the first vertex that is out-of-balance (+2 or -2), if any,
    2. Use one of the four tree rotation cases to rebalance it again, e.g. try Insert(37) on the example above and notice by calling rotateLeft(29) once, we fix the imbalance issue.

Discussion: Is there other tree rotation cases for Insert(v) operation of AVL Tree?

X Esc
Zurück
PgUp
Weiter
PgDn

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

X Esc
Zurück
PgUp
Weiter
PgDn
  1. Just remove v as in normal BST (one of the three removal cases),
  2. Walk up the AVL Tree from the deletion point back to the root and at every step, we update the height and balance factor of the affected vertices:
    1. Now for every vertex that is out-of-balance (+2 or -2), we use one of the four tree rotation cases to rebalance them (can be more than one) again.

The main difference compared to Insert(v) in AVL tree is that we may trigger one of the four possible rebalancing cases several times, but not more than h = O(log N) times :O, try Remove(7) on the example above to see two chain reactions rotateRight(6) and then rotateRight(16)+rotateLeft(8) combo.

X Esc
Zurück
PgUp
Weiter
PgDn

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

X Esc
Zurück
PgUp
Weiter
PgDn
Wir werden dieses Modul mit ein paar weiteren interessanten Dingen über BST und ausgeglichenen BST (vorallem AVL-Baum) beenden
X Esc
Zurück
PgUp
Weiter
PgDn

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

X Esc
Zurück
PgUp
Weiter
PgDn

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

X Esc
Zurück
PgUp
Weiter
PgDn

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 then go to the Main Training Page to officially clear this module and such achievement will be recorded in your user account.

X Esc
Zurück
PgUp
Weiter
PgDn

We also have a few programming problems that somewhat requires the usage of this balanced BST (like AVL Tree) data structure: Kattis - compoundwords and Kattis - baconeggsandspam.


Try them to consolidate and improve your understanding about this data structure. You are allowed to use C++ STL map/set, Java TreeMap/TreeSet, or OCaml Map/Set if that simplifies your implementation (Note that Python doesn't have built-in bBST implementation).

X Esc
Zurück
PgUp
Weiter
PgDn

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

X Esc
Zurück
PgUp
Weiter
PgDn
Alle Schritte werden in der Status Anzeige erklärt während sie passieren
X Esc
Zurück
PgUp
Weiter
PgDn

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

X Esc
Zurück
PgUp
Weiter
PgDn
Kontrolliere die Animation mit Hilfe deiner Tastatur! Die Tasten sind:

Leertaste: start/stop/wiederholen
Pfeiltaste rechts/links: ein Schritt vor oder zurück
-/+: senke/erhöhe die Geschwindigkeit
X Esc
Zurück
PgUp
Weiter
PgDn
Kehre zum 'Exploration Mode' zurück und beginne zu Erforschen
X Esc
Zurück
PgUp

Erstellen

Einfügen
(v)

Entfernen
(v)

Pred-/Succ-essor(v)

Inorder Traversierung

>

Leer

Unbalanced Example

Balanced Example

Zufällig

Linksschief

Rechtsschief

v =

Gehen

v =

Gehen

v =

Hole Vorgänger

Hole Nachfolger

Über
Mannschaft
Nutzungsbedingungen

Über

VisuAlgo wurde konzeptioniert 2011 von Dr Steven Halim als ein Tool um seinen Studenten zu helfen Datenstrukturen und Algorithmen besser zu verstehen, indem sie die Grundlagen alleine und in ihrem eigenen Tempo lernen können.
VisuAlgo enthält viele fortgeschrittene Algorithmen die auch in Dr Steven Halim's Buch ('Competitive Programming', co-author ist sein Bruder Dr Felix Halim) und mehr. Heute, können die Visualisierungen/Animationen vieler fortgeschrittener Algorithmen nur auf VisoAlgo gefunden werden.
Obwohl die Visualisierungen speziell für die verschiedenen Datenstruktur und Algorithmik Kurse der National University of Singapore (NUS) gemacht sind, freuen wir uns, als Befürworter des Online Lernens, wenn auch andere neugierige Geister unsere Visualisierungen nützlich finden.
VisuAlgo ist nicht designed um gut auf kleinen Touchscreens (z,B, Smartphones) zu funktionieren, da die Darstellung komplexer Algorithmen viele Pixel benötigt und click-and-drag Aktionen zur Interaktion. Die minimale Bildschirmauflösung für ein akzeptables Benutz Erlebnis ist 1024x768 und nur die Startseite ist einigermaßen mobilfähig.
VisuAlgo ist ein laufendes Projekt und weitere komplexe Visualisierungen werden weiterhin entwickelt.
Die aufregendste Entwicklung ist der automatisierte Fragen Generator und Überprüfer (das Online Quiz System), dass Studenten erlaubt deren Wissen über grundlegende Datenstrukturen und Algorithmen zu testen. Die Fragen werden mit der Hilfe einiger Regeln zufällig generiert und die Antworten der Studenten werden automatisch von unserem Bewertungs Server bewertet. Das Online Quiz System, wenn es von mehr Informatik Tutoren übernommen wird, sollte eigentlich grundlegende Datenstrucktur- und Algorithmikfragen in Klausuren an vielen Universitäten ersetzten. Indem man ein wenig (allerdings nicht null) Gewicht darauf legt, dass das Online Quiz bestanden wird, kann ein Informatik Tutor (stark) das Können seiner Studenten was solche grundlegenden Fragen betrifft erhöhen, da die Studenten eine nahezu unendlich Anzahl ein Trainingsfragen beantworten können bevor sie das Online Quiz machen. Der Training Modus enthält aktuell Fragen für 12 Visualisierungsmodule. Die letzten 8 werden bald folgen, sodass es für alle Visualisierungsmodule ein Online Quiz gibt.
Eine weitere aktive Abteilung ist das Internationalisierungs Sub-Projekt von VisuAlgo. Wir wollen eine Datenbank für alle Informatik Begriffe aus alle englischen Texte im VisuAlgo System anlegen. Das ist eine große Aufgabe und benötigt Crowdsourcing. Sobald das System funktionstüchtig ist, werden wir VisuAlgo Besucher dazu einladen. Besonders wenn sie keine englischen Muttersprachler sind. Aktuel, haben wir auch verschiedene Notizen in verschiedenen Sprachen über VisuAlgo:
zh, id, kr, vn, th.

Mannschaft

Projektleiter & Berater (Juli 2011 bis heute)
Dr Steven Halim, Senior Lecturer, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Software Engineer, Google (Mountain View)

Studentische Hilfskräfte 1 (Jul 2011-Apr 2012)
Koh Zi Chun, Victor Loh Bo Huai

Abschlussprojekt/UROP Studenten 1 (Jul 2012-Dec 2013)
Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy

Abschlussprojekt/UROP Studenten 2 (Jun 2013-Apr 2014)
Rose Marie Tan Zhao Yun, Ivan Reinaldo

Studentische Hilfskräfte 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

Abschlussprojekt/UROP Studenten 3 (Jun 2014-Apr 2015)
Erin Teo Yi Ling, Wang Zi

Abschlussprojekt/UROP Studenten 4 (Jun 2016-Dec 2017)
Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir

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

Danksagungen
Dieses Projekt wird durch den großzügigen Teaching Enhancement Grant des NUS Centre for Development of Teaching and Learning (CDTL) ermöglicht.

Nutzungsbedingungen

VisuAlgo ist kostenlos für die Informatik-Community dieses Planeten (natürlich auch von Leute nicht von der Erde). Wenn dir VisuAlgo gefällt, ist die einzige Bezahlung um die wir bitten, das du anderen Informatik Studenten und Tutoren von dieser Seite erzählst. =) über Facebook, Twitter, Kurs Internet Seit, Blog Eintrag, Email usw.

Bist du ein Datenstruktur oder Algorithmik Student/Tutor, darfst du diese Webseite für deine Kurse nutzen. Solltest du Screenshots (Videos) von dieser Seite machen, darfst du diese woanders verwenden, solange du die URL dieser Seite (http://visualgo.net) als Referenz angibst. Es ist allerdings NICHT erlaubt VisuAlgo (client-Side) Dateien herunter zu laden und diese auf deiner eigenen Website zu hosten, da das ein  Plagiat wäre. Es ist auch NICHT erlaubt eine Anspaltung dieser Website zu machen und Varianten von VisuAlgo zu erstellen. Eine private Nutzung einer offline Kopie (client-side) von VisuAlgo ist erlaubt.

Beachte allerdings das VisuAlgo's Online Quiz System von Natur aus eine schwere Server-seitige Komponente hat und es gibt keinen einfachen Weg die Server-seitige Scripts und Datenbanken lokal zu speichern. Aktuell kann die allgemeinen Öffentlichkeit nur den 'Trainings Modus' nutzen um an das Online Quiz System zu kommen. Der 'Test-Modus' ist eine kontrollierterte Umgebung in der zufällig generierte Fragen und automatische Überprüfung für eine echte Prüfung in NUS genutzt werden. Andere interessierte Informatik Tutoren sollten Steven kontaktieren, wenn sie auch diesen 'Test-Modus' ausprobieren wollen.

Liste der Publikationen

Diese Arbeit wurde kurz beim CLI Workshop beim ACM ICPC Weltfinale 2012 (Polen, Warschau) und bei der IOI Konferenz bei IOI 2012 (Italien, Sirmione-Montichiari). Du kannst du diesen Link klicken um unser 2012 Paper über dieses System zu lesen (Es hieß 2012 noch nicht VisuAlgo).
Diese Arbeit wurde wurde hauptsächlich von ehemaligen Studenten gemacht. Die letzten Ergebnisse sind hier: Erin, Wang Zi, Rose, Ivan.

Bug Reports oder Anfragen zu neuen Features

VisuAgo ist kein fertiges Projekt. Dr Steven Halim arbeitet aktiv daran VisuAlgo zu verbessern. Wenn du beim benutzten von VisuAlgo in einer Visualisierung/Online Quiz einen Bug findest oder ein neues Feature möchtest, kontaktiere bitte Dr Steven Halim. Sein Kontakt ist die Verkettung seines Namens und at gmail dot com.