BinarySearchTrees - Algoviz Wiki

Works

Yes

Description

Allows the user to see a number of binary tree variants, including the BST and AVL trees. Users don't just watch a visualization, they can also interact by indicating where they believe the next node should be inserted, etc. Note: URL above is for Version 2.0. Version 1.0 can be found at http://www.iu.hio.no/~ulfu/AlgDat/applet/binarytreesome/

Evaluation

Strengths: Clear presentation of the content. Students are not just passive observers, but can show their knowledge by selecting where the next action should take place.

Exploring the Concept

Screenshots

Videos

References

This is a Java applet, so just clicking on the link should bring it up in the web browser. After selecting a tree from the menu item, you can "queue up" a series of numbers in the text box. Then, one by one, the next number is presented in the upper left corner. Each number should be dragged to the appropriate spot in the tree. Initially, you just see a little ball in the upper left corner, and an open circle in the upper right/middle of the pane. Drag the green ball on the left to the open (white) circle. If you run out of numbers "queued up" then just type in some more. There are reports of problems with running this applet on the Mac.

First Visited

2005-09-01

Last Visited

2009-07-29

Last Updated

2007

Topic

Community

Average rating:	5.0
Your rating:	You must be logged in to Rate.

http://www.cs.hut.fi/Research/TRAKLA2/exercises/index.shtml

Edit

You may edit this entry if you have an account.

Trakla - Binary Search Tree

Recommendation

Recommended

Link

Delivery Method

Java Application

License

GPL

Language

English

Author

Ville Karavirta; Ari Korhonen; Lauri Malmi; Kimmo Stålnacke

Institution

Helsinki University of Technology

Project

Trakla2

Works

Yes

Description

A collection of exercises related to searching, inserting into, and deleting from BSTs. User points at the appropriate node, or drags-and-drops nodes as appropriate.

Evaluation

This works well as an exercise, since the mechanics are at the right level of granularity to gain understanding without becoming too repetitive. The exercises are easy to use. Several exercises are included.

Canned Data; Predictions

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-29

Last Visited

2008-07-29

Last Updated

2006-01-25

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://jhave.org/learner/

Edit

You may edit this entry if you have an account.

JHAVÉ - Binary Search Tree

Recommendation

Recommended

Link

Delivery Method

Java Web Start

License

CreativeCommons

Language

English

Author

Tom Naps

Institution

University of Wisconsin - Oshkosh

Project

JHAVÉ

Works

Yes

Description

Visualization for Binary Search Tree. Includes dynamically highlighted pseudo code. Users can select random data, or seed a collection of values to insert/delete

Evaluation

The AV is set up as a series of "slides" in one pane, and pseudocode in the adjacent pane. As the user steps through the "slides", the associated pseudocode is highlighted. Occasional questions pop up for the user to answer. This works even when the user is giving their own data... the user has to pre-list the values to be inserted and deleted, and then the whole series of slides is generated by the system for play-back. Does a nice job in general of showing how the values are inserted/deleted. Some of the intermediate steps can be a little hard to follow, especially on delete, since there is an instantaneous jump between slides.

Step Control; Questions; Random Data; User Data

Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-08

Last Visited

2008-07-08

Last Updated

2008-07-01

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://people.ksp.sk/~kuko/bak/

Edit

You may edit this entry if you have an account.

Visualisation of search trees

Recommendation

Unrated

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Kubo Kovac

Institution

Comenius University, Slovakia

Project

Kovac's Tree Project

Works

Yes

Description

This AV shows various search trees such as AVL, BST, B tree, red-black tree, AA tree, skiplist, heap, treap, scapegoat tree and splay tree. It demonstrates insertion, deletion and search. Users can start with randomly generated input dataset or user's own data. For the data structuers where this is relevent, it provides balance factors such as ‘+’, ‘-‘ and ‘.’ by the nodes.

Evaluation

Strengths: The best feature of this tool is to provide many search trees. This may allow learners to identify how the search trees work by comparison with each other. Randomly generated dataset lets users quickly see the structure of the tree. Users can also construct their own data set. Weaknesses: Like many tree AVs, it just shows the result of the insert or delete operation, without explaining how it works. What is neeed is good textual explanation about each search structure and documentation explaining basic key concepts such as balance factors, re-balancing, etc. The text size of balance factors on the nodes is too small to be recognized (you need to use the "big" version of the applet to see them at all).

Exploring the Concept; Comparison; Lecture Aid

Screenshots

Videos

References

First Visited

2007

Last Visited

2008-06-12

Last Updated

2007

Topic

Community

Average rating:	4.0
Your rating:	You must be logged in to Rate.

http://nova.umuc.edu/~jarc/idsv

Edit

You may edit this entry if you have an account.

Interactive Data Structure Visualization - Binary Search Trees

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

By Request

Language

English

Author

Duane J. Jarc

Institution

University of Maryland University College

Project

IDSV

Works

Yes

Description

This AV performs fundamental operations of Binary Search Trees (BST): Find, Insert and Delete. Find operation examines a given search key or detect that it is not present in the tree. Insert operation inserts a node with a given key to the tree only if it is not found. Delete operation remove a node with a given key and restore the tree if necessary. Three operations are smoothly animated and not hard to follow them. The dataset and keys (nodes) for three operations are randomized each time users performs operations, or it provides a option to choose “I’ll pick” mode which allows users to directly enters keys. Thus, users can construct their own tree or the AV can randomly generate the trees. The AV shows fairly simple visualizations, and it provides the option to either animate the algorithm procedures or step through the visualization by users. It has an "I'll Try" mode and in this mode users are asked to select what are the next steps or keys of BST for selected operations. Also, users can check their progress how many their tries are correct or incorrect. While animation is running or users are interacting with the visualization, it provides textual feedbacks about how the steps take. It must use IE.

Evaluation

Unlike most of the other AV, this AV provides an interactive prediction features. Users can not only watch animations, but also interactively predict the next step of BST by answering question given by the visualization or directly clicking a proper node. Thus, users can ensure their understanding of BST algorithm by actively predicting the next steps. In this prediction mode, the AV provides textual feedbacks which are accompanied by every user activity and visualization. In many AV, the lack of the significant benefits of using AV was often attributable to the AV that failed to actively engage the students, but this AV allows learners to test whether being able to predict the future steps of the BST algorithm, and that would improve learning about the algorithm. In particular, since the user’s activities are coupled with the textual feedback about each answer that the users enter or click a node for BST, the visualization can proactively engage and involve users. This AV provides relatively simplistic features, and many of useful features, such as multiple views, pseudo codes, algorithm explanation and performance information, are not present in the visualization. Simple stepwise presentation of the behavior of BST using animation which comes with a short description would be useful for understanding it. Users can speed up for the easy part and slow down the difficult part to take a moment to examine what is happening. Although it is static and not connected to the AV, a brief overview of BST algorithm was useful. It would have been more beneficial if explanation of entire algorithm or pseudo code is coupled with the visualization. Overall, a good AV, but a bit simplistic since all the user can do is show where the node is inserted, or click on node to delete.

Random Data; Predictions

Lecture Aid; Self Study; Lab Exercise

Screenshots

Videos

References

First Visited

2006-08-01

Last Visited

2008-07-15

Last Updated

2005-12-03

Topic

Community

Average rating:	3.0
Your rating:	You must be logged in to Rate.

http://gustavus.edu/academics/mcs/max/concabs/applets/BST/

Edit

You may edit this entry if you have an account.

Virtual Manipulative -- BST search

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Max Hailperin

Institution

Gustavus Adolphus College

Project

Works

Yes

Description

Shows in detail how to insert into a BST, using a display based on "opening nested boxes" when a given branch is followed.

Evaluation

This AV has some interesting ideas. A good aspect is that it shows in some detail how search is done in a BST, from the "point of view" of the algorithm working through the tree. This is in contrast to standing back and seeing pointers moving through the tree. It might help students see this in a new perspective. It is also good in that it focuses on how the find algorithm works, rather than just seeing the result. The main downside is that it doesn't do anything more than find, which is generally not a difficult concept for students. It would not be a big step to extend this to insert. All that would be needed is to have the inserted value sit below the tree area, and the user can move it into the appropriate box (empty leaf node) when it becomes available. I don't see immediately how this could be extended to deletion, which is what students really have trouble with.

Random Data; Step Control

Teaching the Concept

Screenshots

Videos

References

First Visited

2008-03-17

Last Visited

2009-04-28

Last Updated

1999

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://dbs.mathematik.uni-marburg.de/research/projects/dsn/

Edit

You may edit this entry if you have an account.

Data Structures Navigator - Binary Search Trees - "natural"

Recommendation

Has Potential

Link

Delivery Method

Java Application

License

Unavailable

Language

English

Author

Jens-Peter Dittrich; Jochen van den Bercken; Tobias Schäfer; Marcus Klein

Institution

Phillips-University of Marburg

Project

Data Structure Navigator

Works

Yes

Description

Allows user to add/find/remove values in a BST

Evaluation

No pseudocode or explanation of the process, just a fairly standard visualization showing where nodes are inserted into a tree (including the path gone down to find the location), and similar for deletion.

Step Control; Animation; User Data

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2006-09-01

Last Visited

2008-07-16

Last Updated

2000-07-31

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.usfca.edu/galles/visualization/download.html

Edit

You may edit this entry if you have an account.

Data Structure Visualization - Binary Search Tree

Recommendation

Not Recommended

Link

Delivery Method

Java Application

License

Unlicensed Sourcecode

Language

English

Author

David Galles

Institution

University of San Francisco

Project

Data Structure Visualization

Works

Yes

Description

Allows users to input values, find, and delete.

Evaluation

The visualization is limited. There is no code shown, and there is no explanation of what is happening. All you see is basically the results from inserting/deleting the value.

User Data

Lecture Aid; Debugging

Screenshots

Videos

References

First Visited

2006-09-01

Last Visited

2008-07-01

Last Updated

2006-04-05

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.csanimated.com/animation.php?t=Binary_search_tree

Edit

You may edit this entry if you have an account.

CS Animated - Binary Search Tree

Recommendation

Has Potential

Link

Delivery Method

Flash

License

Non-Commercial

Language

English

Author

Bill Jacobs

Institution

None

Project

Jacobs' AV Lectures

PartOfCollection

Works

Yes

Description

A basic introduction to BSTs. A multimedia lecture, with audio used to explain the data structure and a series of slides for the visual component. Each slide has its own video component, so it is easy to move through the lecture. Each slide has flash animation as appropriate.

Evaluation

Not interactive, but in that sense it is certainly no worse than a standard animation. The presentations are generally clear, but students will likely have trouble understanding how deletion works from the presentation. See also the link http://www.csanimated.com/animation.php?t=Self-balancing_binary_search_tree for an overview of how BSTs can be self-balancing, and http://www.csanimated.com/animation.php?t=Tree_rotation for an overview of balancing rotations.

Animation Only; Canned Data

Self Study

Screenshots

Videos

References

First Visited

2008-06-23

Last Visited

2008-06-23

Last Updated

2008-06-01

Topic

Community

Average rating:	3.0
Your rating:	You must be logged in to Rate.

http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/BSTNew.html

Edit

You may edit this entry if you have an account.

Java Applets Centre - Binary Search Tree

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

R. Mukundan

Institution

University of Canterbury

Project

Java Applets Centre

Works

Yes

Description

This AV allows users to perform Insert, Search and Delete Operations in a Binary Search Tree. User can either pick a new value to insert/search/delete, or pick a random value. Nodes are highlighted as they are visited during the operations. A small description provided along with search code snippet. The code snippets are however not traced though as the algorithm works. This site as a second AV for just BST search which is not at all useful.

Evaluation

No explanation of what is happening during the operations. Visualization good enough only for beginners and for simple trees. The visualization doesn’t work for trees of height greater than 5. Moreover, when the user tries to insert an element which would lead to a tree of height greater than 5, no message is displayed stating that the visualization doesn’t support dynamic layout of the graphs. No message displayed upon the end of search and delete operations. Similarly, no message is displayed when an element is inserted/deleted.

Lecture Aid

Screenshots

Videos

References

First Visited

2008-04-29

Last Visited

2008-07-21

Last Updated

2006

Topic

Community

Average rating:	3.0
Your rating:	You must be logged in to Rate.

http://www.cs.jhu.edu/~goodrich/dsa/trees/btree.html

Edit

You may edit this entry if you have an account.

Animated Binary Tree

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unlicensed Sourcecode

Language

English

Author

John Kloss; Michael Goodrich

Institution

Johns Hopkins University

Project

Goodrich's Collection

PartOfCollection

Works

Yes

Description

Type in numbers, you see the path through the tree to where it goes. Hard to really understand the algorithm from this.

Evaluation

Strengths: simple UI, animated insert/delete. Weaknesses: difficult to get a sense of the algorithm

Exploring the Concept; Debugging

Screenshots

Videos

References

First Visited

2006-08-01

Last Visited

2006-08-01

Last Updated

1997-08-05

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/BST-Example.html

Edit

You may edit this entry if you have an account.

Standard Binary Search Tree

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Language

English

Author

Doug Ierardi

Institution

Technische Universität Braunschweig

Project

Works

Yes

Description

This AV is very interesting visualization for Binary Search Tree (BST). This BST visualization has physics; the balls hang from elastic cords. It only provides very simplistic features and focuses on basic operations on a BST through highly intuitive animation computed by physical simulations. It allows users to perform the operations of the BST such as Insert, delete, and locate. Instead of just stepping through the visualization, Users can directly choose one of the nodes on the BST by clicking it, and then run one of the basic operations (Insert, Delete, and Location) for that node. Also, the visualization is accompanied by short explanation at each step of the algorithm. Users can configure the default settings for some user-selectable styles of tree shapes, and animation properties. The data is only randomly generated, and user cannot experiment with his/her own data. And, This AV supports only continuous mode operation of the animation, and users cannot step through the animation at user’s own speed or with controls. The visualization automatically step forward the Binary search algorithm.

Evaluation

This AV looks fairly pleasant, and the fundamental operations of BST are visually presented. The lack of many extra features, such as animation control and user input data, is a major drawback of this AV. On the other hand, it provides a compact interface and fairly neat visualization which rarely distract a user who is learning a BST. I could see some benefits for this AV. In particular, its visualization is quietly intuitive, and a user is likely to raise his or her awareness from node's physical movements while learning about BST. This AV allows user to directly participate in constructing the visualization through interactivity. The user can select a node and execute available basic operations. This nice point-and-click functionality also makes the AV easy to use. However, without any advance knowledge of BST it seems that it is hard to learn the algorithm from this. It provides short textual information which is coupled with the visualization, but it would be insufficient for understanding how BST's basic operations work. If it included some document and explanation about operations of BST, this AV would have been more beneficial. A continuous operation doesn’t allow users to take a moment to examine what is happening and what the algorithm is doing at a current step. Also, since the execution history is not maintained, it is difficult for users to keep track of the state changes of BST algorithm. It would be much useful if a user was able to enter their own input data that allows them to directly explore how their input data can construct the binary search tree. If the user could execute basic operations, such as input, delete, and location with user’s input node, the user could engage and involve the BST visualization actively. This AV can be used either as part of a lecture by an instructor and along with instructor’s explanation. This AV would be useful for conveying some concepts of BST to students. Also, it can be provided as supplements for static presentations.

Lecture Aid; Teaching the Concept

Screenshots

Videos

References

First Visited

2006-08-01

Last Visited

2006-08-01

Last Updated

1996

Topic

Community

Average rating:	3.0
Your rating:	You must be logged in to Rate.

http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/binarySearchTree/bst.html

Edit

You may edit this entry if you have an account.

Ghosh - Binary Search Tree

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

R. K. Ghosh

Institution

Indian Institute of Technology, Kanpur

Project

Ghosh's Collection

PartOfCollection

Works

Yes

Description

Shows basic presentation for BST operations.

Evaluation

Has step-by-step presentation showing what the operations are doing. It would help if there were speed control for the animations that take place along with each step.

Lecture Aid; Self Study; Debugging

Screenshots

Videos

References

First Visited

2006-08-01

Last Visited

2008-07-15

Last Updated

2001-08-11

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://research.cs.vt.edu/AVresearch/Swan/

Edit

You may edit this entry if you have an account.

SWAN - Binary Search Tree

Recommendation

Not Recommended

Link

Delivery Method

Windows Application

License

GPL

Language

English

Author

Jun Yang; Cliff Shaffer

Institution

Virginia Tech

Project

Swan

Works

Yes

Description

Part of the SWAN distribution. Users can insert and delete nodes in a BST.

Evaluation

Limited usefulness, since the user specifies a node value and the resulting tree is shown. No explanation is given for how the insert takes place. User can also select a node to delete, and it is immediately deleted.

User Data

Lecture Aid; Debugging

Screenshots

Videos

References

First Visited

2006-11-08

Last Visited

2008-06-27

Last Updated

1996

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www.cs.queensu.ca/home/jstewart/applets/bst/bst-rotation.html

Edit

You may edit this entry if you have an account.

Tutorial on Binary Search Tree Rotation

Recommendation

Unrated

Link

Delivery Method

Java Applet

License

Language

English

Author

James Stewart

Institution

Queen's University

Project

Works

Yes

Description

BST rotation tutorial with minimal interactivity until the final example.

Evaluation

Strengths: nice descriptions, limited actions allow only "correct" movements except for the final visualization, nice built-in data set. Weaknesses: no user-definable data sets

Teaching the Concept

Screenshots

Videos

References