lironsade

#Fill in your runtime results in this file
#You should replace each X with the corresponding value

#These values correspond to the time it takes (in ms) to insert data1 to all data structures
OpenHashSet_AddData1 = 28751.0
ClosedHashSet_AddData1 = 187606.0
TreeSet_AddData1 = 40.0
LinkedList_AddData1 = 28863.0
HashSet_AddData1 = 37.0

lironsade

import java.util.Iterator;

/**
 * Implements an AVL tree
 */
class AvlTree implements Iterable<Integer> {
    
    /* Constructors */

    /**

lironsade

    public Iterator<Integer> iterator() {
       return new BSTIterator();
    }

    /* Package Private Methods */

    Node findSuccessor(Node node) {
        if(node == null) {
            return null;
        }

lironsade

     void setLeft(Node left) {
         this.left = left;
         if (left != null) {
             this.left.setDad(this);
             this.leftHeight = left.getHeight();
         } else {
             this.leftHeight = -1;
         }
     }

lironsade

    private void rotateLeft(Node rotated) {
        Node rotator = rotated.getRight();
        rotator.setDad(rotated.getDad());
        rotated.setRight(rotator.getLeft());
        rotator.setLeft(rotated);
        if(rotator.getDad() != null){
            if (rotator.getDad().getRight() == rotated){
                rotator.getDad().setRight(rotator);
            } else {
                rotator.getDad().setLeft(rotator);

lironsade

package oop.ex4.data_structures;

/**
 * Created by liron on 5/6/17.
 */
public class Test {
    public static void main(String[] args) {
//        AvlTree a = new AvlTree(new int[] {5,4,6,7,15,23,50,71});
        System.out.println("Test 1: " + test1());
        System.out.println("Test 2: " + test2());

lironsade

    public int contains(int searchVal) {
        Node pointer = this.getRoot();
        int depth = 0;
        while(pointer != null) {
            if(pointer.getData() == searchVal) {
                return depth;
            }
            if (pointer.getData() > searchVal) {
                pointer = pointer.getLeft();
            } else{

lironsade

private void rotateLeft(Node rotated) {
    Node rotator = rotated.getRight();
    rotator.setDad(rotated.getDad());
    rotated.setRight(rotator.getLeft());
    rotator.setLeft(rotated);
    if(rotator.getDad() != null){
        if (rotator.getDad().getRight() == rotated){
            rotator.getDad().setRight(rotator);
        } else {
            rotator.getDad().setLeft(rotator);

lironsade

    /**
     * Balances the tree according to the case
     *
     * @param pointer node to balance
     */
    private void balanceTree(Node pointer) {
        int balanceFactor = balanceFactor(pointer);
        if (balanceFactor == HEAVY_LEFT) {
            if (balanceFactor(pointer.getLeft()) == LEFT_THEN_RIGHT) {
                // LR

lironsade

    static boolean test9() {
        int[] a = {4,5,6,7,8,9};
        int i = 0;
        AvlTree b = new AvlTree(a);
        boolean flag = true;
        for (int x : b) {
            if (x != a[i])
                flag = false;
            i++;
        }