Hi guys,

I'm working on my homework: I have to use a data structure to store words read from input file, i chose AVL tree to be the data structure, i implemented the tree and tested it with hard coded words, it works fine. However, with words read from input file the problem is each time a word is added to the AVL tree it will be the main root and it keeps showing the hight is 0, also when removing some times it shows NullPointerException.

Here is what i've done so far:

public AVLNode search(String key)
   {
      // Tree is empty
      if (root == null)
      {
            return null;
        }

      // Tree is not empty
      AVLNode p = root;
      try
      {while (true)
      {
            if(p == null && p.getData().equals(key))
            {
                break;
            }
            else if (key.compareTo(p.getData()) < 0)
            {
                p = p.getLeftChild();
            }
            else
            {
                p = p.getRightChild();
            }
      }
      }

      catch(NullPointerException e)
      {
          System.out.println(e);
      }
      return p;
   }

    // INSERT A NODE INTO AVL TRRE
    public void insert(String data) 
    {
        // Case: tree is empty  <------------------------------
        if (root == null)
        {
            root = new AVLNode(data);
            return;
        }

        // Case: tree is not empty
        AVLNode p = root;

        // move p down as far as we can
        while(true)
        {
            if (data.equals(p.getData()) && p.getLeftChild() != null)
            {
                p = p.getLeftChild();
            }

            else if(data.compareTo(p.getData()) < 0 && p.getLeftChild() != null)
            {
                p = p.getLeftChild();
            }
            else if (data.compareTo(p.getData()) > 0 && p.getRightChild() != null)
            {
                p = p.getRightChild();
            }
            else
            {
                break;
            }
        }

        // insert new node to the tree as a child of node p

        AVLNode newNode= new AVLNode(data);

        if(data.equals(p.getData()))
        {
            p.setLeftChild(newNode);
        }

        else if (data.compareTo(p.getData()) < 0)
        {
            p.setLeftChild(newNode);
        }
        else
        {
            p.setRightChild(newNode);
        }

        rebalanceInsertionPath(newNode);
    }

I think the problem is where I put the arrow ( <---------------)

The tests i've done:

 AVLTree tree = new AVLTree();

      tree.insert("university");

      tree.insert("holiday");
      tree.insert("lecture");
      tree.insert("library");
      tree.insert("building");
      tree.insert("new");
      tree.insert("old");

      //tree.displayElements();
      //tree.displayStructure();

      System.out.println( "=== Remove (This shows NullPointerException ====");
      tree.remove("old");   // Requires rotations 
      tree.search("university");
      tree.displayElements();
      tree.displayStructure();

Any ideas why each time the words are added to the main root and the tree doesn't keep adding the nodes?

It works fine with the tests i've done but when reading a file:

System.out.println("Please enter file name to open: \n");

                // Name of first file 
                String firstFileName;

                // Initialising fileName to read first file
                firstFileName = input.nextLine();

                // variable to hold the one line data
                //String line = null;                                                      

                File file = new File(firstFileName);
                Scanner inFile = new Scanner(file).useDelimiter(("\\s+(\\W*\\s)?"));

                // While the file has more words to read, keep reading
                while(inFile.hasNext()) 
                {


                    // Keep reading next word of the file
                    String word = inFile.next();
                    AVLTree tree = new AVLTree();
                   tree.insert(word);
                    tree.displayStructure();

Here where the problem occurs.

By the way: the tree was converted from implementing integers to implementing strings (which what i want it to do).

I really appreciate your help mate :D
Hope if any problems come up, someone also will be able to help after i try till i give up :D

What about the NullPointerException? it still appears even though i catch it.

NPE mans you have an unitialised variable (it's still null). Catching it doesn't help, you have to find why it's happening and fix it.
The exception message tells you the exact line where the NPE happens. Look on that line to see what variables are being used.

I'm trying to read a file into the tree, this what it shows:

- - - ROOT: zoo., height: 0
- - - LEFT
- - - - null
- - - RIGHT
- - - - null
java.lang.NullPointerException
java.lang.NullPointerException
ROOT: can, height: 3
LEFT
- ROOT: and, height: 2
- LEFT
- - ROOT: You, height: 1
- - LEFT

So it doesn't tell the line, it used to tell the line i added the try catch block, now it's not showing the line where the NPE is happening.

Edited 2 Years Ago by mark_jason

That's because you carefully told Java not to tell you the line. In your catch block replace
System.out.println(e); // just prints the type of error
with
e.printStackTrace();; // prints everything about the error

Replaced all of them and still this what i get:

>> right rotate at: is
java.lang.NullPointerException
java.lang.NullPointerException
>> right rotate at: is

sure, here you go:

public AVLNode search(String key)
   {
      // Tree is empty
      if (root == null)
      {
            return null;
        }

      // Tree is not empty
      AVLNode p = root;
      try
      {while (true)
      {
            if(p == null && p.getData().equals(key))
            {
                break;
            }
            else if (key.compareTo(p.getData()) < 0)
            {
                p = p.getLeftChild();
            }
            else
            {
                p = p.getRightChild();
            }
      }
      }

      catch(NullPointerException e)
      {
          e.printStackTrace();
      }
      return p;
   }

    // INSERT A NODE INTO AVL TRRE
    public void insert(String data)
    {
        try
        {
        // Case: tree is empty
        if (root == null)
        {
            root = new AVLNode(data);
            return;
        }

        // Case: tree is not empty
        AVLNode p = root;

        // move p down as far as we can
        while(true)
        {
            if (data.equals(p.getData()) && p.getLeftChild() != null)
            {
                p = p.getLeftChild();
            }

            else if(data.compareTo(p.getData()) < 0 && p.getLeftChild() != null)
            {
                p = p.getLeftChild();
            }
            else if (data.compareTo(p.getData()) > 0 && p.getRightChild() != null)
            {
                p = p.getRightChild();
            }
            else
            {
                break;
            }
        }

        // insert new node to the tree as a child of node p

        AVLNode newNode= new AVLNode(data);

        if(data.equals(p.getData()))
        {
            p.setLeftChild(newNode);
        }

        else if (data.compareTo(p.getData()) < 0)
        {
            p.setLeftChild(newNode);
        }
        else
        {
            p.setRightChild(newNode);
        }

        rebalanceInsertionPath(newNode);
        }

        catch(NullPointerException n)
        {
            n.printStackTrace();
        }
    }

There's nothing in that code I can see that would just print "java.lang.NullPointerException". That suggests it's in one of your other methods

in my assignment i'm just reading words from input file and store them in the tree using the insert method.
It surprices me that the NPE occurs only with some files and only with some words to insert in the tree.

Sounds like either:
there's some odd formatting in some of the files that's messing up your parsing
or:
it's to do with the sort order in which the words appear - leading to a particular sequence of left/right additions

Once you get the full stack trace for your NPE you will know which line is the problem, and the cause will be easy to find. Until then we're just guessing in the dark.

From what I read, I believe the problem lies inside your rebalancing the tree. Show us how you implement it.

Suggestion [strongly]:
You could merge the if in Line 52 and else if in line 57 because you are doing the same thing - if (data.compareTo(p.getData())<=0 && p.getLeftChild()!=null). Better yet, you could simply add the node right inside the statement rather than wait and do it again outside. Then you could eliminate lines 71~87.

while(true) {
  if (data.compareTo(p.getData())<=0) {  // left child
    if (p.getLeftChild()!=null) { p = p.getLeftChild(); }
    else {
      p.setLeftChild(new AVLNode(data));
      break;
    }
  }
  else {  // right child
    if (p.getRightChild()!=null) { p = p.getRightChild(); }
    else {
      p.setRightChild(new AVLNode(data));
      break;
    }
  }  // end either left or right child
}  // end while

My next suggestion because I have a question is that why AVLNode class has root variable? Shouldn't it contain value, leftChild, and rightChild? If the value is null, then the node is empty. It is redundant and confusing to have root variable because it is self reference. In other words, the node itself can be identified as either root or child. As a result, you would rewrite your constructor to accept the incoming value and assign to the value instead of to root.

//Class variable
String data = null;
AVLNode leftChild = null;
AVLNode rightChild = null;

//Constructor
public AVLNode() { }  // or you could omit this one
public AVLNode(String data) {
  if (data==null) {
    throw new IllegalArgumentException("Incoming data cannot be null!");
  }
  value = data;
}

//Lines 4~7 in search(String)
if (value==null || key==null) { return null; }

// Lines 40~44 in insert(String)
if (data==null) { return; }  // not accept null string
if (value==null) {
  value = data;
  return;
}

Are you sure?
Because i tested it on a small file and it seems working correct:

This is the file (some words) i tested it on:

he-llo the're" how, are. you?

The output:

hello.txt
Now adding:  hello
ROOT: hello, height: 0
LEFT
- null
RIGHT
- null
Now adding:  there
ROOT: hello, height: 1
LEFT
- null
RIGHT
- ROOT: there, height: 0
- LEFT
- - null
- RIGHT
- - null
Now adding:  how
>> right-left rotate at: hello
>> right rotate at: there
>> left rotate at: hello
ROOT: how, height: 1
LEFT
- ROOT: hello, height: 0
- LEFT
- - null
- RIGHT
- - null
RIGHT
- ROOT: there, height: 0
- LEFT
- - null
- RIGHT
- - null
Now adding:  are
ROOT: how, height: 2
LEFT
- ROOT: hello, height: 1
- LEFT
- - ROOT: are, height: 0
- - LEFT
- - - null
- - RIGHT
- - - null
- RIGHT
- - null
RIGHT
- ROOT: there, height: 0
- LEFT
- - null
- RIGHT
- - null
Now adding:  you
ROOT: how, height: 2
LEFT
- ROOT: hello, height: 1
- LEFT
- - ROOT: are, height: 0
- - LEFT
- - - null
- - RIGHT
- - - null
- RIGHT
- - null
RIGHT
- ROOT: there, height: 1
- LEFT
- - null
- RIGHT
- - ROOT: you, height: 0
- - LEFT
- - - null
- - RIGHT
- - - null

If you think this is very small file to test on, i agree but because i'm using Putty (which i'm familiar with) so when i test on large file i cann't scrol up much to copy paste or see all the result from the begining,the NullPointerException is gone now (by itself), i didn't change anything but now i'm having a problem when i test on larger files (like an ebook, which i'm supposed to do, to test the program on larger files), the problem is:

CPU time limit exceeded (core dumped)

Any idea how to keep reading without having the cpu limit problem?

Maybe because i'm using ArayList to store the nodes when re-balancing, i'm thinking of a faster collection to store the nodes in.

I found that when i add a duplicate word to the small text file i'm testing on (I'm supposed not to insert only one word of the duplicate words in the AVL tree) then the NPE occurs, testing on the same small file, it shows:

Please enter file name to open:

hello.txt
Now adding:  hello
ROOT: hello, height: 0
LEFT
- null
RIGHT
- null
Now adding:  Hello
ROOT: hello, height: 1
LEFT
- ROOT: Hello, height: 0
- LEFT
- - null
- RIGHT
- - null
RIGHT
- null
Now adding:  there
ROOT: hello, height: 1
LEFT
- ROOT: Hello, height: 0
- LEFT
- - null
- RIGHT
- - null
RIGHT
- ROOT: there, height: 0
- LEFT
- - null
- RIGHT
- - null
Now adding:  how
ROOT: hello, height: 2
LEFT
- ROOT: Hello, height: 0
- LEFT
- - null
- RIGHT
- - null
RIGHT
- ROOT: there, height: 1
- LEFT
- - ROOT: how, height: 0
- - LEFT
- - - null
- - RIGHT
- - - null
- RIGHT
- - null
Now adding:  how
java.lang.NullPointerException
        at AVLTree.setHeight(AVLTree.java:292)
        at AVLTree.rebalanceInsertionPath(AVLTree.java:157)
        at AVLTree.insert(AVLTree.java:136)
        at WordMatch.menu(WordMatch.java:105)
        at WordMatch.main(WordMatch.java:20)
java.lang.NullPointerException
        at AVLTree.getHeightDifference(AVLTree.java:234)
        at AVLTree.rebalance(AVLTree.java:201)
        at AVLTree.rebalanceInsertionPath(AVLTree.java:179)
        at AVLTree.insert(AVLTree.java:136)
        at WordMatch.menu(WordMatch.java:105)
        at WordMatch.main(WordMatch.java:20)
>> right rotate at: there
ROOT: hello, height: 3
LEFT
- ROOT: Hello, height: 0
- LEFT
- - null
- RIGHT
- - null
RIGHT
- ROOT: how, height: 1
- LEFT
- - ROOT: how, height: 0
- - LEFT
- - - null
- - RIGHT
- - - null
- RIGHT
- - ROOT: there, height: 0
- - LEFT
- - - null
- - RIGHT
- - - null
Now adding:  are
ROOT: hello, height: 2
LEFT
- ROOT: Hello, height: 1
- LEFT
- - null
- RIGHT
- - ROOT: are, height: 0
- - LEFT
- - - null
- - RIGHT
- - - null
RIGHT
- ROOT: how, height: 1
- LEFT
- - ROOT: how, height: 0
- - LEFT
- - - null
- - RIGHT
- - - null
- RIGHT
- - ROOT: there, height: 0
- - LEFT
- - - null
- - RIGHT
- - - null
Now adding:  you
ROOT: hello, height: 3
LEFT
- ROOT: Hello, height: 1
- LEFT
- - null
- RIGHT
- - ROOT: are, height: 0
- - LEFT
- - - null
- - RIGHT
- - - null
RIGHT
- ROOT: how, height: 2
- LEFT
- - ROOT: how, height: 0
- - LEFT
- - - null
- - RIGHT
- - - null
- RIGHT
- - ROOT: there, height: 1
- - LEFT
- - - null
- - RIGHT
- - - ROOT: you, height: 0
- - - LEFT
- - - - null
- - - RIGHT
- - - - null

The rebalnce implementation:

private void rebalanceInsertionPath(AVLNode node)
    {
        // Get the path nodes from the root to the node
        ArrayList<AVLNode> nodes = getAllNodesOnPath(node.getData());

        // Reverse the list to get the path from the node to the root
        Collections.reverse(nodes);


        // Set the heights of the nodes along the path
        for(int i = 0; i < nodes.size(); i++)
        {
            setHeight(nodes.get(i));
        }

        // Rebalance all the nodes (subtrees) on path from inserted node
        // to the root
        for(int i = 1; i < nodes.size(); i++)
        {
            AVLNode pp = nodes.get(i);
            AVLNode pc = nodes.get(i-1);
            try
            {
                if (pp.getLeftChild() != null && pp.getLeftChild().equals(pc))
                {
                    AVLNode localRoot = rebalance(pc);
                    pp.setLeftChild(localRoot);
                    if(! (localRoot.equals(pc)))// some rotation has actually been made
                    {
                        break;
                    }
                }
                else
                {
                    AVLNode localRoot = rebalance(pc);
                    pp.setRightChild(localRoot);
                    if(!( localRoot.equals(pc)))    // some rotation has actually been made
                    {
                        break;
                    }
                }
            }

            catch(NullPointerException n)
            {
                n.printStackTrace();
            }
        }

        // .. This is done outside the loop because root does not
        // .. have a parent
        root = rebalance(root);
    }

   private AVLNode rebalance(AVLNode node)
   {
      int diff = getHeightDifference(node);

      if(diff == 2)
      {

              if(getHeightDifference(node.getLeftChild()) == -1)
              {
                 node = leftRightRotation(node);
              }

             else
             {
                 node = rightRotation(node);
             }

      }
      else if(diff == -2)
      {
         if(getHeightDifference(node.getRightChild()) == 1)
         {
            node = rightLeftRotation(node);
         }
         else
         {
            node = leftRotation(node);
         }
      }

      return node;
   }

And because i'm not removing the duplicated words, this what makes the program takes more time to read, insert and print the words into the tree and then in larger files the CPU limit problem occurs.

Hmm...

1)You should not play with duplicated value when you have not correctly completed the implementation. The duplicated value would be an extra step and you will have to make many changes to handle the case. For now, deal with unique values first.

2)How do you compute height? A new node which is not null should have height at least 1. The null node would return height 0. You start the insertion from the hello.txt file but it shows that your first node (root) has height of 0 which is already strange. That's why you have -1 of height involve (which is not confusing and may cause problem).

3)In your small test, you only test right-left rotation and only one time. Therefore, it may not trigger the bug in your code.

4)In your rebalance checking, I thought the algorithm compares the left-right height value AND the value of the current data with the imbalance node value (2 height above the current insertion)? In yours, you are comparing height twice. This site shows how to do the insertion. The example on the page is written in C though. But it is still useful and would be easy for you to port to Java if you know C enough.

5)If you look at the page I gave you, they set the node height immediately after the insertion. It is safer because you will have to climb up the tree to rebalancing after you done rotation. If you separate the height adjustment (rebalanceInsertionPath()), you could get into trouble when you attempt to deal with many nodes. Besides, you could get your height messed up easily.

6)ArrayList shouldn't affect your memory usage that much. I think it is from your implementation that requires the program to unnecessary revisit the same node and loops many times. Though, you don't need to optimize it right now. Just need to make it correct first.

Edited 2 Years Ago by Taywin

I changed the code to what you suggested and got the result i posted in the earlier post.

About changing the AVLNode class, i'm just wondering where did you get the value variable from because in the constructor you initialised data to null, and value is not declared, is value a parameter same as data?

The problem is: the original implementation was AVL tree for integers and i changed it to store strings.

Hmm... Yes, value is the same as data. You need to prevent null value to be created as a node except the root. A tree is a collection of nodes. The control of root could be done in insert() if you want. That's why you need to check for null value at any time you are about to change the data value because null value should not be allowed inside the tree. So an example of creating and using the class is as follows:

class AVLNode {
  String data=null;
  AVLNode leftChild=null;
  AVLNode rightChild=null;

  public AVLNode(String v) {
    if (v==null) {
      throw new IllegalArgumentException('Data cannot be null');
    }
    data = v;
  }

  public String getData() { return data; }
  public void insert(String v) {
    if (v==null) { return; }
    if (data==null) {  // root
      data = v;
      return;
    }
    // do the insertion
    ...
  }
  public void setLeftChild(AVLNode node) {
    ...
  }
  public void setRightChild(AVLNode node) {
    ...
  }
  ...
  ...

  @Override
  public String toString() {
    if (data==null) { return "Empty tree"; }
    ...
  }
}

class TestAVLNode {
  public static void main(String[] args) {
    AVLNode tree = new AVLNode();


    ...
    // first insert, the tree becomes the root node
    tree.insert("blahblah");
    // second insert, the tree has right child
    tree.insert("nono");
    ...
  }
}

So the data it gets is still the same (from data). Yes, the value stored in a node can be any type. You could even have multiple data stored in the node and it can still be indexed as an AVL tree. The only different between an integer and String is the data value comparison (int type uses >,>=,<,<= but String uses compareTo()). The v1.compareTo(v2)>=0 is the same as v1>=v2 in int, and v1.compareTo(v2)<=0 is the same as v1<=v2. That's why you do not need to use equals() at all.

The insert() function on the site, which is written in C, returns node pointer that's because you need to manage the pointer and it is the way you could do in C. Unlike the funcion, in your case in Java, you do not need to do that but rather manage it inside your AVLNode class. Other functions are similar as well (return node pointer but you may ignore).

Edited 2 Years Ago by Taywin

Great, thanks alot, now the null pointer exception is fixed, i'm having issues with the correct place to insert and counting height, should i post my implementation so you can have a look to see why it shows wrong height and inserting?

import java.util.*;
import java.util.*;
import java.util.regex.Pattern;

public class AVLTree {
    private AVLNode root;
    private List<String> matchedList;

    public AVLTree() {
        root = null;
        matchedList  = new ArrayList<String>();
    }

    // DISPLAY ELEMENTS BY INORDER TRAVERSAL (as for binary trees)
    public void displayElements() {
        System.out.println("=== Inorder traversal ===");
        displaySubtreeInOrder(root);
        System.out.println("===");
    }

    private void displaySubtreeInOrder(AVLNode localRoot) {
        if (localRoot != null) {
            displaySubtreeInOrder(localRoot.getLeftChild());
            System.out.println("data: " + localRoot.getData());
            displaySubtreeInOrder(localRoot.getRightChild());
        }
    }

    // DISPLAY TREE STRUCTURE (as for binary tree)
    public void displayStructure() {
        if (root == null) {
            System.out.println("null");
        } else {
            root.display(0); // this display method is defined in AVLNode
        }
    }

    // SEARCH (as for binary search trees)
    public AVLNode search(String key) {
        // Tree is empty
        if (root == null) {
            return null;
        }

        // Tree is not empty
        AVLNode p = root;
        try {
            while (true) {
                if (p == null && p.getData().equals(key)) {
                    break;
                } else if (key.compareTo(p.getData()) < 0) {
                    p = p.getLeftChild();
                } else {
                    p = p.getRightChild();
                }
            }
        }

        catch (NullPointerException e) {
            e.printStackTrace();
        }
        return p;
    }

    // INSERT A NODE INTO AVL TRRE
    public void insert(String data) {
        try {
            // Case: tree is empty
            if (this.root == null) {
                root = new AVLNode(data);
                return;
            }

            // Case: tree is not empty
            AVLNode p = root;
            AVLNode newNode = new AVLNode(data);

            // move p down as far as we can
            while (true) {
                // This commented new
                /*
                 * if (data.equals(p.getData()) && p.getLeftChild() != null) { p
                 * = p.getLeftChild(); }
                 * 
                 * else if(data.compareTo(p.getData()) < 0 && p.getLeftChild()
                 * != null) { p = p.getLeftChild(); } else if
                 * (data.compareTo(p.getData()) > 0 && p.getRightChild() !=
                 * null) { p = p.getRightChild(); } else { break; }
                 */

                // This created new ****************

                if (data.compareTo(p.getData()) <= 0) { // left child
                    if (p.getLeftChild() != null) {
                        p = p.getLeftChild();
                    } else {
                        p.setLeftChild(newNode);
                        break;
                    }
                }

                else if (data.compareTo(p.getData()) > 0) {
                    if (p.getRightChild() != null) {
                        p = p.getRightChild();
                    }

                    else {
                        p.setRightChild(newNode);
                        break;
                    }
                }

            }

            // insert new node to the tree as a child of node p

            // This commented new *****************************
            // AVLNode newNode= new AVLNode(data);

            /*
             * if(data.equals(p.getData())) { p.setLeftChild(newNode);
             * 
             * }
             * 
             * else if (data.compareTo(p.getData()) < 0) {
             * p.setLeftChild(newNode); } else { p.setRightChild(newNode); }
             * Commented new till here ************
             */

            rebalanceInsertionPath(newNode);
        }

        catch (NullPointerException n) {
            n.printStackTrace();
        }
    }

    private void rebalanceInsertionPath(AVLNode node) {
        // Get the path nodes from the root to the node
        ArrayList<AVLNode> nodes = getAllNodesOnPath(node.getData());

        // Reverse the list to get the path from the node to the root
        Collections.reverse(nodes);

        // Set the heights of the nodes along the path
        for (int i = 0; i < nodes.size(); i++) {
            setHeight(nodes.get(i));
        }

        // Rebalance all the nodes (subtrees) on path from inserted node
        // to the root
        for (int i = 1; i < nodes.size(); i++) {
            AVLNode pp = nodes.get(i);
            AVLNode pc = nodes.get(i - 1);
            try {
                if (pp.getLeftChild() != null && pp.getLeftChild().equals(pc)) {
                    AVLNode localRoot = rebalance(pc);
                    pp.setLeftChild(localRoot);
                    if (!(localRoot.equals(pc)))// some rotation has actually
                                                // been made
                    {
                        break;
                    }
                } else {
                    AVLNode localRoot = rebalance(pc);

                    if (localRoot == null)
                    {
                        break;
                    }

                    pp.setRightChild(localRoot);
                    if (!(localRoot.equals(pc))) // some rotation has actually
                                                    // been made
                    {
                        break;
                    }
                }
            }

            catch (NullPointerException n) {
                n.printStackTrace();
            }
        }

        // .. This is done outside the loop because root does not
        // .. have a parent
        root = rebalance(root);
    }

    private AVLNode rebalance(AVLNode node) {
        int diff = getHeightDifference(node);

        if (diff == 2) {

            if (getHeightDifference(node.getLeftChild()) == -1) {
                node = leftRightRotation(node);
            }

            else {
                node = rightRotation(node);
            }

        } else if (diff == -2) {
            if (getHeightDifference(node.getRightChild()) == 1) {
                node = rightLeftRotation(node);
            } else {
                node = leftRotation(node);
            }
        }

        return node;
    }

    private int getHeightDifference(AVLNode node) {

        if (node == null)
        {
            return 0;
        }

        AVLNode leftChild = node.getLeftChild();
        AVLNode rightChild = node.getRightChild();
        int leftHeight = leftChild == null ? -1 : leftChild.getHeight();
        int rightHeight = rightChild == null ? -1 : rightChild.getHeight();

        return leftHeight - rightHeight;
    }

    private AVLNode rightRotation(AVLNode g) {
        // Message to let know about the rotation
        System.out.println(">> right rotate at: " + g.getData());

        AVLNode p = g.getLeftChild();
        AVLNode x = p.getRightChild(); // x is right child of p
        p.setRightChild(g);
        g.setLeftChild(x);
        setHeight(g);
        setHeight(p);
        return p;
    }

    private AVLNode leftRotation(AVLNode g) {
        System.out.println(">> left rotate at: " + g.getData());

        AVLNode p = g.getRightChild();
        AVLNode x = p.getLeftChild(); // x is left child of p
        p.setLeftChild(g);
        g.setRightChild(x);
        setHeight(g);
        setHeight(p);
        return p;
    }

    private AVLNode rightLeftRotation(AVLNode g) {
        System.out.println(">> right-left rotate at: " + g.getData());

        AVLNode p = g.getRightChild();
        g.setRightChild(rightRotation(p));
        return leftRotation(g);
    }

    private AVLNode leftRightRotation(AVLNode g) {
        System.out.println(">> left-right rotate at: " + g.getData());

        AVLNode p = g.getLeftChild();
        g.setLeftChild(leftRotation(p));
        return rightRotation(g);
    }

    private void setHeight(AVLNode node) {
        try {
            // This if statement added new ********
            if (node != null && node.getLeftChild() != null) {
                AVLNode leftChild = node.getLeftChild();
                AVLNode rightChild = node.getRightChild();
                int leftHeight = leftChild == null ? -1 : leftChild.getHeight();
                int rightHeight = rightChild == null ? -1 : rightChild
                        .getHeight();

                if (leftHeight >= rightHeight) {
                    node.setHeight(leftHeight + 1);
                } else {
                    node.setHeight(rightHeight + 1);
                }
            }

        } catch (NullPointerException e) {
            e.printStackTrace();
        }
    }

    // REMOVE NODE FROM AVL TREE
    public boolean remove(String key) {
        // Find the node to be deleted
        AVLNode deleted = root;
        AVLNode parent = null;
        try {
            while (true) {
                if (deleted != null && key.equals(deleted.getData())) {
                    break;
                }

                else if (key.compareTo(deleted.getData()) < 0) {
                    parent = deleted;
                    deleted = deleted.getLeftChild();
                } else if (key.compareTo(deleted.getData()) > 0) {
                    parent = deleted;
                    deleted = deleted.getRightChild();
                }
            }
        }

        catch (NullPointerException e) {
            e.printStackTrace();
        }

        if (deleted == null) // The node is not found
        {
            return false;
        } else if (deleted.getLeftChild() == null
                && deleted.getRightChild() == null) {
            deleteLeafNode(deleted, parent);
            return true;
        } else if ((deleted.getLeftChild() != null && deleted.getRightChild() == null)
                || (deleted.getLeftChild() == null && deleted.getRightChild() != null)) {
            deleteNodeWithOneChild(deleted, parent);
            return true;
        } else {
            deleteNodeWith2Children(deleted, parent);
            return true;
        }
    }

    private void deleteLeafNode(AVLNode deleted, AVLNode parent) {
        if (deleted == root) {
            root = null;
        } else if (parent.getLeftChild() == deleted) {
            parent.setLeftChild(null);
            rebalanceDeletionPath(parent);
        } else {
            parent.setRightChild(null);
            rebalanceDeletionPath(parent);
        }
    }

    private void deleteNodeWithOneChild(AVLNode deleted, AVLNode parent) {
        // Get the child of the deleted node
        AVLNode child = null;
        if (deleted.getLeftChild() != null) {
            child = deleted.getLeftChild();
        } else {
            child = deleted.getRightChild();
        }

        // Let root or parent of deleted node point to the child
        if (deleted == root) {
            root = child;
        } else if (deleted == parent.getLeftChild()) {
            parent.setLeftChild(child);
            rebalanceDeletionPath(parent);
        } else {
            parent.setRightChild(child);
            rebalanceDeletionPath(parent);
        }
    }

    private void deleteNodeWith2Children(AVLNode deleted, AVLNode parent) {
        AVLNode largest = deleted.getLeftChild(); // find largest in left
                                                    // subtree
        AVLNode parentOfLargest = deleted;
        while (largest.getRightChild() != null) {
            parentOfLargest = largest;
            largest = largest.getRightChild();
        }

        deleted.setData(largest.getData()); // copy largests data to
                                            // "deleted node"

        if (largest.getLeftChild() == null) // delete largest
        {
            deleteLeafNode(largest, parentOfLargest);
        } else {
            deleteNodeWithOneChild(largest, parentOfLargest);
        }
    }

    private void rebalanceDeletionPath(AVLNode parent) {

        // Get the path nodes from the root to the parent
        ArrayList<AVLNode> nodes = getAllNodesOnPath(parent.getData());

        // Reverse the list to get the path from parent to root
        Collections.reverse(nodes);

        // Set the heighs of the nodes along the path
        for (int i = 0; i < nodes.size(); i++) {
            setHeight(nodes.get(i));
        }

        // Rebalance the nodes along the path
        for (int i = 1; i < nodes.size(); i++) {
            try {
                AVLNode pp = nodes.get(i);
                AVLNode pc = nodes.get(i - 1);

                if (pp.getRightChild().equals(pc)) {
                    pp.setRightChild(rebalance(pc));
                } else {
                    pp.setLeftChild(rebalance(pc));
                }
            }

            catch (NullPointerException e) {
                e.printStackTrace();
            }
        }

        // .. This is done outside the loop because root does not
        // .. have a parent
        root = rebalance(root);
    }

    public ArrayList<AVLNode> getAllNodesOnPath(String key)
    // The tree is not empty and the key is in the tree

    {
        ArrayList<AVLNode> nodes = new ArrayList<AVLNode>();

        // Add root as the first node
        // Otherwise, it will not be included
        // Modified on 28/03/2012
        nodes.add(root);

        AVLNode p = root;
        while (p != null && p.getData() != key) {
            if (key.compareTo(p.getData()) < 0) {
                p = p.getLeftChild();
            } else {
                p = p.getRightChild();
            }
            nodes.add(p);
        }

        return nodes;
    }
    // Newly Created Methods
    public void searchPattern(AVLNode localRoot,Pattern p) {
        if (localRoot != null) {

            searchPattern(localRoot.getLeftChild(),p);          
            if(p.matcher(localRoot.getData()).matches())
                matchedList.add(localRoot.getData());
//          System.out.println("data: " + localRoot.getData());  // 
            searchPattern(localRoot.getRightChild(),p);
        }
    }
    public List<String> getMatchedLexicons()
    {
        return this.matchedList;
    }

    public AVLNode getRoot() {
        // TODO Auto-generated method stub
        return this.root;
    }
    public void reSetMatchedLexiconsList()
    {
        this.matchedList.clear();
    }
}

I don't have much time here so I am going to give you some idea why it does not work.

Apparently, the site I gave you implements the AVL tree in recursive fashion. Yours is an iterative fashion. As a result, your porting code contains incorrect logic. There are at least 3 parts of your iterative fashion that do not follow the recursive one.

The first, in your rebalanceInsertPath(), you update all nodes' height before you go into the loop to check and do some rotation. In the recursive version, it adjust each node height before it is being checked for rotation.

The second, you adjust the AVLNode height in your AVLTree which is incorrect. The method should be inside AVLNode class itself. Furthermore, the adjust height is recursive. In other words, it will adjust all nodes in the node's subtree going up until the node itself.

Last, your comparing height when the node is null is inconsistent. You need to decide which one you are going for. In your current code, you return -1 for null child node, but you return 0 when the current calling node is null. This could cause problems later on.

That's just my quick note for you. I have a few more nit-picking but don't have much time to explain. Anyway, I can tell you that you do not need to try/catch for NPE if you implement the class correctly. Also, relying on catching the NPE in this type of project is very bad because you should handle/prevent incoming null value instead of allowing it and let try/catch do the work...

After I tried your code using recursive (instead of iterative), it has no problem. However, one thing I have to let you know because it is my fault not to take a close look, is that the site I gave you implemented wrongely set the node height inside rotation function. It should be recursive or the node height is being set wrong. To do it recursively, I have to implement the recursive inside AVLNode class.

// in AVLTree class
// your left rotation code (copy & paste)
private AVLNode leftRotation2(AVLNode g) {
  System.out.println(">> left rotate at: " + g.getData());

  AVLNode p = g.getRightChild();
  AVLNode x = p.getLeftChild(); // x is left child of p
  p.setLeftChild(g);
  g.setRightChild(x);

  // all its children height will be updated as well
  // this includes 'g' node
  p.setHeightRecursive();
//  setHeight(g);  // no need
//  setHeight(p);  // no need
  return p;
}

// in AVLNode class
public int setHeightRecursive() {
  // if this.left is not null, set the node height
  // using returned value of its setHeightRecursive()

  // if this.rightt is not null, set the node height
  // using returned value of its setHeightRecursive()

  // set this.height to max(left, right)+1

  // return this.height
}

// no change
public void setHeight(int h) { height = h; }

Below is what I tested with (even with equal node values).

public static void main(String[] args) {
  AVLTree tree = new AVLTree();
  System.out.println("Inserting: hello");
  tree.insert("hello");
  System.out.println("Inserting: there");
  tree.insert("there");
  System.out.println("Inserting: do");
  tree.insert("do");
  System.out.println("Inserting: you");
  tree.insert("you");
  System.out.println("Inserting: want");
  tree.insert("want");
  System.out.println("Inserting: to");
  tree.insert("to");
  System.out.println("Inserting: know");
  tree.insert("know");
  System.out.println("Inserting: me");
  tree.insert("me");
  System.out.println("Inserting: ?");
  tree.insert("?");
  System.out.println("Inserting: ?");
  tree.insert("?");
  System.out.println("Inserting: to");
  tree.insert("to");
  System.out.println("  ----------Final----------");
  System.out.println(tree);
/*
      ----------Final----------
    V:there | L:hello | R:want | H:4
     V:hello | L:? | R:know | H:3
     V:want | L:to | R:you | H:3
      V:? | L:? | R:do | H:2
      V:know | L:null | R:me | H:2
      V:to | L:null | R:to | H:2
       V:you | L:null | R:null | H:1
       V:? | L:null | R:null | H:1
       V:do | L:null | R:null | H:1
       V:me | L:null | R:null | H:1
       V:to | L:null | R:null | H:1
*/
}

Thanks for that but i tried to go to the website you mentioned the link is not clickable.

This article has been dead for over six months. Start a new discussion instead.