二叉排序树

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; }}然后是 BSTBST 的类型我们只初始化了一个根节点 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 thismaxNode; } /* * 获取最大节点 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 thisminNode; } /* * 获取最小节点 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 等于 null2. RST 等于 null3. 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 = thisfindMinNode; // 找到右节点的最小节点 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 = thisfindMinNode; // 找到右节点的最小节点 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 thisminNode; } /* * 获取最小节点 key * @param {节点} node / [minNode] (node) { if (node) { while (node && node.left !== null) { node = node.left; } return node.key; } return null; } /* * 获取最大节点 key / max() { return thismaxNode; } /* * 获取最大节点 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…