用JavaScript实现二叉搜索树[每日前端夜话0xA8]
source link: https://www.tuicool.com/articles/7ZraM3r
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
每日前端夜话 0xA8
每日前端夜话，陪你聊前端。
每天晚上18:00准时推送。
正文共：3742 字
预计阅读时间：12 分钟
作者：Nicholas C. Zakas
翻译：疯狂的技术宅
来源： humanwhocodes
计算机科学中最常用和讨论最多的数据结构之一是二叉搜索树。这通常是引入的第一个具有非线性插入算法的数据结构。二叉搜索树类似于双链表，每个节点包含一些数据，以及两个指向其他节点的指针；它们在这些节点彼此相关联的方式上有所不同。二叉搜索树节点的指针通常被称为“左”和“右”，用来指示与当前值相关的子树。这种节点的简单 JavaScript 实现如下：
1var node = {
2 value: 125,
3 left: null,
4 right: null
5};
从名称中可以看出，二叉搜索树被组织成分层的树状结构。 第一个项目成为根节点，每个附加值作为该根的祖先添加到树中。 但是，二叉搜索树节点上的值是唯一的，根据它们包含的值进行排序： 作为节点左子树的值总是小于节点的值，右子树中的值都是大于节点的值。 通过这种方式，在二叉搜索树中查找值变得非常简单，只要你要查找的值小于正在处理的节点则向左，如果值更大，则向右移动。 二叉搜索树中不能有重复项，因为重复会破坏这种关系。 下图表示一个简单的二叉搜索树。
上图表示一个二叉搜索树，其根的值为 8。当添加值 3 时，它成为根的左子节点，因为 3 小于 8。当添加值 1 时，它成为 3 的左子节点，因为 1 小于 8（所以向左）然后 1 小于3（再向左）。当添加值 10 时，它成为跟的右子节点，因为 10 大于 8。不断用此过程继续处理值 6，4，7，14 和 13。此二叉搜索树的深度为 3，表示距离根最远的节点是三个节点。
二叉搜索树以自然排序的顺序结束，因此可用于快速查找数据，因为你可以立即消除每个步骤的可能性。通过限制需要查找的节点数量，可以更快地进行搜索。假设你要在上面的树中找到值 6。从根开始，确定 6 小于 8，因此前往根的左子节点。由于 6 大于 3，因此你将前往右侧节点。你就能找到正确的值。所以你只需访问三个而不是九个节点来查找这个值。
要在 JavaScript 中实现二叉搜索树，第一步要先定义基本接口：
1function BinarySearchTree() {
2 this._root = null;
3}
4
5BinarySearchTree.prototype = {
6
7 //restore constructor
8 constructor: BinarySearchTree,
9
10 add: function (value){
11 },
12
13 contains: function(value){
14 },
15
16 remove: function(value){
17 },
18
19 size: function(){
20 },
21
22 toArray: function(){
23 },
24
25 toString: function(){
26 }
27
28};
基本接与其他数据结构类似，有添加和删除值的方法。我还添加了一些方便的方法， size() ， toArray() 和 toString() ，它们对 JavaScript 很有用。
要掌握使用二叉搜索树的方法，最好从 contains() 方法开始。 contains() 方法接受一个值作为参数，如果值存在于树中则返回 true ，否则返回 false 。此方法遵循基本的二叉搜索算法来确定该值是否存在：
1BinarySearchTree.prototype = {
2
3 //more code
4
5 contains: function(value){
6 var found = false,
7 current = this._root
8
9 //make sure there's a node to search
10 while(!found && current){
11
12 //if the value is less than the current node's, go left
13 if (value < current.value){
14 current = current.left;
15
16 //if the value is greater than the current node's, go right
17 } else if (value > current.value){
18 current = current.right;
19
20 //values are equal, found it!
21 } else {
22 found = true;
23 }
24 }
25
26 //only proceed if the node was found
27 return found;
28 },
29
30 //more code
31
32};
搜索从树的根开始。如果没有添加数据，则可能没有根，所以必须要进行检查。遍历树遵循前面讨论的简单算法：如果要查找的值小于当前节点则向左移动，如果值更大则向右移动。每次都会覆盖 current 指针，直到找到要找的值（在这种情况下 found 设置为 true ）或者在那个方向上没有更多的节点了（在这种情况下，值不在树上）。
在 contains() 中使用的方法也可用于在树中插入新值。主要区别在于你要寻找放置新值的位置，而不是在树中查找值：
1BinarySearchTree.prototype = {
2
3 //more code
4
5 add: function(value){
6 //create a new item object, place data in
7 var node = {
8 value: value,
9 left: null,
10 right: null
11 },
12
13 //used to traverse the structure
14 current;
15
16 //special case: no items in the tree yet
17 if (this._root === null){
18 this._root = node;
19 } else {
20 current = this._root;
21
22 while(true){
23
24 //if the new value is less than this node's value, go left
25 if (value < current.value){
26
27 //if there's no left, then the new node belongs there
28 if (current.left === null){
29 current.left = node;
30 break;
31 } else {
32 current = current.left;
33 }
34
35 //if the new value is greater than this node's value, go right
36 } else if (value > current.value){
37
38 //if there's no right, then the new node belongs there
39 if (current.right === null){
40 current.right = node;
41 break;
42 } else {
43 current = current.right;
44 }
45
46 //if the new value is equal to the current one, just ignore
47 } else {
48 break;
49 }
50 }
51 }
52 },
53
54 //more code
55
56};
在二叉搜索树中添加值时，特殊情况是在没有根的情况。在这种情况下，只需将根设置为新值即可轻松完成工作。对于其他情况，基本算法与 contains() 中使用的基本算法完全相同：新值小于当前节点向左，如果值更大则向右。主要区别在于，当你无法继续前进时，这就是新值的位置。所以如果你需要向左移动但没有左侧节点，则新值将成为左侧节点（与右侧节点相同）。由于不存在重复项，因此如果找到具有相同值的节点，则操作将停止。
在继续讨论 size() 方法之前，我想深入讨论树遍历。为了计算二叉搜索树的大小，必须要访问树中的每个节点。二叉搜索树通常会有不同类型的遍历方法，最常用的是有序遍历。通过处理左子树，然后是节点本身，然后是右子树，在每个节点上执行有序遍历。由于二叉搜索树以这种方式排序，从左到右，结果是节点以正确的排序顺序处理。对于 size() 方法，节点遍历的顺序实际上并不重要，但它对 toArray() 方法很重要。由于两种方法都需要执行遍历，我决定添加一个可以通用的 traverse() 方法：
1BinarySearchTree.prototype = {
2
3 //more code
4
5 traverse: function(process){
6
7 //helper function
8 function inOrder(node){
9 if (node){
10
11 //traverse the left subtree
12 if (node.left !== null){
13 inOrder(node.left);
14 }
15
16 //call the process method on this node
17 process.call(this, node);
18
19 //traverse the right subtree
20 if (node.right !== null){
21 inOrder(node.right);
22 }
23 }
24 }
25
26 //start with the root
27 inOrder(this._root);
28 },
29
30 //more code
31
32};
此方法接受一个参数 process ，这是一个应该在树中的每个节点上运行的函数。该方法定义了一个名为 inOrder() 的辅助函数用于递归遍历树。注意，如果当前节点存在，则递归仅左右移动（以避免多次处理 null ）。然后 traverse() 方法从根节点开始按顺序遍历， process() 函数处理每个节点。然后可以使用此方法实现 size() 、 toArray() 、 toString() ：
1BinarySearchTree.prototype = {
2
3 //more code
4
5 size: function(){
6 var length = 0;
7
8 this.traverse(function(node){
9 length++;
10 });
11
12 return length;
13 },
14
15 toArray: function(){
16 var result = [];
17
18 this.traverse(function(node){
19 result.push(node.value);
20 });
21
22 return result;
23 },
24
25 toString: function(){
26 return this.toArray().toString();
27 },
28
29 //more code
30
31};
size() 和 toArray() 都调用 traverse() 方法并传入一个函数来在每个节点上运行。在使用 size() 的情况下，函数只是递增长度变量，而 toArray() 使用函数将节点的值添加到数组中。 toString() 方法在调用 toArray() 之前把返回的数组转换为字符串，并返回 。
删除节点时，你需要确定它是否为根节点。根节点的处理方式与其他节点类似，但明显的例外是根节点需要在结尾处设置为不同的值。为简单起见，这将被视为 JavaScript 代码中的一个特例。
删除节点的第一步是确定节点是否存在：
1BinarySearchTree.prototype = {
2
3 //more code here
4
5 remove: function(value){
6
7 var found = false,
8 parent = null,
9 current = this._root,
10 childCount,
11 replacement,
12 replacementParent;
13
14 //make sure there's a node to search
15 while(!found && current){
16
17 //if the value is less than the current node's, go left
18 if (value < current.value){
19 parent = current;
20 current = current.left;
21
22 //if the value is greater than the current node's, go right
23 } else if (value > current.value){
24 parent = current;
25 current = current.right;
26
27 //values are equal, found it!
28 } else {
29 found = true;
30 }
31 }
32
33 //only proceed if the node was found
34 if (found){
35 //continue
36 }
37
38 },
39 //more code here
40
41};
remove() 方法的第一部分是用二叉搜索定位要被删除的节点，如果值小于当前节点的话则向左移动，如果值大于当前节点则向右移动。当遍历时还会跟踪 parent 节点，因为你最终需要从其父节点中删除该节点。当 found 等于 true 时， current 的值是要删除的节点。
删除节点时需要注意三个条件：
-
叶子节点
-
只有一个孩子的节点
-
有两个孩子的节点
从二叉搜索树中删除除了叶节点之外的内容意味着必须移动值来对树正确的排序。前两个实现起来相对简单，只删除了一个叶子节点，删除了一个带有一个子节点的节点并用其子节点替换。最后一种情况有点复杂，以便稍后访问。
在了解如何删除节点之前，你需要知道节点上究竟存在多少个子节点。一旦知道了，你必须确定节点是否为根节点，留下一个相当简单的决策树：
1BinarySearchTree.prototype = {
2
3 //more code here
4
5 remove: function(value){
6
7 var found = false,
8 parent = null,
9 current = this._root,
10 childCount,
11 replacement,
12 replacementParent;
13
14 //find the node (removed for space)
15
16 //only proceed if the node was found
17 if (found){
18
19 //figure out how many children
20 childCount = (current.left !== null ? 1 : 0) +
21 (current.right !== null ? 1 : 0);
22
23 //special case: the value is at the root
24 if (current === this._root){
25 switch(childCount){
26
27 //no children, just erase the root
28 case 0:
29 this._root = null;
30 break;
31
32 //one child, use one as the root
33 case 1:
34 this._root = (current.right === null ?
35 current.left : current.right);
36 break;
37
38 //two children, little work to do
39 case 2:
40
41 //TODO
42
43 //no default
44
45 }
46
47 //non-root values
48 } else {
49
50 switch (childCount){
51
52 //no children, just remove it from the parent
53 case 0:
54 //if the current value is less than its
55 //parent's, null out the left pointer
56 if (current.value < parent.value){
57 parent.left = null;
58
59 //if the current value is greater than its
60 //parent's, null out the right pointer
61 } else {
62 parent.right = null;
63 }
64 break;
65
66 //one child, just reassign to parent
67 case 1:
68 //if the current value is less than its
69 //parent's, reset the left pointer
70 if (current.value < parent.value){
71 parent.left = (current.left === null ?
72 current.right : current.left);
73
74 //if the current value is greater than its
75 //parent's, reset the right pointer
76 } else {
77 parent.right = (current.left === null ?
78 current.right : current.left);
79 }
80 break;
81
82 //two children, a bit more complicated
83 case 2:
84
85 //TODO
86
87 //no default
88
89 }
90
91 }
92
93 }
94
95 },
96
97 //more code here
98
99};
处理根节点时，这是一个覆盖它的简单过程。对于非根节点，必须根据要删除的节点的值设置 parent 上的相应指针：如果删除的值小于父节点，则 left 指针必须重置为 null （对于没有子节点的节点）或删除节点的 left 指针；如果删除的值大于父级，则必须将 right 指针重置为 null 或删除的节点的 right 指针。
如前所述，删除具有两个子节点的节点是最复杂的操作。考虑二元搜索树的以下表示。
根为 8，左子为 3，如果 3 被删除会发生什么？有两种可能性：1（3 左边的孩子，称为有序前身）或4（右子树的最左边的孩子，称为有序继承者）都可以取代 3。
这两个选项中的任何一个都是合适的。要查找有序前驱，即删除值之前的值，请检查要删除的节点的左子树，并选择最右侧的子节点；找到有序后继，在删除值后立即出现的值，反转进程并检查最左侧的右子树。其中每个都需要另一次遍历树来完成操作：
1BinarySearchTree.prototype = {
2
3 //more code here
4
5 remove: function(value){
6
7 var found = false,
8 parent = null,
9 current = this._root,
10 childCount,
11 replacement,
12 replacementParent;
13
14 //find the node (removed for space)
15
16 //only proceed if the node was found
17 if (found){
18
19 //figure out how many children
20 childCount = (current.left !== null ? 1 : 0) +
21 (current.right !== null ? 1 : 0);
22
23 //special case: the value is at the root
24 if (current === this._root){
25 switch(childCount){
26
27 //other cases removed to save space
28
29 //two children, little work to do
30 case 2:
31
32 //new root will be the old root's left child
33 //...maybe
34 replacement = this._root.left;
35
36 //find the right-most leaf node to be
37 //the real new root
38 while (replacement.right !== null){
39 replacementParent = replacement;
40 replacement = replacement.right;
41 }
42
43 //it's not the first node on the left
44 if (replacementParent !== null){
45
46 //remove the new root from it's
47 //previous position
48 replacementParent.right = replacement.left;
49
50 //give the new root all of the old
51 //root's children
52 replacement.right = this._root.right;
53 replacement.left = this._root.left;
54 } else {
55
56 //just assign the children
57 replacement.right = this._root.right;
58 }
59
60 //officially assign new root
61 this._root = replacement;
62
63 //no default
64
65 }
66
67 //non-root values
68 } else {
69
70 switch (childCount){
71
72 //other cases removed to save space
73
74 //two children, a bit more complicated
75 case 2:
76
77 //reset pointers for new traversal
78 replacement = current.left;
79 replacementParent = current;
80
81 //find the right-most node
82 while(replacement.right !== null){
83 replacementParent = replacement;
84 replacement = replacement.right;
85 }
86
87 replacementParent.right = replacement.left;
88
89 //assign children to the replacement
90 replacement.right = current.right;
91 replacement.left = current.left;
92
93 //place the replacement in the right spot
94 if (current.value < parent.value){
95 parent.left = replacement;
96 } else {
97 parent.right = replacement;
98 }
99
100 //no default
101
102 }
103
104 }
105
106 }
107
108 },
109
110 //more code here
111
112};
具有两个子节点的根节点和非根节点的代码几乎相同。此实现始终通过查看左子树并查找最右侧子节点来查找有序前驱。遍历是使用 while 循环中的 replacement 和 replacementParent 变量完成的。 replacement 中的节点最终成为替换 current 的节点，因此通过将其父级的 right 指针设置为替换的 left 指针，将其从当前位置移除。对于根节点，当 replacement 是根节点的直接子节点时， replacementParent 将为 null ，因此 replacement 的 right 指针只是设置为 root 的 right 指针。最后一步是将替换节点分配到正确的位置。对于根节点，替换设置为新根；对于非根节点，替换被分配到原始 parent 上的适当位置。
关于此实现的说明：始终用有序前驱替换节点可能导致不平衡树，其中大多数值会位于树的一侧。不平衡树意味着搜索效率较低，因此在实际场景中应该引起关注。在二叉搜索树实现中，要确定是用有序前驱还是有序后继以使树保持适当平衡（通常称为自平衡二叉搜索树）。
这个二叉搜索树实现的完整源代码可以在我的GitHub 中【 http://github.com/nzakas/computer-science-in-javascript/ 】中找到。对于替代实现，你还可以查看 Isaac Schlueter 的 GitHub fork【 http://github.com/isaacs/computer-science-in-javascript 】。
原文： https://humanwhocodes.com/blog/2009/06/09/computer-science-in-javascript-binary-search-tree-part-1/
下面夹杂一些私货：也许你和高薪之间只差这一张图
2019年京程一灯课程体系上新，这是我们第一次将全部课程列表对外开放。
愿你有个好前程，愿你月薪30K。我们是认真的 ！ 
在公众号内回复“体系”查看高清大图
长按二维码，加大鹏老师微信好友
拉你加入前端技术交流群
唠一唠怎样才能拿高薪
往期精选
小手一抖，资料全有。长按二维码关注 前端先锋 ，阅读更多技术文章和业界动态。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK