SplayTrees - Algoviz Wiki

Works

Yes

Description

Includes RedBlackTrees, BinarySearchTrees, and SplayTrees. It allows the user to create randomly generated input data or to insert user’s own input data for a splay tree in different formats such as integer, double, and character. Users can construct a splay tree by directly inserting, deleting, and splaying tree nodes to the top. The user can also select different tree operations such as in, pre- and post-order traversals. It provides a number of flexible user controls including the speed control, stop, forward, backward steps, etc. Text-based descriptions are displayed for each algorithm step. The textual descriptions include miscellaneous information about the tree including the size, number of elements and depth. This text information can define a history of the algorithm.

Evaluation

One of the best AVs for the splay tree. It provides interaction-oriented operations and adjustable spatial layout with intuitive animations. This AV includes almost all necessary features for the splay tree. Randomly generated input data offered many advantages for a beginner to start with some input. It also allows constructing the splay tree with user’s own input dataset. The graphic representation and animation for the splay tree is intuitive and helpful for understanding each algorithm step. A small text window lists algorithm steps that are performed. The AV has a simple, intuitive interface. For new users, it can be difficult to get started, though, since there is no help facility or introduction to the AV. The user can select a node by clicking it. A context menu then appears which allows double rotation, splay to the top, and delete. Controls at the top allow nodes to be inserted. There are some weaknesses.The layout is spacious but the number representation seems sometimes misleading during the animation and transformation. There is a problem with scalability of nodes in representation of the tree. When the number of elements in the tree grows beyond 10, the nodes become too small for the user to read. There is no quiz or exercise mode to encourage self-evaluation. Some controls ambiguous . For example, although those controls present on the interface menu, backwards and forwards steps of the animation don't seem to do anything. The history window is too small.

User Data; Random Data

Teaching the Concept; Exploring the Concept

Screenshots

Videos

References

First Visited

2006-06-07

Last Visited

2009-06-02

Last Updated

2002-08-29

Topic

Community

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

http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm

Edit

You may edit this entry if you have an account.

SplayJavaModel

Recommendation

Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Arsen Gogeshvili

Institution

University of LA Laguna

Project

Works

Yes

Description

This visualization allows random generation of input; as well as user defined input. It has sound options that work seamlessly with all the animations. The tool allows users to control the step-wise operations by pausing the animation or changing the animation speed. Description of each operation as well as pre and post-order traversals are available in the visualization. Other fancy options like shape control feature and direction control features are also included. Moreover, images on command buttons help users use this tool intuitively. The visualization also shows the basic splay operation, which was missing in most other splay tree visualizations.

Evaluation

This visualization provides several options like user defined data, step-wise speed control, description of each operation with valuable visual effects. It also provides sound effects and animation effect, in particular, rotation signs before executing operations. This application is highly intuitive with simple and neat animation. The descriptions after the operation has completed give an insight into what operations the Algorithm visualization went through. The algorithm write up provided by the author is also insightful. Interface provides options to insert node, delete node and find nodes in predetermined or user defined dataset. It also provides good control over the speed of animation. Despite its neat design, the visualization is missing some options. The next button is missing (hence no step by step trace capability) which could have been an added advantage. The layout is pretty decent but it can not support a large set of numbers. It shows the basic splay operation which was missing in earlier visualizations. But sadly, one can not control the pacing of the splay operation and it splays the node selected to the root through a series of fast visual iterations. One needs to control the pace of these iterations to have better understanding of the Splaying concept which forms the basis of Splay trees. Further, once we press “Splay” button, there is no getting back. One has to have a basic knowledge of the BSTs and Self Balancing trees to work with this visualization and this cannot be given to novices who have not taken any Data Structures course till now. Providing pace control, “Previous” and “Next” Buttons, and a short text Box that explains what happened in a particular iteration would make this AV a very potent and useful tool for all user groups.

User Data; Random Data; Animation

Teaching the Concept; Exploring the Concept

Screenshots

Videos

References

First Visited

2008-02-10

Last Visited

2008-02-17

Last Updated

2002-05-18

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

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

PartOfProject

Works

Yes

Description

Allows user to give values to insert/find/delete in SplayTree. Smooth animation of the movements for nodes.

Evaluation

Easy to use interface, nice graphics. The main problem is that there is no explanation of what is going on. The user can step through the splay operations one by one, but any given splay operation happens rather quickly with no explanation of the process. So the user needs to already understand how the splay tree works (at least in principle) to get much from this.

Step Control; Animation; User Data

Lecture Aid; Self Study; Debugging

Screenshots

Videos

References

First Visited

2006-09-01

Last Visited

2008-07-16

Last Updated

2000-07-31

Topic

Community

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

http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/SplayTree-Example.html; http://aleph0.clarku.edu/%7Eachou/cs102/examples/bst_animation/

Edit

You may edit this entry if you have an account.

Splay Tree Applet

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unlicensed Sourcecode

Language

English

Author

Doug Ierardi; Ta-Wei Li

Institution

University of Southern California

Project

Works

Yes

Description

This AV is a physics simulation-based java applet that provides text explanations and animations for the splay tree together. It demonstrated just Splay Trees unlike many other tools that provides more algorithms such as BST, AVL. It allows users to execute the basic function of splay, insert, delete and locate. It has highly intuitive animations but with limitative user control options. There is no animation speed control, no user input data, no random data generation, no ‘BACK’ and ‘NEXT’ button, no step animation. Instead of allowing them to make their own data, it allows users to click one of nodes, execute one of operation such as find, delete and insert.

Evaluation

The SplayJavaTree has good features. First, its animation is neat and highly intuitive due to using physics based simulation. In addition, it provides good description about each step performed. The web page explains about Splay trees in brief which is very helpful in getting started. The algorithm documentation provided along the AV also proves pretty nifty when it comes to the understanding of the basic functionality of the splay trees. An AV page for the basic operation rotation is made separately. There is a very simple step instruction and pseudo code. It provides random generation of input. This feature will provide beginners with convenience although it advanced learners need more functionality, user own data generation. Input is automatically generated when an operation is selected on a node. In other words, through interactivity through mouse selection users can select a node and perform the available operations. This tool is good visualization tool for understanding the algorithm since it uses nice animation to display various nodes with different color and operation that are performed on these nodes. Although the SplayJavaTree provides nice features for beginners, it needs to be improved in some sense. Most of all, it provides users with option for user’s own data construction, it is very important to understand algorithm for naïve users. This feature would meaningful in terms of constructivism or situated cognition by providing users with cognition environment to be convenient to them. It has neither history maintained nor no animation speed control. There are no buttons such as next or back, reverse which would allow stepwise tracing. To make this AV more beneficial, one can include some documentation and static pictures of how the rotation actually takes place and what is zig-zag movement exactly. Note: The links above appear to be from courses that installed copies of the distribution. The original USC distribution appears to be missing.

Teaching the Concept

Screenshots

Videos

References

First Visited

2006-06-07

Last Visited

2010-02-16

Last Updated

1996

Topic

Community

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

http://www.cs.miami.edu/~burt/projects/Archive/trees/Splay/

Edit

You may edit this entry if you have an account.

SplayTreeJava

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unlicensed Sourcecode

Language

English

Author

Burton Rosenberg

Institution

University of Miami

Project

Works

Yes

Description

The page contains a little description of how splay trees work and a very basic visualization. There are two buttons ('Clear Tree' and 'Insert to Tree') and a text field, allowing the user to enter elements to be inserted into the tree. The user can also click on the nodes of the tree to perform a splay at that point.

Evaluation

The documentation accompanying this visualization does a reasonable job of explaining the concept of splay trees if all the user needs is a memory jog, but it would be insufficient as a primary document on understanding how splay trees work. The only thing that the user can do with the actual tool is insert values into the tree. There is no explanation about why values are placed where they are in the tree or how they get there. The biggest problem is that insertions are not done correctly. The tool just inserts values as if it was building a binary search tree without splaying the new node to the root (despite mentioning that this is how splay trees work in the description). The user can also splay an arbitrary point to the root (either to complete the insert correctly or to emulate search), but there is no animation to walk the user through the process - the visualization just jumps to the result. The viewing window that contains the tree is also far too small, and after a modest number of insertions, like five or six, nodes start to be obscured. What is particularly striking is that not only does the user have to supply the splay step following an insertion manually, there is no explicit support for searching (again, the user must know that splaying a node to the top of the tree is “searching”) or deleting elements from the tree. At best, this AV is incomplete and in need of major work, and at worst it is misleading and confusing.

Lecture Aid

Screenshots

Videos

References

First Visited

2007

Last Visited

Last Updated

1996-11-24

Topic

Community

Average rating:	1.5
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.

Kovac's Splay Tree

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Kubo Kovac

Institution

Comenius University, Slovakia

Project

Kovac's Tree Project

PartOfProject

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

Screenshots

Videos

References

First Visited

2007

Last Visited

2008-06-12

Last Updated

2007

Topic

Community

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

http://www.cs.nyu.edu/algvis/java/

Edit

You may edit this entry if you have an account.

Binary Search Tree Visualization

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Henning Biermann

Institution

New York University

Project

NYU Algvis

PartOfProject

Works

Yes

Description

Uses a unique "comic strip" system--instead of actively animating a single depiction of the tree, it generates snapshots of the tree's state interspersed with descriptive text. Also a general-purpose Binary Search Tree visualizer.

Evaluation

Strengths: interesting "comic strip" technique, allows user to enter data / Weaknesses: tree is prepopulated, so to define a completely unique data set, the user would have to first remove all system-provided nodes.

Exploring the Concept

Screenshots

Videos

References

First Visited

2006-06-07

Last Visited

2006-06-07

Last Updated

1998-02-25

Topic

Community

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

http://www.technion.ac.il/~itai/

Edit

You may edit this entry if you have an account.

Visualization of Splay Tree

Recommendation

Not Recommended

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Vladimir Yanovsky; Alon Itai

Institution

Technion (Israel Institute of Technology)

Project

Works

Yes

Description

Demonstration for Splay Tree. Users can enter values, and will see the steps used to perform the operation.

Evaluation

There is no stepwise operation, this is an animation for what takes place. There is no explanation of the actions taking place on the screen. It is very difficult to follow what is happening as the value is splayed up the tree.

User Data; Animation

Lecture Aid

Screenshots

Videos

References

First Visited

2007

Last Visited

2009-04-28

Last Updated

Topic

Community

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

http://www.link.cs.cmu.edu/splay/

Edit

You may edit this entry if you have an account.

Sleator's Splay Tree Demo

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Public Domain

Language

English

Author

Daniel Sleator

Institution

Carnegie-Mellon University

Project

Works

Yes

Description

Given a tree (an initial tree can easily be generated), clicking on a node will show the result of splaying from that node (effectively what would happen if you had searched for that value). Alternatively, you can ask for a value to be inserted, and it will show the resulting splay tree. Implemented as a Java Applet front-end for a tree implemented in C.

Evaluation

The big weakness of this AV is that it does not show how splaying is done. It just instantly shows the result of the search or insert operation. However, this could be helpful to determine if another implementation (such as a student project) was giving the right answer.