Binary-Search-Tree in JavaScript

这里用 JavaScript 实现一个二叉搜索树。二叉搜索树可以很方便地进行排序。下面的实现比较简单,很容易就会出现非平衡二叉树。G.M. Adelson-Velsky 和 E.M. Landis 在 1962 年的论文《An Algorithm For The Organization Of Information》中提出了一种可以实现自平衡二叉树,后世称为 AVL 树。

除了 AVL 树,还有很多其他的平衡二叉树的实现,例如 AVL树,红黑树,B树,B+树,Trie树都分别应用在哪些现实场景中? 就是个不错的入门级参考,可以大致了解这些平衡树的特点、区别。看起来,红黑树是应用最广泛的。

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
/**
* 二叉搜索树构造函数
*/
function BinarySearchTree() {
var Node = function(key) {
this.key = key;
this.left = null;
this.right = null;
};
var root = null;
/**
* 插入值
*/
this.insert = function(key) {
var newNode = new Node(key);
if (root === null) {
root = newNode;
} else {
insertNode(root, newNode);
}
};
function insertNode(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);
}
}
}
/**
* 中序遍历二叉树
*/
this.inOrderTraverse = function(cb) {
inOrderTraverseNode(root, cb);
};
function inOrderTraverseNode(node, cb) {
if (node !== null) {
inOrderTraverseNode(node.left, cb);
cb(node);
inOrderTraverseNode(node.right, cb);
}
}
/**
* 先序遍历二叉树
*/
this.preOrderTraverse = function(cb) {
preOrderTraverseNode(root, cb);
};
function preOrderTraverseNode(node, cb) {
if (node !== null) {
cb(node);
preOrderTraverseNode(node.left, cb);
preOrderTraverseNode(node.right, cb);
}
}
/**
* 后序遍历二叉树
*/
this.postOrderTraverse = function(cb) {
postOrderTraverseNode(root, cb);
};
function postOrderTraverseNode(node, cb) {
if (node !== null) {
postOrderTraverseNode(node.left, cb);
postOrderTraverseNode(node.right, cb);
cb(node);
}
}
/**
* 获取最小值节点
*/
this.min = function() {
return findMinNode(root);
};
function findMinNode(node) {
var n = node;
while(n && n.left) {
n = n.left;
}
return n;
}
/**
* 移除一个节点
*/
this.remove = function(key) {
root = removeNode(root, key);
}
function removeNode(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 {
if (node.left === null && node.right === null) {
node = null;
return node;
} else 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 bst = new BinarySearchTree();
bst.insert(17);
bst.insert(1);
bst.insert(2);
bst.insert(1);
bst.insert(10);
bst.insert(4);
bst.insert(15);
bst.insert(6);
console.log('\n中序遍历二叉树 =>\n');
bst.inOrderTraverse(function(node) {
console.log(node.key);
});
console.log('\n先序遍历二叉树 =>\n');
bst.preOrderTraverse(function(node) {
console.log(node.key);
});
console.log('\n后序遍历二叉树 =>\n');
bst.postOrderTraverse(function(node) {
console.log(node.key);
});
console.log('\nmin node =>', bst.min().key);
bst.remove(2);
console.log('\n先序遍历二叉树 =>\n');
bst.preOrderTraverse(function(node) {
console.log(node.key);
});

代码分析

上面的测试代码,执行完所有的插入操作之后,二叉搜索树是这个样子的:

也就是说,它并非尽可能是满二叉树。会因为输入数据的顺序原因,而导致某个或某些分支特别长。这样是非常影响搜索效率的。AVL 树、红黑树等都是为了尽可能实现满二叉树而提出的算法。

Share