共计 6681 个字符，预计需要花费 17 分钟才能阅读完成。
JavaScript 数据结构篇 之 BST
前言
有段时间没有写文章了，整个人感觉变得有点懒散了，大家可不要向我一样哦~ 今天开始 seaconch 打算开始记录 JavaScript 数据结构的学习经历。至此，开始。
课本：《学习 JavaScript 数据结构与算法 (第 2 版)》
术语：
BST (binary sort tree)
LST (left subtree)
RST (right subtree)
OUTLINE
特性
定义
插入
查找
最大
最小
移除
特性
BST 有如下特性：
若 LST 不为空，则 LST 所有节点值都 小 于它的根节点值
若 RST 不为空，则 RST 所有节点值都 大 于它的根节点值
左右子树也都是 BST
没有重复键
定义
为了存储 BST，我们先定义一个 Node 类型，存储各个节点。
Node 节点的构造函数默认为其初始化 Subtree 都是 null。
/**
* 节点
*/
class Node {
constructor (key) {
this.key = key;
this.left = null;
this.right = null;
}
}
然后是 BST
BST 的类型我们只初始化了一个根节点 root。
/**
* 二叉排序树
*/
class BinarySearchTree {
constructor() {
this.root = null;
}
}
插入
插入节点只要遵循一个原则就好：大与 node.key 就向 node.right 中插入，小于 node.key 就向 node.left 插入。
首先定义私有函数。
const insertNode = Symbol(‘insertNode’);
/**
* 插入节点
*/
insert(key) {
let newNode = new Node(key);
if (this.root === null) this.root = newNode;
else this[insertNode](this.root, newNode);
}
/**
* 插入节点
* @param {当前节点} node
* @param {新节点} newNode
*/
[insertNode] (node, newNode) {
if (newNode.key < node.key) {
if (node.left === null) node.left = newNode;
else this[insertNode](node.left, newNode);
} else {
if (node.right === null) node.right = newNode;
else this[insertNode](node.right, newNode);
}
}
这里稍微的说明一下，之所以写成私有函数，无非就是为了不希望外部看到这些没必要的。
其实东西多了感觉也会乱糟糟的 …
接下来为了查看一下效果，我们来写一个初始化 BST 的函数。
我们的目标是初始化一个这样的 BST。
/**
* 初始化数据
* @param {树} tree
*/
function initialization(tree) {
let treeKeys = [50, 25, 13, 5, 19, 35, 28, 49, 75, 64, 56, 74, 85, 79, 99];
treeKeys.forEach(key => tree.insert(key) )
}
现在来试试实例化一个 BST 来看看效果。
let tree = new BinarySearchTree();
initialization(tree);
console.log(tree.root);
打印效果如图
查找
由:
若 LST 不为空，则 LST 所有节点值都 小 于它的根节点值
若 RST 不为空，则 RST 所有节点值都 大 于它的根节点值
左右子树也都是 BST
因此我们可以相对快速的查找元素。
定义私有函数
const searchNode = Symbol(‘searchNode’);
/**
* 是否存在目标 key
*/
existKey(key) {
return this[searchNode](this.root, key);
}
/**
*
* @param {当前节点} node
* @param {key} key
*/
[searchNode] (node, key) {
if (node === null) return false;
if (key < node.key) return this[searchNode](node.left, key);
else if (key > node.key) return this[searchNode](node.right, key);
else return true;
}
我们的思路是这样的：
如果要查找的 key 值 小于 当前节点的 key 值，则向 LST 继续查找; 如果要查找的 key 值 大于 当前节点的 key 值，则向 RST 继续查找; 如果要查找的 key 值 等于 当前节点的 key 值，则返回 true
运行效果如下：
最大值
由：
若 RST 不为空，则 RST 所有节点值都 大 于它的根节点值
左右子树也都是 BST
我们可以求得最大值
很明显是这样的
代码如下
定义私有函数
const maxNode = Symbol(‘maxNode’);
/**
* 获取最大节点 key
*/
max() {
return this[maxNode](this.root);
}
/**
* 获取最大节点 key
* @param {节点} node
*/
[maxNode] (node) {
if (node) {
while (node && node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
}
输出结果为：99
最小值
获取最小值的方法与最大值类似，只是方向变了一下
定义私有函数
const minNode = Symbol(‘minNode’);
/**
* 获取最小节点 key
*/
min() {
return this[minNode](this.root);
}
/**
* 获取最小节点 key
* @param {节点} node
*/
[minNode] (node) {
if (node) {
while (node && node.left !== null) {
node = node.left;
}
return node.key;
}
return null;
}
运行结果自然是：5
移除
移除相对来说复杂一点，因为假如我们要移除的是一个父节点，那他们的子节点怎么办？
当然也是有相应的应对措施的。
对于没有 subtree 的 node 来说，只需要把他们修改为 null 即可
对于存在 subtree 的 node 来说，就要考虑所有情况分别处理
当 LST === null 时 => RST 上前来顶替待删除节点的位置
当 RST === null 时 => LST 上前来顶替待删除节点的位置
当 LST && RST 都不是 null 时，由 RST 中最小节点上前来顶起待删除节点的位置
图例说明：
1. LST 等于 null
2. RST 等于 null
3. LST 和 RST 都不等于 null
定义私有函数
const removeNode = Symbol(‘removeNode’);
const findMinNode = Symbol(‘findMinNode’);
/**
* 删除节点
*/
remove(key) {
this[removeNode](this.root, key);
}
/**
* 删除节点，返回删除后的 tree
* @param {当前节点} node
* @param {key} key
*/
[removeNode] (node, key) {
if (node === null) /** the tree is empty or does not have this key who you want to remove. */ return null;
if (key < node.key) /** the key of currrent node is bigger than target key. */ {
node.left = this[removeNode](node.left, key);
return node;
} else if (key > node.key) /** smaller */ {
node.right = this[removeNode](node.right, key);
return node;
} else /** 相等 */ {
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;
}
/**
* 来到这里代表当前节点有两个子节点
*/
let aux = this[findMinNode](node.right); // 找到右节点的最小节点
node.key = aux.key; // 把要删除的节点的 key 覆盖为右侧最小节点 key
node.right = this[removeNode](node.right, aux.key); // 重构 right side tree (删除上面找到的 aux 节点)
return node;
}
}
/**
* 返回目标节点分支下最小节点
* @param {目标节点} node
*/
[findMinNode] (node) {
while (node && node.left !== null) {
node = node.left;
}
return node;
}
好了，现在来一起运行一下，看一下效果吧
oh, sorry…
源码如下：
/**
* 节点
*/
class Node {
constructor (key) {
this.key = key;
this.left = null;
this.right = null;
}
}
const insertNode = Symbol(‘insertNode’);
const removeNode = Symbol(‘removeNode’);
const findMinNode = Symbol(‘findMinNode’);
const minNode = Symbol(‘minNode’);
const maxNode = Symbol(‘maxNode’);
const searchNode = Symbol(‘searchNode’);
/**
* 二叉排序树
*/
class BinarySearchTree {
constructor() {
this.root = null;
}
/**
* 插入节点
*/
insert(key) {
let newNode = new Node(key);
if (this.root === null) this.root = newNode;
else this[insertNode](this.root, newNode);
}
/**
* 插入节点
* @param {当前节点} node
* @param {新节点} newNode
*/
[insertNode] (node, newNode) {
if (newNode.key < node.key) {
if (node.left === null) node.left = newNode;
else this[insertNode](node.left, newNode);
} else {
if (node.right === null) node.right = newNode;
else this[insertNode](node.right, newNode);
}
}
/**
* 删除节点
*/
remove(key) {
this[removeNode](this.root, key);
}
/**
* 删除节点，返回删除后的 tree
* @param {当前节点} node
* @param {key} key
*/
[removeNode] (node, key) {
if (node === null) /** the tree is empty or does not have this key who you want to remove. */ return null;
if (key < node.key) /** the key of currrent node is bigger than target key. */ {
node.left = this[removeNode](node.left, key);
return node;
} else if (key > node.key) /** smaller */ {
node.right = this[removeNode](node.right, key);
return node;
} else /** 相等 */ {
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;
}
/**
* 来到这里代表当前节点有两个子节点
*/
let aux = this[findMinNode](node.right); // 找到右节点的最小节点
node.key = aux.key; // 把要删除的节点的 key 覆盖为右侧最小节点 key
node.right = this[removeNode](node.right, aux.key); // 重构 right side tree (删除上面找到的 aux 节点)
return node;
}
}
/**
* 返回目标节点分支下最小节点
* @param {目标节点} node
*/
[findMinNode] (node) {
while (node && node.left !== null) {
node = node.left;
}
return node;
}
/**
* 获取最小节点 key
*/
min() {
return this[minNode](this.root);
}
/**
* 获取最小节点 key
* @param {节点} node
*/
[minNode] (node) {
if (node) {
while (node && node.left !== null) {
node = node.left;
}
return node.key;
}
return null;
}
/**
* 获取最大节点 key
*/
max() {
return this[maxNode](this.root);
}
/**
* 获取最大节点 key
* @param {节点} node
*/
[maxNode] (node) {
if (node) {
while (node && node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
}
/**
* 是否存在目标 key
*/
existKey(key) {
return this[searchNode](this.root, key);
}
/**
*
* @param {当前节点} node
* @param {key} key
*/
[searchNode] (node, key) {
if (node === null) return false;
if (key < node.key) return this[searchNode](node.left, key);
else if (key > node.key) return this[searchNode](node.right, key);
else return true;
}
}
/**
* 初始化数据
* @param {树} tree
*/
function initialization(tree) {
let treeKeys = [50, 25, 13, 5, 19, 35, 28, 49, 75, 64, 56, 74, 85, 79, 99];
treeKeys.forEach(key => tree.insert(key) )
}
let tree = new BinarySearchTree();
initialization(tree);
console.log(‘the min node.key is: ‘, tree.min());
console.log(‘the max node.key is: ‘, tree.max());
let tempKey = 49;
console.log(‘the key of [‘, tempKey, ‘]’, tree.existKey(tempKey) ? ‘real’ : ‘not’, ‘exist.’);
tree.remove(49)
console.log(‘remove key [‘, tempKey, ‘]’);
console.log(‘the key of [‘, tempKey, ‘]’, tree.existKey(tempKey) ? ‘real’ : ‘not’, ‘exist.’);
continue…