AVL Tree in JavaScript

avltree.js

/*jslint browser: true, regexp: true, nomen: true */

(function (win) {
	'use strict';
	var AvlTreeNode,
	    AvlTree,
	    events = {};
	
	function max(a, b) {
		a = a || 0;
		b = b || 0;
		return a > b ? a : b;
	}

	function height(node) {
		return max((node.left && node.left.height), (node.right && node.right.height));
	}

	AvlTreeNode = (function () {
		function AvlTreeNode(data) {
			this.left = null;
			this.right = null;
			this.height = 0;
			
			this.__defineGetter__('bf', function () {
				return (this.left ? this.left.height : -1) - (this.right ? this.right.height : -1);
			});

			var i;
			for (i in data) {
				if (data.hasOwnProperty(i) && !this.hasOwnProperty(i)) {
					this[i] = data[i];
				}
			}

		}
		return AvlTreeNode;
	}());

	AvlTree = (function () {
		function AvlTree(root, compare) {
			if (!AvlTree.isNode(root)) {
				root = new AvlTreeNode();
			}
			if (compare && typeof compare !== 'function') {
				throw new Error('AvlTree 第二個參數請給一個比較 Node 用的 funciton。');
			}

			function fire(name) {
				if (events[name]) {
					events[name].forEach(function (val, i) {
						val(this);
					});
				}
			}

			this.on = function (name, cb) {
				if (!name || !cb) {
					return this;
				}
				if (events[name]) {
					events[name].push(cb);
				} else {
					events[name] = [cb];
				}
				return this;
			};

			this.off = function (name, cb) {
				if (!name || !cb) {
					return this;
				}
				if (events[name]) {
					var length = events[name].length,
					    i,
					    tmp;
					for (i = 0; i < length; i += 1) {
						if (events[name] === cb) {
							tmp = events[name].slice(0, i);
							events = tmp.concat(events[name].slice(i + 1));
							break;
						}
					}
				}
				return this;
			};

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

			this.insert = function (node) {
				var tmp;

				if (!AvlTree.isNode(node)) {
					return false;
				}

				(function _insert(gNode, pNode) {
					if (compare(pNode, node)) {
						if (pNode.left) {
							_insert(pNode, pNode.left);
							if (pNode.bf > 1) {
								if (compare(pNode.left, node)) {
									// LL 旋轉
									tmp = pNode.left;
									pNode.left = tmp.right;
									tmp.right = pNode;
									pNode = tmp;
								} else {
									// LR 旋轉
									tmp = pNode.left.right;
									pNode.left.right = tmp.left;
									tmp.left = pNode.left;
									pNode.left = tmp.right;
									tmp.right = pNode;
									pNode = tmp;
								}
								pNode.right.height = height(pNode.right) + 1;
								pNode.left.height = height(pNode.left) + 1;
								// 將原本指向原始根節點的變數指向旋轉後的跟節點
								if (root === pNode.right) {
									root = pNode;
								} else {
									if (gNode.left === pNode.right) {
										gNode.left = pNode;
									} else {
										gNode.right = pNode;
									}
								}
							}
						} else {
							pNode.left = node;
						}
					} else {
						if (pNode.right) {
							_insert(pNode, pNode.right);
							if (pNode.bf < -1) {
								if (compare(pNode.right, node)) {
									// RL 旋轉
									tmp = pNode.right.left;
									pNode.right.left = tmp.right;
									tmp.right = pNode.right;
									pNode.right = tmp.left;
									tmp.left = pNode;
									pNode = tmp;
								} else {
									// RR 旋轉
									tmp = pNode.right;
									pNode.right = tmp.left;
									tmp.left = pNode;
									pNode = tmp;
								}
								pNode.left.height = height(pNode.left) + 1;
								pNode.right.height = height(pNode.right) + 1;
								// 將原本指向原始根節點的變數指向旋轉後的跟節點
								if (root === pNode.left) {
									root = pNode;
								} else {
									if (gNode.left === pNode.left) {
										gNode.left = pNode;
									} else {
										gNode.right = pNode;
									}
								}
							}
						} else {
							pNode.right = node;
						}
					}

					pNode.height = height(pNode) + 1;
				}(root, root));

				fire('insert');
			};
		}

		AvlTree.isNode = function (node) {
			return (node && node.constructor && node.constructor.name === AvlTreeNode.name) ? true : false;
		};

		return AvlTree;
	}());

	win.AvlTree = AvlTree;
	win.AvlTreeNode = AvlTreeNode;
}(this));