学习《JavaScript 数据结构与算法》读书笔记

8 树

8.2 树的相关术语

一树结构包含一系列存在父子关系的节点，每个节点都有一个父节点（除了顶部的第一个节点）以及零个或多个子节点

位于树顶部的节点叫做根节点，它没有父节点。树中的每个元素都叫做节点，节点分为内部节点和外部节点。至少有一个子节点的节点称为内部节点。没有子元素的几点称为外部节点或叶节点。

一个节点可以有祖先和后代。一个节点（除了根节点）的祖先包括父节点、祖父节点、曾祖父节点等。一个节点的后代包括子节点、孙子节点、曾孙节点等。

子树由节点和它的后代构成。

节点的一个属性是深度，节点的深度取决于它的祖先节点的数量。

树的高度取决于所有节点深度的最大值。一棵树也可以被分解成层级。根节点在第0级，它的子节点在第1层，以此类推。

8.3 二叉树和二叉搜索树

二叉树中的节点最多只能有两个子节点：一个左侧子节点，另一个是右侧子节点。
二叉搜索树（BST）是二叉树的一种，但是它只允许在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大（或者等于）的值。

8.3.1 创建 BinarySearchTree 类

1
2
3
4
5
6
7
8
9
function BinarySearchTree() {
	var node = function(key) {
		this.key = key;
		this.left = null;
		this.right = null;
	};

	var root = null;
}

8.3.2 向树中插入一个键

1
2
3
4
5
6
7
8
this.insert = function(key) {
	var newNode = new Node(key);
	if (root === null) {
		root = newNode;
	} else {
		insertNode(root, newNode);
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var insertNode = function(node, newNode) {
	if (newNode.key < node.key) {
		if (node.left === null) {
			node.left = newNode;
		} else {
			insertNode(node.left, newNode);
		}
	} else {
		if (node.right === null) {
			node.right = newNode;
		} else {
			insertNode(node.right, newNode);
		}
	}
};

8.4 树的遍历

遍历一棵树是指访问树的每个节点并对它们进行某种操作的过程。

8.4.1 中序遍历

中序遍历是一种以上行顺序访问BST所有节点的遍历方式，也就是以从最小到最大的顺序访问所有节点。中序遍历的一种应用就是对数进行排序操作。

1
2
3
this.inOrderTraverse = function(callback) {
	inOrderTraverseNode(root, callback);
};

1
2
3
4
5
6
7
var inOrdertraverseNode = function(node, callback) {
	if (node !== null) {
		inOrderTraverseNode(node.left, callback);
		callback(node.key);
		inOrderTraverseNode(node.right, callback);
	}
};

8.4.2 先序遍历

先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。

1
2
3
this.preOrderTraverse = function(callback) {
	preOrderTraverseNode(root, callback);
};
1
2
3
4
5
6
7
var preOrderTraverseNode = function(node, callback) {
	if (node !== null) {
		callback(node.key);
		preOrderTraverseNode(node.left, callback);
		preOrderTraverseNode(node.right, callback);
	}
};

8.4.3 后序遍历

后序遍历则是先访问节点的后代节点，再访问节点本身，后序遍历的一种应用是计算一个目录和它的子目录中所有文件所占空间的大小

1
2
3
this.postOrderTraverse = function(callback) {
	postOrderTraverse(root, callback);
};
1
2
3
4
5
6
7
var postOrderTraverseNode = function(node, callback) {
	if (node !== null) {
		postOrderTraverseNode(node.left, callback);
		postOrderTraverseNode(node.right, callback);
		callback(node.key);
	}
}

8.5 搜索树中的值

8.5.1 搜索最小值和最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
this.min = function() {
	return minNode(root);
};

var minNode = function(node) {
	if (node) {
		while (node && node.left !== null) {
			node = node.left;
		}
		return node.key;
	}
	return null;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
this.max = function() {
	return maxNode(root);
};

var maxNode = function(node) {
	if (node) {
		while (node && node.right !== null) {
			node = node.right;
		}
		return node.key;
	}
	return null;
};

对于寻找最小值，总是沿着树的左边；而对于寻找最大值，总是沿着树的右边。

8.5.2 搜索一个特定的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
this.search = function(key) {
	return searchNode(root, key);
};

var searchNode = function(node, key) {
	if (node === null) {
		return false;
	}
	if (key < node.key) {
		return searchNode(node.left, key);
	} else if (key > node.key) {
		return searchNode(node.right, key);
	} else {
		return true;
	}
};

8.5.3 移除一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
this.remove = function(key) {
	root = removeNode(root, key);
};

var removeNode = function(node, key) {
	if (node === null) {
		return null;
	}
	if (key < node.key) {
		node.left = removeNode(node.left, key);
		return node;
	} else if (key > node.key) {
		node.right = removeNode(node.right, key);
		return node;
	} else { /* 键等于node.key */
		/* 第一种情况 一个叶节点 */
		if (node.left === null && node.right === null) {
			node = null;
			return node;
		}
		/* 第二种情况 只有一个子节点的节点 */
		if (node.left === null) {
			node = node.right;
			return node;
		} else if (node.right === null) {
			node = node.left;
			return node;
		}
		/* 第三种情况 一个有两个子节点的节点 */
		var aux = findMinNode(node.right);
		node.key = aux.key;
		node.right = removeNode(node.right, aux.key);
		return node;
	}
};

var findMinNode = function(node) {
	while (node && node.left !== null) {
		node = node.left;
	}
	return node;
}

8.6 自平衡树

BST存在一个问题：取决于你添加的节点数，树的一条边可能会非常深；也就是说，树的一条分支会有很多层，而其他的分支却只有几层。
这会在需要在某条边上添加、移除和搜索某个节点时引起的一些性能问题。为了解决这个问题，有一种树叫作 Adelson-Velskii-Landi 树（AVL树）。AVL树是一种自平衡二叉搜索树，意思是任何一个节点左右两侧子树的高度之差最多为1。也就是说这种书会在添加或移除节点时尽量试着成为一颗完全树。

8.6.1 Adelson-Velskii-Landi 树（AVL树）

1 在 AVL 树中插入节点

在 AVL 树中插入或移除节点和 BST 完全相同。然而， AVL 树的不同之处在于我们需要检验它的平衡因子，如果有需要，则将逻辑应用于树的自平衡。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var insertNode = function(node, element) {
	if (node === null) {
		node = new Node(element);
	} else if (element < node.key) {
		node.left = insertNode(node.left, element);

		if (node.left !== null) {
			/* 确认是否需要平衡 */
		}
	} else if (element > node.key) {
		node.right = insertNode(node.right, element);

		if (node.right !== null) {
			/* 确认是否需要平衡 */
		}
	}
	return node;
};

计算平衡因子

在 AVL 树中，需要对每个节点计算右子树高度（hr）和左子树高度（hl）的差值，该值（hr - hl） 应为0、1或-1。如果结果不是这三个值之一，则需要平衡该 AVL 树。

1
2
3
4
5
6
7
var heightNode = function(node) {
	if (node === null) {
		return -1;
	} else {
		return Math.max(heightNode(node.left), heightNode(node.right)) + 1;
	}
};

因此，在向左子树插入新节点时，需要计算其高度；如果高度大于1（即不为-1、0和1之一），就需要平衡左子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var insertNode = function(node, element) {
	if (node === null) {
		node = new Node(element);
	} else if (element < node.key) {
		node.left = insertNode(node.left, element);

		if (node.left !== null) {
			if ((heightNode(node.left) - heightNode(node.right)) > 1) {
				/* 旋转 */
			}

			if ((heightNode(node.right) - heightNode(node.left)) > 1) {
				/* 旋转 */
			}
		}
	}
};
AVL 旋转

向 AVL 树插入节点时，可以执行单旋转或双旋转两种平衡操作，分别对应四种场景。

右-右（RR）:向左的单旋转
1
2
3
4
5
6
var rotationRR = function(node) {
	var tmp = node.right;
	node.right = tmp.left;
	tmp.left = node;
	return tmp;
};
左-左（LL）:向右的单旋转
1
2
3
4
5
6
var rotationLL = function(node) {
	var tmp = node.left;
	node.left = tmp.right;
	tmp.right = node;
	return tmp;
};
左-右（LR）:向右的双旋转
1
2
3
4
var rotationLR = function(node) {
	node.left = rotationRR(node.left);
	return rotationLL(node);
};
右-左（RL）:向左的双旋转
1
2
3
4
var rotationRL = function(node) {
	node.right = rotationLL(node.right);
	return rotationRR(node);
};

2 完成 insertNode 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var insertNode = function(node, element) {
	if (node === null) {
		node = new Node(element);
	} else if (element < node.key) {
		node.left = insertNode(node.left, element);

		if (node.left !== null) {
			if ((heightNode(node.left) - heightNode(node.right)) > 1) {
				if (element < node.left.key) {
					node = rotationLL(node);
				} else {
					node = rotationLR(node);
				}
			}

			if ((heightNode(node.right) - heightNode(node.left)) > 1) {
				if (element > node.right.key) {
					node = rotationRR(node);
				} else {
					node = rotationRL(node);
				}
			}
		}
	}
};

8.6.2 更多关于二叉树的知识

红黑树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
function RedBlackTree() {
	var Colors = {
		RED: 0,
		BLACK: 1
	};

	var Node = function(key, color) {
		this.key = key;
		this.left = null;
		this.right = null;
		this.color = color;

		this.flipColor = function() {
			if (this.color === Colors.RED) {
				this.color = Colors.BLACK;
			} else {
				this.color = Colors.RED;
			}
		};
	};

	var root = null;

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

	var isRed = function(node) {
		if (!node) {
			return false;
		}
		return node.color === Color.RED;
	};

	var flipColors = function(node) {
		node.left.flipColor();
		node.right.flipColor();
	};

	var rotateLeft = function(node) {
		var temp = node.right;
		if (temp !== null) {
			node.right = temp.right;
			temp.left = node;
			temp.color = node.color;
			node.color = Colors.RED;
		}
		return temp;
	};

	var rotateRight = function(node) {
		var temp = node.left;
		if (temp !== null) {
			node.left = temp.right;
			temp.right = node;
			temp.color = node.color;
			node.color = Color.RED;
		}
		return temp;
	};

	var insertNode = function(node, element) {
		if (node === null) {
			return new Node(element, Color.RED);
		}

		var newRoot = node;

		if (element < node.key) {
			node.left = insertNode(node.left, element);
		} else if (element > node.key) {
			node.right = insertNode(node.right, element);
		} else {
			node.key = element;
		}

		if (isRed(node.right) && !isRed(node.left)) {
			newRoot = rotateLeft(node);
		}

		if (isRed(node.left) && isRed(node.left.left)) {
			newRoot = rotateRight(node);
		}

		if (isRed(node.left) && isRed(node.right)) {
			flipColors(node);
		}

		return newRoot;
	};

	this.insert = function(element) {
		root = insertNode(root, element);
		root.color = Colors.BLACK;
	};
}