AVL-Tree/AVLTree.java at master · JimmyLindstrom/AVL-Tree · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

/**
 * Class representing an AVL-Tree extending the BinaryTree-class.
 *
 * @author Jimmy Lindström
 */

public class AVLTree extends BinaryTree {

    public AVLTree() {
        super();
    }

    /**
     * Method for adding a value to the tree, calling the insert method.
     *
     * @param data the value to be added
     */
    @Override
    public void add(int data) {
        super.add(data);
        TreeNode parent = findParent(root, data);
        if(parent != null){
            parent.setHeight();
            balanceTree(parent);
        }
    }


    /**
     * Method for deleting a node, that calls the remove method. It sets the new
     * root of the tree
     *
     * @param data the value to be deleted from the tree
     */
    @Override
    public void delete(int data) {
        TreeNode parent = findParent(root, data);
        super.delete(data);
        if (parent == null){
            TreeNode successor = findSuccessor(root);
            balanceTree(successor);
        }else{
            parent.setHeight();
            balanceTree(parent);
        }
    }

    /**Method for checking the balance of the tree after inserting/deleting
     * It calls the methods for rotating left/right if unbalanced
     *
     * @param current the node from where the balancing should start
     * @return balanced tree
     */
    private TreeNode balanceTree(TreeNode current) {
        if(current == null)
            return current;

        int balance = current.getBalance();
        // if tree is unbalanced
        if (balance > 1 || balance < -1) {

            // if it is left-heavy
            if (balance < 0) {
                // if it is left-right-heavy
                if (current.getLeft().getBalance() > 0)
                    rotateLeft(current.getLeft());
                // if it is left-left-heavy
                rotateRight(current);

                // if it is right-heavy
            } else {
                // if it is right-left-heavy
                if (current.getRight().getBalance() < 0)
                    rotateRight(current.getRight());
                // if it is right-right-heavy
                rotateLeft(current);
            }
        }
        //when the node is balanced move upp towards the root to check balance
        TreeNode parent = findParent(root, current.getData());
        if(parent != null) {
            parent.setHeight();
            balanceTree(parent);
        }

        return current;
    }

    /**Method for balancing the tree by doing a left rotation
     *
     * @param current the unbalanced node
     * @return the balanced tree
     */
    private TreeNode rotateRight(TreeNode current) {
        TreeNode parent = findParent(root, current.getData());
        TreeNode leftChild = current.getLeft();
        TreeNode rightChild = leftChild.getRight();

        leftChild.setRight(current);
        current.setLeft(rightChild);

        if (parent == null){
            root = leftChild;
        }
        if(parent != null && parent.getLeft() == current){
            parent.setLeft(leftChild);
        }else if(parent != null && parent.getRight() == current){
            parent.setRight(leftChild);
        }

        current.setHeight();
        leftChild.setHeight();

        return leftChild;
    }

    /**Method for balancing tree by doing a right rotation
     *
     * @param current the unbalanced node
     * @return the balanced tree
     */
    private TreeNode rotateLeft(TreeNode current) {
        TreeNode parent = findParent(root, current.getData());
        TreeNode rightChild = current.getRight();
        TreeNode leftChild = rightChild.getLeft();

        rightChild.setLeft(current);
        current.setRight(leftChild);
        //if current is the root
        if (parent == null){
            root = rightChild;
        }else if(parent != null && parent.getLeft() == current){
            parent.setLeft(rightChild);
        }else if (parent != null && parent.getRight() == current){
            parent.setRight(rightChild);
        }
        current.setHeight();
        rightChild.setHeight();

        return rightChild;
    }

}