AVL tree : javascript

AVLNode.js

/**
 * @author   redcrow
 * @link     http://na5cent.blogspot.com/2013/06/avl-tree-javascript.html
 * @create   25/06/2013
 */
var AVLNode = function(item) {
    var item_ = item || null;
    var left_ = null;
    var right_ = null;
    var height_ = 0;

    this.getItem = function() {
        return item_;
    };

    this.getLeft = function() {
        return left_;
    };

    this.setLeft = function(node) {
        left_ = node;
    };

    this.getRight = function() {
        return right_;
    };

    this.setRight = function(node) {
        right_ = node;
    };

    this.getHeight = function() {
        return height_;
    };

    this.size = function(node) {
        if (node === null) {
            return 0;
        } else {
            return size(node.getLeft()) + size(node.getRight()) + 1;
        }
    };

    this.preorderPrint = function(padding) {
        padding = padding || '';
        padding = '--' + padding;

        console.log(padding + item_);

        if (left_ !== null) {
            left_.preorderPrint(padding);
        }

        if (right_ !== null) {
            right_.preorderPrint(padding);
        }
    };

    this.inorderPrint = function(padding) {
        padding = padding || '';
        padding = '--' + padding;

        if (left_ !== null) {
            left_.inorderPrint(padding);
        }

        console.log(padding + item_);

        if (right_ !== null) {
            right_.inorderPrint(padding);
        }
    };

    this.postorderPrint = function(padding) {
        padding = padding || '';
        padding = '--' + padding;

        if (left_ !== null) {
            left_.postorderPrint(padding);
        }

        if (right_ !== null) {
            right_.postorderPrint(padding);
        }

        console.log(padding + item_);
    };
};

AVLTree.js

/**
 * @author   redcrow
 * @link     http://na5cent.blogspot.com/2013/06/avl-tree-javascript.html
 * @create   25/06/2013
 */
var AVLTree = function() {
    var root_ = null;
    var lastNode_;
    var deleteNode_;

    this.getRoot = function() {
        return root_;
    };


    var height_ = function(node) {
        if (node === null) {
            return -1;
        } else {
            return Math.max(height_(node.getLeft()), height_(node.getRight())) + 1;
        }
    };

    this.height = function(node) {
        return height_(node);
    };

    var singleRotateRight_ = function(node) {
        var tmp = node.getLeft();
        node.setLeft(tmp.getRight());
        tmp.setRight(node);

        return tmp;
    };

    var singleRotateLeft_ = function(node) {
        var tmp = node.getRight();
        node.setRight(tmp.getLeft());
        tmp.setLeft(node);

        return tmp;
    };

    var doubleRotateRight_ = function(node) {
        node.setLeft(singleRotateLeft_(node.getLeft()));
        return singleRotateRight_(node);
    };

    var doubleRotateLeft_ = function(node) {
        node.setRight(singleRotateRight_(node.getRight()));
        return singleRotateLeft_(node);
    };

    var insert_ = function(key, node) {
        if (node === null) {
            node = new AVLNode(key);
        } else if (key < node.getItem()) {
            node.setLeft(insert_(key, node.getLeft()));
            if (node.getLeft() !== null) {
                if ((height_(node.getLeft()) - height_(node.getRight())) === 2) {
                    if (key < node.getLeft().getItem()) {
                        node = singleRotateRight_(node);
                    } else {
                        node = doubleRotateRight_(node);
                    }
                }
            }
        } else if (key > node.getItem()) {
            node.setRight(insert_(key, node.getRight()));
            if (node.getRight() !== null) {
                if ((height_(node.getRight()) - height_(node.getLeft())) === 2) {
                    if (key > node.getRight().getItem()) {
                        node = singleRotateLeft_(node);
                    } else {
                        node = doubleRotateLeft_(node);
                    }
                }
            }
        } else {
            //duplicate not allow!
        }

        return node;
    };

    this.insertNode = function(key) {
        root_ = insert_(key, root_);
    };

    var delete_ = function(key, node) {
        if (node === null) {
            return null;
        }
        lastNode_ = node;

        if (key < node.getItem()) {
            node.setLeft(delete_(key, node.getLeft()));
        } else {
            deleteNode_ = node;
            node.setRight(delete_(key, node.getRight()));
        }

        if (node === lastNode_) {
            if (deleteNode_ !== null && key === deleteNode_.getItem()) {
                if (deleteNode_ === lastNode_) {
                    node = node.getLeft();
                } else {
                    var tmp = deleteNode_.getItem();
                    deleteNode_.setItem(lastNode_.getItem());
                    lastNode_.setItem(tmp);
                    node = node.getRight();
                }
            }
        } else {
            if ((height_(node.getLeft()) - height_(node.getRight())) === 2) {
                if (key < node.getLeft().getItem()) {
                    node = singleRotateRight_(node);
                } else {
                    node = doubleRotateRight_(node);
                }
            }

            if ((height_(node.getRight()) - height_(node.getLeft())) === 2) {
                if (key > node.getRight().getItem()) {
                    node = singleRotateLeft_(node);
                } else {
                    node = doubleRotateLeft_(node);
                }
            }
        }
    };

    this.deleteNode = function(key) {
        lastNode_ = null;
        deleteNode_ = null;
        root_ = delete_(key, root_);
    };

    this.findMinNode = function(node) {
        if (node !== null) {
            while (node.getLeft() !== null) {
                node = node.getLeft();
            }
        }

        return node;
    };

    this.findMaxNode = function(node) {
        if (node !== null) {
            while (node.getRight() !== null) {
                node = node.getRight();
            }
        }

        return node;
    };

    var removeMinNode_ = function(node) {
        if (node === null) {
            console.log('Error! tree is empty.');
            return null;
        } else if (node.getLeft() !== null) {
            node.setLeft(removeMinNode_(node.getLeft()));
            return node;
        } else {
            return node.getRight();
        }
    };

    var removeMaxNode_ = function(node) {
        if (node === null) {
            console.log('Error! tree is empty.');
            return null;
        } else if (node.getRight() !== null) {
            node.setRight(removeMaxNode_(node.getRight()));
            return node;
        } else {
            return node.getLeft();
        }
    };

    this.removeMinNode = function(node) {
        return removeMinNode_(node);
    };

    this.removeMaxNode = function(node) {
        return removeMaxNode_(node);
    };

    this.printAVLTree = function() {
        console.log('Items : ');
        root_.preorderPrint();
        console.log();
    };
};

Main.js

/**
 * @author   redcrow
 * @link     http://na5cent.blogspot.com/2013/06/avl-tree-javascript.html
 * @create   25/06/2013
 */
var tree = new AVLTree();
var data = [8, 12, 14, 18, 20, 21, 23, 33, 48, 50, 52, 60, 80, 100, 23, 50, 59, 50, 40, 30, 20, -2, 40, 30];

for (var i = 0; i < data.length; i++) {
    tree.insertNode(data[i]);
}
//tree.printAVLTree();
//console.log('root => ' + tree.getRoot().getItem());
var parent = document.getElementsByTagName('body')[0];

walkTree(tree.getRoot(), parent, 255);
//console.log('tree height => '+ tree.height(tree.getRoot()));


function walkTree(node, parent, color) {
    var element = document.createElement('div');
    element.setAttribute('style', 'background-color : rgb(' + color + ',' + color + ',' + color + ')');
    element.setAttribute('class', 'tree-node');

    var item = document.createElement('center');
    color = color - 10;

    if (node !== null) {
        item.innerHTML = node.getItem();
        element.appendChild(item);
        parent.appendChild(element);

        walkTree(node.getLeft(), element, color);
        walkTree(node.getRight(), element, color);
    } else {
        item.innerHTML = 'null';
        element.appendChild(item);
        parent.appendChild(element);
    }
}

UI.css

.tree-node{
    border : solid 1px #ccc;
    float: left;
    margin: 5px;
    border-radius: 20px;    
    padding : 5px;
}

.tree-node center{
    font-weight : bold;
    padding-top : 5px;
}