Root node is null after inserting new node into AVLTree

Question

So in simpletons, I am creating my own AVLTree data structure. Now when i add a new node into my tree, it seems to add fine.

EDIT: It doesnt seem to take into account my duplicates (nor add them to the original node's list by key).

But when i print the rootNode to see if it exists it doesn't exist. I can't figure out what the problem is with my add method.

Here is my AVLTree class:

package cw.util;

import java.util.ArrayList;
import java.util.Comparator;

public class AVLTree<K, V>
{
    public class Node {
        private K key;
        private ArrayList<V> valuesList;
        private Node left, right;
        private int height;

        public Node(K key, ArrayList<V> valuesList) {
            this.key = key;
            this.valuesList = valuesList;
            this.height = 0;
        }

        public Node(V value) {
        }

        public void addToNode(V value) {
            valuesList.add(value);
        }

        public K getKey() {
            return key;
        }

        public ArrayList<V> getValues() {
            return valuesList;
        }

        public Node getLeftChild() {
            return left;
        }
        public Node getRightChild() {
            return right;
        }

        public int getHeight() {
            return height;
        }

        public Node getChildNodeFromSide(String side) {
            switch(side) {
                default: return null;
                case "left": return left;
                case "right": return right;
            }
        }
    }

    private Node rootNode;
    private Comparator<K> comparator;

    //Unused
    public AVLTree() {
    }

    public AVLTree(Comparator<K> comparator) {
        this.comparator = comparator;
        this.rootNode = null;
    }

    public V insert(K key, V value) {
        Node n = insert(key, value, rootNode);

        if(n != null) {
            for(V v : n.getValues())
                System.out.println(v.toString());
            System.out.println();
            return value;
        } else {
            return null;
        }
    }

    public Node insert(K key, V value, Node node) {
        ArrayList<V> values = new ArrayList<V>();
        values.add(value);

        if(node == null)
            node = new Node(key, values);
        else if(comparator.compare(key, node.key) < 0) {
            node.left = insert(key, value, node.left);

            if(height(node.left) - height(node.right) == 2) {
                if(comparator.compare(key, node.left.key) < 0)
                    node = rotateWithLeftChild(node);
                else
                    node = doubleRotateWithLeft(node);
            }

        } else if(comparator.compare(key, node.key) > 0) {
            node.right = insert(key, value, node.right);

            if(height(node.right) - height(node.left) == 2) {
                if(comparator.compare(key, node.right.key) > 0)
                    node = rotateWithRightChild(node);
                else
                    node = doubleRotateWithRight(node);
            }
        } else node.getValues().add(value);

        node.height = Math.max(height(node.left), height(node.right)) + 1;

        return node;
    }

    public Node search(K key) {
        return search(key, rootNode);
    }

    public Node search(K key, Node node) {
        boolean isFound = false;

        while((node != null) && !isFound) {
            K nodeKey = node.getKey();
            if(comparator.compare(key, nodeKey) < 0)
                node = node.getLeftChild();
            else if(comparator.compare(key, nodeKey) > 0)
                node = node.getRightChild();
            else {
                isFound = true;
            }
            node = search(key, node);
        }
        if(isFound) return node;
        else return null;
    }

    //Custom Methods
    public boolean isEmpty() {
        return rootNode == null;
    }
    private int height(Node n) {
        return n == null ? -1 : n.getHeight();
    }

    private Node rotateWithLeftChild(Node node2) {
        Node node1 = node2.left;
        node2.left = node1.right;
        node1.right = node2;

        node2.height = Math.max(height(node2.left), height(node2.right)) + 1;
        node1.height = Math.max(height(node1.left), node2.getHeight()) + 1;

        return node1;
    }
    private Node rotateWithRightChild(Node node1) {
        Node node2 = node1.right;
        node1.right = node2.left;
        node2.left = node1;

        node1.height = Math.max(height(node1.left), height(node1.right)) + 1;
        node2.height = Math.max(height(node2.left), node1.getHeight()) + 1;

        return node2;
    }
    private Node doubleRotateWithLeft(Node node) {
        node.left = rotateWithRightChild(node.left);
        return rotateWithLeftChild(node);
    }
    private Node doubleRotateWithRight(Node node) {
        node.right = rotateWithLeftChild(node.right);
        return rotateWithRightChild(node);
    }
}

Here is how I test the class:

package cw.avl;

import cw.util.AVLTree;

public class AVLTest
{
    public static void main(String[] args) {
        AVLTree<String, Integer> tree = new AVLTree<String, Integer>(String.CASE_INSENSITIVE_ORDER);

        for (int i=1; i <= 10;i++) {
            String s = "S" + i;
            int x = i;
            tree.insert(s, x);
            tree.insert(s, x);
        }
    }
}

Answer 1

Well, you don't seem to ever assign to rootNode, so it starts null and remains so. In fact, your methods create nodes and return them:

if(node == null) node = new Node(key, values); ... return node

But you don't use the returned node.

Edit: longer explanation:

When you call from the other function like this: Node n = insert(key, value, rootNode); you are basically saying: Node n = insert(key, value, null);. On the receiving end, here:

public Node insert(K key, V value, Node node) { ,

you are creating a new variable called node with initial value null. Then you replace that value when you do:

node = new Node(key, values);

That value is for the node variable in the insert(K,V,N) method, in no way is rootNode retroactively updated. You could just do so right there:

if(node == null) { node = new Node(key, values); rootNode = node; }