BST数，AVL树，红黑树

定义树的节点：

Node = function(data) {	var R = 15;		this.x;	this.y;		this.data = data;	this.parent = null;	this.left = null;	this.right = null;	this.color = "lightblue";		this.getR = function() {		return R;	}		this.setLeft = function(left) {		this.left = left;		if (left != null)			this.left.parent = this;	}		this.setRight = function(right) {		this.right = right;		if (right != null)			this.right.parent = this;	}		this.isLeft = function() {		if (this.parent == null) return null;		return this.parent.left == this;	}		this.isRight = function() {		if (this.parent == null) return null;		return this.parent.right == this;	}		this.toString = function() {		return data;	}		// for avl	this.getLeftAndRightLevel = function() {		var left = 0;		var right = 0;				if (this.left != null) {			left = this.left.getMaxLevel() - this.getLevel();		}		if (this.right != null) {			right = this.right.getMaxLevel() - this.getLevel();		}			return {left: left, right: right} ;			}			this.getLevel = function() {		return (this.parent == null ? 1 : this.parent.getLevel() + 1);	}			this.getMaxLevel = function() {		var stack = new Array();		stack.push(this);		var max = 0;		while (stack.length > 0) {			var d = stack.pop();						var l = d.getLevel();			if (l > max && d.left == null && d.right == null) {				max = l;			}						if (d.left != null) stack.push(d.left);			if (d.right != null) stack.push(d.right);		}				return max;	}}
初始化一些测试数据
	var n = new Array();			this.init = function() {		var m = Math.round(Math.random() * 30);				for (var i=0; i<m; i++) {			var k =  Math.round(Math.random() * 1000);			if (n.indexOf(k) == -1) {				n.push(k);			}		}	}
显示树
		var canvas = document.getElementById(canvasid);				var a = new Array();		var stack = new Array();		stack.push(this.root);				while (stack.length > 0) {			var n = stack.shift();			a.push(n);			if (n != null) {				var h = n.getLevel();				var w = this.getLeftNumber(n);								var x = w * 30 - n.getR() /2;				var y = h * 30 - n.getR() /2;								n.x = x;				n.y = y;								if (n.left != null) stack.push(n.left);				if (n.right != null) stack.push(n.right);							}		}				for (var i=0; i<a.length; i++) {			var n = a[i];						if (n.parent != null) {				var l = drawLine(n.x, n.y, n.parent.x, n.parent.y);				canvas.appendChild(l);			}		}		for (var i=0; i<a.length; i++) {			var n = a[i];			var c = drawCircle(n.x, n.y, n);			canvas.appendChild(c);						var t = drawText(n.x, n.y, n);			canvas.appendChild(t);		}	}
定义画布
	<div style="height:300px;overflow:auto">		<svg id="c" width="100%"  version="1.1" xmlns="http://www.w3.org/2000/svg" />	</div>	<div  style="height:300px;overflow:auto">		<svg id="d" width="100%" version="1.1" xmlns="http://www.w3.org/2000/svg" />	</div>	<div  style="height:300px;overflow:auto">		<svg id="e" width="100%" version="1.1" xmlns="http://www.w3.org/2000/svg" />	</div>
打印遍历树
	this.disparray = function() {		var r = new Array();		var stack = new Array();				var p = this.root;				while (p!= null || stack.length != 0) {			while (p != null ) {				stack.push(p);				p = p.left;			}						p = stack.pop();			r.push(p);			p = p.right;		}		console.log(r.join(",") );	}
执行
	t = new Tree();	t.init();		t.BST();	t.disp("c");	t.disparray();	t.AVL();	t.disp("d");	t.disparray();	t.RBT();	t.disp("e");	t.disparray();二叉查找树
	this.BST = function() {		// clear		this.root = null;		cachenodes = null;		for (var i=0; i<n.length; i++) {			var m = n[i];						var p = this.root;			var parent = null;			var left = true;			while (p != null) {				parent = p;				if (m < p.data) {					p = p.left;					left = true;				}				else if (m>p.data) {					p = p.right;					left = false;				}			}						if (parent == null) {				this.root = new Node(m);			}			else {				p = new Node(m);				if (left) parent.setLeft(p);				else parent.setRight(p);			}		}	}
二叉平衡树
	function ll(node) {		var parent = node.parent;		var left = node.isLeft() ;				var p = node.left;		node.setLeft(node.left.right);		p.setRight(node);				if (left != null) {			if (left)  parent.setLeft(p); else parent.setRight(p);		}		else p.parent = null;		return p;	}		function rr(node) {		var parent = node.parent;		var left = node.isLeft() ;		var p = node.right;		node.setRight(node.right.left);		p.setLeft(node);				if (left != null) {			if (left)  parent.setLeft(p); else parent.setRight(p);		}		else p.parent = null;		return p;	}		function lr(node) {		var parent = node.parent;		var left = node.isLeft() ;		var p = rr(node.left);		p = ll(node);				if (left != null) {			if (left)  parent.setLeft(p); else parent.setRight(p);		}		else p.parent = null;		return p;	}		function rl(node) {		var parent = node.parent;		var left = node.isLeft() ;		var p = ll(node.right);		p = rr(node);		if (left != null) {			if (left)  parent.setLeft(p); else parent.setRight(p);		}		else p.parent = null;		return p;	}		this.AVL = function() {		this.root = null;		cachenodes = null;		for (var i=0; i<n.length; i++) {			var m = n[i];						var p = this.root;			var parent = null;			var path = new Array();						while (p != null ) {				path.push(p);				parent = p;								if (m < p.data) {					p = p.left;				}				else if (m>p.data) {					p = p.right;				}			}						if (parent == null) {				this.root = new Node(m);				continue ;			}			p = new Node(m);			if (m < parent.data) parent.setLeft(p);	else parent.setRight(p);			// 			while (path.length > 0) {				p = path.pop();								var l = p.getLeftAndRightLevel();				if (l.left - l.right > 1) { // ll or lr 					if (p.left.left != null) p = ll(p);	else  if (p.left.right != null) p = lr(p);				}				else if (l.right - l.left > 1 ) { // rr or rl					if (p.right.right != null) p = rr(p); else if (p.right.left != null) p = rl(p);				}				if (path.length == 0) this.root = p;			}		}	}
红黑树
	function lll(node) {		var parent = node.parent;		var left = node.isLeft() ;		var p = node.right;		node.setRight(p.left);		p.setLeft(node);		if (left != null) {			if (left)  parent.setLeft(p); else parent.setRight(p);		}		else p.parent = null;		return p;	}		function rrr(node) {		var parent = node.parent;		var left = node.isLeft() ;		var p = node.left;		node.setLeft(p.right);		p.setRight(node);		if (left != null) {			if (left)  parent.setLeft(p); else parent.setRight(p);		}		else p.parent = null;		return p;	}		this.RBT = function() {		this.root = null;		cachenodes = null;		for (var i=0; i<n.length; i++) {			var m = n[i];						if (this.root == null) {				this.root = new Node(m);				this.root.color = "grey";				continue ;			}						var p = this.root;			var parent = null;						while (p != null ) {				parent = p;								if (m < p.data) {					p = p.left;				}				else if (m>p.data) {					p = p.right;				}			}						p = new Node(m);			p.color = "red";			if (m < parent.data) parent.setLeft(p); else parent.setRight(p);						// set color			while (parent != null && parent.color == "red") {				if (parent.isLeft() == true) {					var fb = parent.parent.right;					if (fb != null && fb.color == "red") {						fb.color = "grey";						parent.color = "grey";						p.parent.parent.color = "red";						p = p.parent.parent;					}					else {						if (p.isRight() == true) {							p = p.parent;							var t = lll(p);							if (t.parent == null) this.root = t;						}						p.parent.color = "grey";						if (p.parent.parent != null) p.parent.parent.color = "red";						var t = rrr(p.parent.parent);						if (t.parent == null) this.root = t;					}				}				if (parent.isRight() == true) {					var fb = parent.parent.left;					if (fb != null && fb.color == "red") {											fb.color = "grey";						parent.color = "grey";						p.parent.parent.color = "red";						p = p.parent.parent;					}					else {						if (p.isLeft() == true) {							p = p.parent;							var t = rrr(p);							if (t.parent == null) this.root = t;						}						p.parent.color = "grey";						if (p.parent.parent != null) p.parent.parent.color = "red";						var t = lll(p.parent.parent);						if (t.parent == null) this.root = t;					}				}				parent = p.parent;			}						this.root.color = "grey";		}	}
显示图，第一个是二叉查找数， 第二个是二叉平衡数，第三个是红黑树
F5