A Binary Search Tree BST is a binary tree in which each vertex has only up to 2 children that satisfies BST property: 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. By default, we show e-Lecture Mode for first time or non logged-in visitor.

Binary Search Tree - Animation

Please login if you are a repeated visitor or register for an optional free account first. 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: 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: 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:. We designed this visualization and this e-Lecture mode to look good on x resolution or larger typical modern laptop resolution in We recommend using Google Chrome to access VisuAlgo.

Go to full screen mode F11 to enjoy this setup. The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo. If we use sorted array to implement table ADT, we can improve the Search v performance but weakens the Insert v performance:.

The goal for this module 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. What are the best possible implementation for the first three additional operations if we are limited to use [sorted unsorted] array?

Phylogeny Programs (continued)

The simpler data structure that can be used to implement Table ADT is Linked List. Can we perform all basic three Table ADT operations: 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. 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? 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. Each vertex has at least 4 attributes: Not all attributes will be used for all vertices, e.

Some other implementation separates key for ordering of vertices in the BST with the actual satellite data associated with the keys.

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

There are a few other possible BST operations that are not shown as they are reserved for pedagogical purposes in NUS. Data structure that is efficient even if there are many update operations is called dynamic data structure.

BST and especially balanced BST e.

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. We keep doing this until we either find the required vertex or we don't.

On the example BST above, try clicking Search 15 found after just 1 comparison , Search 7 found after 3 comparisons , Search 21 not found after 3 comparisons. Try clicking FindMin and FindMax on the example BST shown above. The answers should be 4 and 71 both after 4 comparisons. 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 this value should not exist as we only use random integers between [ 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:.

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. 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. 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 to largest.

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. Some people call insertion of N unordered integers into a BST in O N log N and then performing the O N Inorder Traversal as ' BST sort '. It is rarely used though as there are several easier-to-use comparison-based sorting algorithms than this.

We have not included these two other classic tree traversal methods as they are not that relevant for BST. But basically, in Preorder Traversal, we visit the current root before going to left subtree and then right subtree. And in Postorder Traversal, we visit the left subtree and right subtree first, before visiting the current root. 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. By now you should be aware that this h can be as tall as O N in a normal BST as shown in the random 'skewed right' example above. 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: 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.

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. The second case is also not that hard: 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. The third case is the most complex among the three: 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. 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. 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: There will be a downloadable link to BSTDemo.

When you are ready to continue with the explanation of balanced BST we use AVL Tree as our example , press [Esc] again or switch the mode back to 'e-Lecture Mode' from the top-right corner drop down menu.

Then, use the slide selector drop down list to resume from this slide We have seen from earlier slides that most of our BST operations except Inorder traversal runs in O h where h is the height of the BST that can be as tall as N There are several known implementations of balanced BST, too many to be visualized and explained one by one in VisuAlgo.

Other balanced BST implementations are: 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. There is a dramatic difference between log 2 N and N and we have seen from the discussion of the lower bound that getting perfect BST at all times is near impossible So can we have BST that has height closer to log 2 N , i.

If we can, then BST operations that run in O h actually run in O log N Introducing AVL Tree, invented by two Russian Soviet inventors: Georgy Adelson-Velskii and Evgenii Landis, back in Therefore, most AVL Tree operations run in O log N time — efficient. Insert v and Remove v update operations may change the height h of the AVL Tree, but we will see rotation operation s to maintain the AVL Tree height to be low.

Instead, we compute O 1: Try Insert 37 on the example BST no AVL Tree rotation for now. Notice that only a few vertices along the insertion path: 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.

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? To quickly detect if a vertex v is height balanced or not, we modify the AVL Tree invariant that has absolute function inside into: Now try Insert 37 on the example AVL Tree again.

A few vertices along the insertion path: We need to restore the balance. 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. Tree Rotation preserves BST property. Basically, there are only these four imbalance cases.

We use Tree Rotation s to deal with each of them. 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 module, 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. There will be a downloadable link to AVLDemo.

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. We also have a few programming problems that somewhat requires the usage of this balanced BST like AVL Tree data structure: UVa - Hardwood Species and Kattis - baconeggsandspam.

Try them to consolidate and improve your understanding about this data structure. 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: VisuAlgo was conceptualised in by Dr Steven Halim as a tool to help his students better understand data structures and algorithms, by allowing them to learn the basics on their own and at their own pace.

VisuAlgo contains many advanced algorithms that are discussed in Dr Steven Halim's book 'Competitive Programming', co-authored with his brother Dr Felix Halim and beyond. Though specifically designed for National University of Singapore NUS students taking various data structure and algorithm classes e.

CS, CS, CS, CS, CS, and CS , as advocators of online learning, we hope that curious minds around the world will find these visualisations useful too. VisuAlgo is not designed to work well on small touch screens e. The minimum screen resolution for a respectable user experience is x and only the landing page is relatively mobile-friendly. The most exciting development is the automated question generator and verifier the online quiz system that allows students to test their knowledge of basic data structures and algorithms.

The questions are randomly generated via some rules and students' answers are instantly and automatically graded upon submission to our grading server.

This online quiz system, when it is adopted by more CS instructors worldwide, should technically eliminate manual basic data structure and algorithm questions from typical Computer Science examinations in many Universities.

The training mode currently contains questions for 12 visualization modules. We will soon add the remaining 8 visualization modules so that every visualization module in VisuAlgo have online quiz component. Another active branch of development is the internationalization sub-project of VisuAlgo. We want to prepare a database of CS terminologies for all English text that ever appear in VisuAlgo system. This is a big task and requires crowdsourcing. Once the system is ready, we will invite VisuAlgo visitors to contribute, especially if you are not a native English speaker.

Currently, we have also written public notes about VisuAlgo in various languages: Undergraduate Student Researchers 1 Jul Apr Koh Zi Chun, Victor Loh Bo Huai. Undergraduate Student Researchers 2 May Jul Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu.

Acknowledgements This project is made possible by the generous Teaching Enhancement Grant from NUS Centre for Development of Teaching and Learning CDTL. VisuAlgo is free of charge for Computer Science community on earth. If you take screen shots videos from this website, you can use the screen shots videos elsewhere as long as you cite the URL of this website http: However, you are NOT allowed to download VisuAlgo client-side files and host it on your own website as it is plagiarism.

As of now, we do NOT allow other people to fork this project and create variants of VisuAlgo. Using the offline copy of client-side VisuAlgo for your personal usage is fine.

Binary Search Tree Java Applet

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

Other interested CS instructor should contact Steven if you want to try such 'test mode'. This work has been presented briefly at the CLI Workshop at the ACM ICPC World Finals Poland, Warsaw and at the IOI Conference at IOI Sirmione-Montichiari, Italy.

You can click this link to read our paper about this system it was not yet called VisuAlgo back in This work is done mostly by my past students. The most recent final reports are here: Erin , Wang Zi , Rose , Ivan. VisuAlgo is not a finished project. Dr Steven Halim is still actively improving VisuAlgo. His contact is the concatenation of his name and add gmail dot com.

Binary Search Tree 2. What Kind of Table ADT? O log N Complexities? What about Linked List? What about Hash Table? What Are The Other BST Operations? Static vs Dynamic Data Structure 6. O h Time Complexity 7. O h Time Complexity 8. Preorder and Postorder Traversal 9. O h Time Complexity Try Exploration Mode The Combined Bound AVL Tree Summary Side Usage of Balanced BST? Return to 'Exploration Mode'.

A Table ADT must support at least the following three operations as efficient as possible: Search v — determine if v exists in the ADT or not, Insert v — insert v into the ADT, Remove v — remove v from the ADT. If we use unsorted array to implement table ADT, it can be inefficient: Search v runs in O N , as we may end up exploring all N elements of the ADT if v actually does not exist, Insert v can be implemented in O 1 , just put v at the back of the array, 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.

If we use sorted array to implement table ADT, we can improve the Search v performance but weakens the Insert v performance: Search v can now be implemented in O log N , as we can now use binary search on the sorted array, Insert v now runs in O N as we need to implement an insertion-sort like strategy to make the array remains sorted, 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.

On top of the basic three, there are a few other possible Table ADT operations: No Yes Submit Discussion: Go back to the previous 4 slides ago. We will now introduce BST data structure. See the visualization of an example BST above!

Query operations the BST structure remains unchanged: Search v , Predecessor v and similarly Successor v , and Inorder Traversal, Update operations the BST structure may likely change: Insert v , Remove v , and Create BST several criteria. 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: 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 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 If v is the maximum integer in the BST, v does not have a successor. Try Successor 71 should be none. Inorder Traversal runs in O N , regardless of the height of the BST. Insert v runs in O h where h is the height of the BST. You can use the 'Exploration mode' to verify the answer. We can remove an existing integer in BST by performing similar operation as Search v. If v is not found in the BST, we simply do nothing.

The first case is the easiest: Vertex v is currently one of the leaf vertex of the BST. This part is clearly O 1 — on top of the earlier O h search-like effort. This case 3 warrants further discussions: Why replacing a vertex B that has two children with its successor C is always a valid strategy?

Can we replace vertex B that has two children with its predecessor A instead? Why or why not? To make life easier in 'Exploration Mode', you can create a new BST using these options: So, is there a way to make our BSTs 'not that tall'? At this point, we encourage you to press [Esc] or click the X button on the top right of this e-Lecture slide to enter the 'Exploration Mode' and try various BST operations yourself to strengthen your understanding about this versatile data structure.

What are the values of height 20 , height 65 , and height 41 on the BST above? Do you know how to get skewed left BST instead? The proof is long and currently hidden.

Look at the example BST again. See that all vertices are height-balanced, an AVL Tree. Just insert v as in normal BST, 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: Is there any possible tree rotation cases for Insert v operation of AVL Tree? Just remove v as in normal BST one of the three removal cases , 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: We will end this module with a few more interesting things about BST and balanced BST especially AVL Tree.

As the action is being carried out, each step will be described in the status panel. Control the animation with the player controls! Return to 'Exploration Mode' to start exploring! About Team Terms of use.

VisuAlgo is an ongoing project and more complex visualisations are still being developed. List of Publications This work has been presented briefly at the CLI Workshop at the ACM ICPC World Finals Poland, Warsaw and at the IOI Conference at IOI Sirmione-Montichiari, Italy.

Bug Reports or Request for New Features VisuAlgo is not a finished project.