Binary search tree software

We have nothing to work with, since elements E is []. The solution is to check first to see whether k is bound in t. Only bound keys need be in the list of elements:. Proving correctness requires more work than completeness. Hint Transparent uncurry. Prove that elements t is sorted by keys.

Print NoDup. To state that theorem, we first need to formalize what it means for two lists to be disjoint:. A Faster elements Implementation. This corollary illustrates a general technique: prove the correctness of a simple, slow implementation; then prove that the slow version is functionally equivalent to a fast implementation. The proof of correctness for the fast implementation then comes "for free".

An Algebraic Specification of elements. But for the second equation, we have to express the result of inserting k , v into the elements list for t , accounting for ordering and the possibility that t may already contain a pair k , v' which must be replaced. The following rather ugly function will do the trick:.

Moreover, this equation doesn't tell us anything directly about the overall properties of elements t for a given tree t. Nonetheless, we can proceed with a rather ugly verification.

Model-based Specifications. In general, model-based specifications may use an abstraction relation, allowing each concrete value to be related to multiple abstract values. But in this case a simple abstraction function will do, assigning a unique abstract value to each concrete one.

We also need a bound operation on maps. 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. 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. 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. 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 At this point, we encourage you to press [Esc] or click the X button on the bottom 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.

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 There are several known implementations of balanced BST, too many to be visualized and explained one by one in VisuAlgo. 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.

Instead, we compute O 1 : x. 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. 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. 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? 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. 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: Kattis - compoundwords 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: stevenhalim at gmail dot com.

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.

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. However, we are currently experimenting with a mobile lite version of VisuAlgo to be ready by April 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 12 visualization modules so that every visualization module in VisuAlgo have online quiz component. Currently, we have also written public notes about VisuAlgo in various languages:. VisuAlgo is free of charge for Computer Science community on earth.

However, you are NOT allowed to download VisuAlgo client-side files and host it on your own website as it is plagiarism. Using the offline copy of client-side VisuAlgo for your personal usage is fine. Note that VisuAlgo's online quiz component is by nature has heavy server-side component and there is no easy way to save the server-side scripts and databases locally. Currently, the general public can only use the 'training mode' to access these online quiz system.

Currently the 'test mode' is a more controlled environment for using these randomly generated questions and automatic verification for real examinations in NUS. You can click this link to read our paper about this system it was not yet called VisuAlgo back in 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. Disclosure to all visitors: We currently use Google Analytics to get an overview understanding of our site visitors.

We plan to change this to a more privacy-friendly alternative tracker soon e. For NUS students enrolled in modules that uses VisuAlgo: By using a VisuAlgo account a tuple of NUS official email address, NUS official 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 module lecturer to keep track of your e-lecture slides reading and online quiz training progresses that is needed to run the module 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 module unless you choose to keep your account OPT-IN. Access to the full VisuAlgo database with encrypted passwords is limited to Steven 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 be tracked similarly as a normal NUS student account above but it 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 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.

Binary Search Tree 2. Motivation We have to decide what to do when the node that we want to insert has a key value equal to the key of some node already in the tree.

If during insert we find a node that duplicates the key value to be inserted, then we have two options. If the application does not allow nodes with equal keys, then this insertion should be treated as an error or ignored. If duplicate keys are allowed, our convention will be to insert the duplicate in the left subtree.

The shape of a BST depends on the order in which elements are inserted. A new element is added to the BST as a new leaf node, potentially increasing the depth of the tree. This would happen if, for example, all elements were inserted in sorted order. In general, it is preferable for a BST to be as shallow as possible. This keeps the average cost of a BST operation low. Removing a node from a BST is a bit trickier than inserting a node, but it is not complicated if all of the possible cases are considered individually.

Before tackling the general node removal process, we will first see how to remove from a given subtree the node with the largest key value. This routine will be used later by the general node removal function. The return value of the deletemax method is the subtree of the current node with the maximum-valued node in the subtree removed. Similar to the inserthelp method, each node on the path back to the root has its right child pointer reassigned to the subtree resulting from its call to the deletemax method.

A useful companion method is getmax which returns a pointer to the node containing the maximum value in the subtree. Now we are ready for the removehelp method. Thus, the question becomes: Which value can substitute for the one being removed?

It cannot be any arbitrary value, because we must preserve the BST property without making major changes to the structure of the tree. Which value is most like the one being removed? The answer is the least key value greater than the one being removed, or else the greatest key value less than or equal to the one being removed.