CS 470 Project 2

Scott Ratchford, Sam Gaines, Abbie Bosko, Audrey Kim, Summer Hawkins, Navamin Leelarburanathanakoon

Project Description

This project compares three data structures:

1. Red-Black Trees
2. Fibonacci Heaps
3. Skip Lists

The purpose of this project is to compare the three data structures on the following operations:

• Insert
• Find
• Delete

Python and Tkinter were used for the implementation of the comparison.

Overview

To begin, run tripleVisualization.py. Once the GUI has opened, the user has the option to choose how many elements they want to add to the data structures using the "elements" spinbox. The default value for this is 10.

Once element size has been chosen, the user then can then select to randomize data with the corresponding buttom to generate a new dataset.

After randomizing data, the "Start All" button begins inserting the dataset into each data structure.

The spinbox Insert allows the user to insert an element into each data structure.

The spinbox Remove allows the user to delete an element from each data structure.

The spinbox Find allows the user to find an element from each data structure.

Skip List Animation Overview

When finding an element, the algorithm traverses through the top level of the list until the next element is greater than or equal to the value. Then, the next row down is searched through in a similar fashion, and this process repeats until the element is found or not found in the bottom row. The visited nodes are colored pink in the order they are visited.

When inserting a new element, the algorithm searches for the new element's value, then inserts the new element where its value should be located. The visited nodes are colored blue in the order they are visited. The new element is inserted at a random height generated by probability function P(height = h) = 0.5^h.

When deleting an element, the algorithm searches for the element's value, then removes the element from the list if it is found. The visited nodes are colored red in the order they are visited.

Fibonacci Heap Animation Overview

Once elements are inserted, the minimum element is placed at the beginning of the root list and colored light blue. The double arrows represent a circular doubly linked list.

When inserting a new element, the algorithm checks if it is less than the existing minimum. If it is, the element is put at the beginning of the root list and colored light blue. If it is not, the element is simply added to the root list.

When deleting an element, the algorithm searches for the value. Nodes that have been searched are colored red. If the node is found, the animation removes the value and then calls merge. Each step of the merge function is shown in the animation.

When finding an element, the animation colors visited nodes pink. When it finds a root element of a tree that is less than the element it is searching for, it traverses the tree. If/when the element is found, it terminates.

Red-Black Tree Animation Overview

Once elements are inserted, much like a normal binary search tree, for every node the left child will have a lesser value and the right child will have a greater value. The nodes are colored red and black accordingly.

In node insertion/deletion/searching, the program will traverse the red black tree like a binary search tree until it gets to a leaf node or finds where the insertion/deletion/search must take place. Nodes are colored blue, red, or pink (insertion, deletion, search respectively) as they are traversed through. At this stage, a set of rules and rotations will occur in order to preserve two main properties:

1. The child of a red node is always black (there can never be two consecutive red nodes).
2. Every path from the root to the leaf will have the same number of black nodes.

Assignments:

• Skiplist: Scott, Sam
• Fib Heap: Abbie, Audrey
• RBT: Summer, Navamin