前言
【从蛋壳到满天飞】JS 数据结构解析和算法实现，全部文章大概的内容如下： Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜索树)、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(优先队列)、SegmentTree(线段树)、Trie(字典树)、UnionFind(并查集)、AVLTree(AVL 平衡树)、RedBlackTree(红黑平衡树)、HashTable(哈希表)
源代码有三个：ES6（单个单个的 class 类型的 js 文件） | JS + HTML（一个 js 配合一个 html）| JAVA (一个一个的工程)
全部源代码已上传 github，，光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。
本文章适合 对数据结构想了解并且感兴趣的人群，文章风格一如既往如此，就觉得手机上看起来比较方便，这样显得比较有条理，整理这些笔记加源码，时间跨度也算将近半年时间了，希望对想学习数据结构的人或者正在学习数据结构的人群有帮助。
颜色翻转和右旋转
-
添加元素的情况
- 添加的第一个元素会变成根节点，并且会被设置为黑色，
- 如果再添加一个元素，如果这个元素被添加为这个根节点的左孩子，
- 那么就顺理成章的保持了红黑树的性质，
- 因为这个新节点与根节点组成了二三树中的一个三节点，
- 但是如果添加的这个元素被添加为这个根节点的右孩子，
- 那么就需要进行左旋转的操作，否则就会违背红黑树的性质。
-
在红黑树中的三节点中添加元素的第一种情况
-
下图中节点 37 和节点 42 已经形成了一个三节点，
-
因为所谓红色节点的意思就是它和它的父亲是融合在一起的，
-
如果这个时候再添加一个元素 66，新添加的节点默认为红色，
-
那么按照二分搜索树中的性质，这个元素会被添加为根节点 44 的右孩子，
-
此时就会对应二三树中临时的四节点，在红黑树的表示就是，
-
根节点是黑色的，左右孩子节点都是红色的，
-
所谓红色节点的意思就是它和它的父亲是融合在一起的。
// 中括号为黑色节点，大括号为红色节点// [42]// /// {37}// 添加元素 66// [42]// / \// {37} {66}复制代码
-
-
颜色翻转
-
在二三树中这个临时的四节点之后会被分裂成三个二节点，
-
对应红黑树中的操作是将根节点 42 下面两个节点 37 和 66 都染成黑色，
-
这样就表示了在二三树中三个二节点组成了一棵子树，
-
临时的四节点分裂之后，新的子树的根节点需要向上进行融合操作，
-
所以在红黑树中的操作是，这个根节点 42 要变成红色，
-
因为所谓红色节点的意思就是它和它的父亲是融合在一起的，
-
这个过程就让根节点的颜色与左右子树的颜色进行了一个翻转操作，
-
颜色翻转的英文就是 flipColors，这是在红黑树中添加一个新元素的辅助过程，
-
实际上也是等价的在二三树中的三节点中添加了一个新元素所对应的一个辅助过程。
// 中括号为黑色节点，大括号为红色节点// 添加元素 66// [42]// / \// {37} {66}// 颜色翻转// {42}// / \// [37] [66]复制代码
-
-
在红黑树中的三节点中添加元素的另外一种情况
- 下图中节点 37 和节点 42 已经形成了一个三节点，，
- 如果这个时候再添加一个元素 12，新添加的节点默认为红色，
- 那么按照二分搜索树中的性质，这个元素会被添加为根节点 44 的左孩子 37 的左孩子，
- 这样一来就相当于节点 42 的左孩子是红色节点然后左孩子的左孩子还是红色节点，
- 所谓红色的节点，就是它与它的父节点是融合在了一起，
- 这样的一种情况也可以将它理解为一个临时的四节点，
- 节点 23 是红色的，它和它的父节点 37 融合在了一起，然后节点 37 是红色，
- 它和它的父节点 42 也是融合在一起的，所以这种形状也表示对应二三树中的四节点，
- 也是一样的，需要对四节点进行分裂操作，变成一个由三个二节点组成的子树，
- 所以在红黑树中需要将这样的向左偏斜的形状进行一个纠正，
- 要让它变成一个根节点左右两个孩子的形状，此时就需要引入另外一个子过程右旋转。
// 中括号为黑色节点，大括号为红色节点// [42]// /// {37}// 添加元素 12// [42]// /// {37}// /// {23}复制代码 -
右旋转
- 让节点 node 的左子树与节点 x 进行断开连接，让节点 x 与右子树 T1 断开连接，
- 让节点 x 的右子树与节点 node 进行连接，让节点 node 的左子树与 T1 进行连接，
- 这样就有一个右旋转的过程，这个和左旋转是类似的，
- 之后对于红黑树来说还需要维护一下颜色的信息，
- 这个维护的过程和之前讲的左旋转的过程是一样的，
- 新的根节点 x 的颜色应该和原来的根节点 node 的颜色是一样的，
- 经过这样的处理之后，node 虽然变成了 x 的右孩子了，
- 但是需要将它染色成红色，这是为了保证后续的操作能够有效进行，
- 右旋转的作用只是让这三个节点对应成二三树中的临时四节点。
- 也还是一样，需要进行颜色翻转操作，从而维护红黑树的性质，
- 新的子树的根节点需要向上进行融合，所以它需要变成红色，
- 在红黑树中红色节点的左右子树的颜色都是黑色的，
- 所以根节点的左右孩子节点颜色都要变成黑色。
// 中括号为黑色节点，大括号为红色节点// 小括号只是参与演示，并不真实存在// 原来是这样的// [42] node// / \// x {37} (T2)// / \// {23} (T1)// 进行右旋转后// {37} x// / \// {23} {42} node// / \// (T1) (T2)// node.left = T1// x.right = node;// x.color = node.color;// node.color = RED;// 颜色翻转后// {37} x// / \// [23] [42] node// / \// (T1) (T2)// x.color = RED;// x.left.color = BLACK;// x.right.color = BLACK;复制代码
代码示例
-
MyRedBlackTree
// 自定义红黑树节点 RedBalckTreeNodeclass MyRedBalckTreeNode { constructor(key = null, value = null, left = null, right = null) { this.key = key; this.value = value; this.left = left; this.right = right; this.color = MyRedBlackTree.RED; // MyRedBlackTree.BLACK; } // @Override toString 2018-11-25-jwl toString() { return ( this.key.toString() + '--->' + this.value.toString() + '--->' + (this.color ? '红色节点' : '绿色节点') ); }}// 自定义红黑树 RedBlackTreeclass MyRedBlackTree { constructor() { MyRedBlackTree.RED = true; MyRedBlackTree.BLACK = false; this.root = null; this.size = 0; } // 判断节点node的颜色 isRed(node) { // 定义：空节点颜色为黑色 if (!node) return MyRedBlackTree.BLACK; return node.color; } // node x // / \ 左旋转 / \ // T1 x ---------> node T3 // / \ / \ // T2 T3 T1 T2 leftRotate(node) { const x = node.right; // 左旋转过程 node.right = x.left; x.left = node; // 染色过程 x.color = node.color; node.color = MyRedBlackTree.RED; // 返回这个 x return x; } // 颜色翻转 当前节点变红 左右孩子变黑 // 表示当前节点需要继续向上进行融合 flipColors(node) { node.color = MyRedBlackTree.RED; node.left.color = MyRedBlackTree.BLACK; node.right.color = MyRedBlackTree.BLACK; } // node x // / \ 右旋转 / \ // x T2 -------> y node // / \ / \ // y T1 T1 T2 rightRotate(node) { const x = node.left; // 右翻转过程 node.left = x.right; x.right = node; // 染色过程 x.color = node.color; node.color = MyRedBlackTree.RED; // 返回这个 x return x; } // 比较的功能 compare(keyA, keyB) { if (keyA === null || keyB === null) throw new Error("key is error. key can't compare."); if (keyA > keyB) return 1; else if (keyA < keyB) return -1; else return 0; } // 根据key获取节点 - getNode(node, key) { // 先解决最基本的问题 if (node === null) return null; // 开始将复杂的问题 逐渐缩小规模 // 从而求出小问题的解，最后构建出原问题的解 switch (this.compare(node.key, key)) { case 1: // 向左找 return this.getNode(node.left, key); break; case -1: // 向右找 return this.getNode(node.right, key); break; case 0: // 找到了 return node; break; default: throw new Error( 'compare result is error. compare result : 0、 1、 -1 .' ); break; } } // 添加操作 + add(key, value) { this.root = this.recursiveAdd(this.root, key, value); this.root.color = MyRedBlackTree.BLACK; } // 添加操作 递归算法 - recursiveAdd(node, key, value) { // 解决最简单的问题 if (node === null) { this.size++; return new MyRedBalckTreeNode(key, value); } // 将复杂的问题规模逐渐变小， // 从而求出小问题的解，从而构建出原问题的答案 if (this.compare(node.key, key) > 0) node.left = this.recursiveAdd(node.left, key, value); else if (this.compare(node.key, key) < 0) node.right = this.recursiveAdd(node.right, key, value); else node.value = value; return node; } // 删除操作 返回被删除的元素 + remove(key) { let node = this.getNode(this.root, key); if (node === null) return null; this.root = this.recursiveRemove(this.root, key); return node.value; } // 删除操作 递归算法 + recursiveRemove(node, key) { // 解决最基本的问题 if (node === null) return null; if (this.compare(node.key, key) > 0) { node.left = this.recursiveRemove(node.left, key); return node; } else if (this.compare(node.key, key) < 0) { node.right = this.recursiveRemove(node.right, key); return node; } else { // 当前节点的key 与 待删除的key的那个节点相同 // 有三种情况 // 1. 当前节点没有左子树，那么只有让当前节点的右子树直接覆盖当前节点，就表示当前节点被删除了 // 2. 当前节点没有右子树，那么只有让当前节点的左子树直接覆盖当前节点，就表示当前节点被删除了 // 3. 当前节点左右子树都有， 那么又分两种情况，使用前驱删除法或者后继删除法 // 1. 前驱删除法：使用当前节点的左子树上最大的那个节点覆盖当前节点 // 2. 后继删除法：使用当前节点的右子树上最小的那个节点覆盖当前节点 if (node.left === null) { let rightNode = node.right; node.right = null; this.size--; return rightNode; } else if (node.right === null) { let leftNode = node.left; node.left = null; this.size--; return leftNode; } else { let predecessor = this.maximum(node.left); node.left = this.removeMax(node.left); this.size++; // 开始嫁接 当前节点的左右子树 predecessor.left = node.left; predecessor.right = node.right; // 将当前节点从根节点剔除 node = node.left = node.right = null; this.size--; // 返回嫁接后的新节点 return predecessor; } } } // 删除操作的两个辅助函数 // 获取最大值、删除最大值 // 以前驱的方式 来辅助删除操作的函数 // 获取最大值 maximum(node) { // 再也不能往右了，说明当前节点已经是最大的了 if (node.right === null) return node; // 将复杂的问题渐渐减小规模，从而求出小问题的解，最后用小问题的解构建出原问题的答案 return this.maximum(node.right); } // 删除最大值 removeMax(node) { // 解决最基本的问题 if (node.right === null) { let leftNode = node.left; node.left = null; this.size--; return leftNode; } // 开始化归 node.right = this.removeMax(node.right); return node; } // 查询操作 返回查询到的元素 + get(key) { let node = this.getNode(this.root, key); if (node === null) return null; return node.value; } // 修改操作 + set(key, value) { let node = this.getNode(this.root, key); if (node === null) throw new Error(key + " doesn't exist."); node.value = value; } // 返回是否包含该key的元素的判断值 + contains(key) { return this.getNode(this.root, key) !== null; } // 返回映射中实际的元素个数 + getSize() { return this.size; } // 返回映射中是否为空的判断值 + isEmpty() { return this.size === 0; } // @Override toString() 2018-11-05-jwl toString() { let mapInfo = `MyBinarySearchTreeMap: size = ${ this.size}, data = [ `; document.body.innerHTML += `MyBinarySearchTreeMap: size = ${ this.size }, data = [ `; // 以非递归的前序遍历 输出字符串 let stack = new MyLinkedListStack(); stack.push(this.root); if (this.root === null) stack.pop(); while (!stack.isEmpty()) { let node = stack.pop(); if (node.left !== null) stack.push(node.left); if (node.right !== null) stack.push(node.right); if (node.left === null && node.right === null) { mapInfo += ` ${node.toString()} \r\n`; document.body.innerHTML += ` ${node.toString()} `; } else { mapInfo += ` ${node.toString()}, \r\n`; document.body.innerHTML += ` ${node.toString()}, `; } } mapInfo += ` ] \r\n`; document.body.innerHTML += ` ] `; return mapInfo; }}复制代码
向红黑树中添加新节点
-
在红黑树中添加新节点等价于在二三树的一个二或三节点上融合一个新的元素
-
在二节点上进行融合操作，
-
如果新添加的这个节点比最后找到的叶子节点的元素小，
-
那么对应在红黑树中的操作就是直接添加为当前节点的左孩子即可；
-
如果新添加的这个节点比最后找到的叶子节点的元素大，
-
那么对应在红黑树中的操作是 首先直接添加为当前节点的右孩子，
-
然后再进行左旋转操作，让新添加的节点作为根节点，
-
而原来的根节点作为新添加的节点的左孩子节点即可；
-
左旋转操作需要将新的根节点与原来的根节点的颜色对调，
-
然后将原来的根节点染色为红色，最后，
-
左旋转的过程中并不会去维护红黑树的性质，
-
左旋转的作用只是让这两个节点对应成二三树中的三节点。
-
在三节点上进行融合操作，
-
如果新添加的这个节点比根节点要大，
-
那么对应在红黑树中的操作就是直接添加为根节点的右孩子，
-
之后进行一下颜色的翻转操作即可；
-
如果新添加的这个节点比根节点要小并且比根节点的左孩子要小，
-
那么对应在红黑树中的操作就是先直接添加为根节点的左孩子的左孩子，
-
然后进行一下右旋转，
-
旋转右旋转操作需要将新的根节点与原来的根节点的颜色对调，
-
然后将原来的根节点染色为红色，
-
也是一样，旋转操作不会去维护红黑树的性质，
-
右旋转的作用只是让这三个节点对应成二三树中的临时四节点，
-
之后进行一下颜色的翻转操作即可；
-
如果新添加的这个节点比根节点要小并且比根节点的左孩子要大，
-
那么对应在红黑树中的操作就是先直接添加为根节点的左孩子的右孩子，
-
然后对这个根节点的左孩子进行一个左旋转操作，
-
左旋转操作之后就如下图所示，
-
就变成了
新添加的这个节点比根节点要小并且比根节点的左孩子要小的情况， -
那么就对这个根节点进行一个右旋转操作，
-
再来一个颜色翻转操作即可。
// 中括号为黑色节点，大括号为红色节点// 原来是这样的// [42]// /// {37}// \// {40}// 对根节点的左孩子 进行左旋转后 染色后// [42]// /// {40}// /// {37}// 对根节点 进行右旋转后 染色后// [40]// / \// {37} {42}//// 对根节点 颜色翻转后// {40}// / \// [37] [42]复制代码
-
-
红黑树添加节点逻辑分布图
-
下图中的逻辑只要分为三种
-
是否需要左旋转、右旋转、颜色翻转，
-
当当前节点的右孩子为红色并且当前节点的左孩子不为红色时，那么就需要进行左旋转；
-
当当前节点的左孩子为红色并且当前节点的左孩子的左孩子也为红色时，那么就需要进行右旋转；
-
当当前节点的左右孩子全都是红色时，那么就需要进行颜色翻转；
-
这三种逻辑并非是互斥的，而是相吸，每一次都需要进行这三种判断，
-
下图也是按照这样的顺序来进行步骤的执行的。
// 中括号为黑色节点，大括号为红色节点// 融合二节点// 步骤一 步骤二 步骤三// [null] [node] [node] [X]// ----> ----> \ ----> /// {X} {node}// 首次添加节点 ----> 添加节点X ----> 左旋转//// 情况一 如果红黑树的根节点为空// 那么 步骤一// 情况二 如果红黑树的根节点不为空 新添加的节点小于根节点// 那么 步骤一 --> 步骤三// 情况三 如果红黑树的根节点不为空 新添加的节点大于根节点// 那么 步骤一 --> 步骤二 --> 步骤三// 融合三节点//// 步骤1 步骤2 步骤3 步骤4 步骤5// [node] [node] [node] [Y] {Y}// / ----> / ----> / ----> / \ ----> / \//{X} {X} {Y} {X} {node} [X] [node]// \ /// {Y} {X}// 添加节点Y ----> 左旋转 ----> 右旋转 ----> 颜色翻转//// 情况一 如果新添加的这个新节点 大于 根节点// 那么步骤1 --> 步骤4 --> 步骤5// 情况二 如果新添加的这个节点比根节点要小并且比根节点的左孩子要小// 那么步骤1 --> 步骤3 --> 步骤4 --> 步骤5// 情况三 如果新添加的这个节点比根节点要小并且比根节点的左孩子要大// 那么步骤1 --> 步骤2 --> 步骤3 --> 步骤4 --> 步骤5复制代码
-
-
红黑树添加节点时维护性质的时机
- 红黑树维护的时机和 AVL 树一样，
- 先使用二分搜索树的基本逻辑将新的节点添加进红黑树中，
- 之后再来进行回溯向上维护的操作，
- 也就是将当前的节点维护之后，再将维护后的新的节点返回给递归调用的上一层，
- 然后再到上一层中进行维护，再将维护后的新的节点返回给递归调用的上一层，
- 整个过程依此类推。
代码示例
-
MyRedBlackTree
// 自定义红黑树节点 RedBalckTreeNodeclass MyRedBalckTreeNode { constructor(key = null, value = null, left = null, right = null) { this.key = key; this.value = value; this.left = left; this.right = right; this.color = MyRedBlackTree.RED; // MyRedBlackTree.BLACK; } // @Override toString 2018-11-25-jwl toString() { return ( this.key.toString() + '--->' + this.value.toString() + '--->' + (this.color ? '红色节点' : '绿色节点') ); }}// 自定义红黑树 RedBlackTreeclass MyRedBlackTree { constructor() { MyRedBlackTree.RED = true; MyRedBlackTree.BLACK = false; this.root = null; this.size = 0; } // 判断节点node的颜色 isRed(node) { // 定义：空节点颜色为黑色 if (!node) return MyRedBlackTree.BLACK; return node.color; } // node x // / \ 左旋转 / \ // T1 x ---------> node T3 // / \ / \ // T2 T3 T1 T2 leftRotate(node) { const x = node.right; // 左旋转过程 node.right = x.left; x.left = node; // 染色过程 x.color = node.color; node.color = MyRedBlackTree.RED; // 返回这个 x return x; } // 颜色翻转 当前节点变红 左右孩子变黑 // 表示当前节点需要继续向上进行融合 flipColors(node) { node.color = MyRedBlackTree.RED; node.left.color = MyRedBlackTree.BLACK; node.right.color = MyRedBlackTree.BLACK; } // node x // / \ 右旋转 / \ // x T2 -------> y node // / \ / \ // y T1 T1 T2 rightRotate(node) { const x = node.left; // 右翻转过程 node.left = x.right; x.right = node; // 染色过程 x.color = node.color; node.color = MyRedBlackTree.RED; // 返回这个 x return x; } // 比较的功能 compare(keyA, keyB) { if (keyA === null || keyB === null) throw new Error("key is error. key can't compare."); if (keyA > keyB) return 1; else if (keyA < keyB) return -1; else return 0; } // 根据key获取节点 - getNode(node, key) { // 先解决最基本的问题 if (!node) return null; // 开始将复杂的问题 逐渐缩小规模 // 从而求出小问题的解，最后构建出原问题的解 switch (this.compare(node.key, key)) { case 1: // 向左找 return this.getNode(node.left, key); break; case -1: // 向右找 return this.getNode(node.right, key); break; case 0: // 找到了 return node; break; default: throw new Error( 'compare result is error. compare result : 0、 1、 -1 .' ); break; } } // 添加操作 + add(key, value) { this.root = this.recursiveAdd(this.root, key, value); this.root.color = MyRedBlackTree.BLACK; } // 添加操作 递归算法 - recursiveAdd(node, key, value) { // 解决最简单的问题 if (!node) { this.size++; return new MyRedBalckTreeNode(key, value); } // 将复杂的问题规模逐渐变小， // 从而求出小问题的解，从而构建出原问题的答案 if (this.compare(node.key, key) > 0) node.left = this.recursiveAdd(node.left, key, value); else if (this.compare(node.key, key) < 0) node.right = this.recursiveAdd(node.right, key, value); else { node.value = value; return node; } // 红黑树性质的维护 // 是否需要左旋转 // 如果当前节点的右孩子是红色 并且 左孩子不是红色 if (this.isRed(node.right) && !this.isRed(node.left)) node = this.leftRotate(node); // 是否需要右旋转 // 如果当前节点的左孩子是红色 并且 左孩子的左孩子也是红色 if (this.isRed(node.left) && this.isRed(node.left.left)) node = this.rightRotate(node); // 是否需要颜色的翻转 // 当前节点的左孩子和右孩子全都是红色 if (this.isRed(node.left) && this.isRed(node.right)) this.flipColors(node); // 最后返回这个node return node; } // 删除操作 返回被删除的元素 + remove(key) { let node = this.getNode(this.root, key); if (!node) return null; this.root = this.recursiveRemove(this.root, key); return node.value; } // 删除操作 递归算法 + recursiveRemove(node, key) { // 解决最基本的问题 if (!node) return null; if (this.compare(node.key, key) > 0) { node.left = this.recursiveRemove(node.left, key); return node; } else if (this.compare(node.key, key) < 0) { node.right = this.recursiveRemove(node.right, key); return node; } else { // 当前节点的key 与 待删除的key的那个节点相同 // 有三种情况 // 1. 当前节点没有左子树，那么只有让当前节点的右子树直接覆盖当前节点，就表示当前节点被删除了 // 2. 当前节点没有右子树，那么只有让当前节点的左子树直接覆盖当前节点，就表示当前节点被删除了 // 3. 当前节点左右子树都有， 那么又分两种情况，使用前驱删除法或者后继删除法 // 1. 前驱删除法：使用当前节点的左子树上最大的那个节点覆盖当前节点 // 2. 后继删除法：使用当前节点的右子树上最小的那个节点覆盖当前节点 if (node.left === null) { let rightNode = node.right; node.right = null; this.size--; return rightNode; } else if (node.right === null) { let leftNode = node.left; node.left = null; this.size--; return leftNode; } else { let predecessor = this.maximum(node.left); node.left = this.removeMax(node.left); this.size++; // 开始嫁接 当前节点的左右子树 predecessor.left = node.left; predecessor.right = node.right; // 将当前节点从根节点剔除 node = node.left = node.right = null; this.size--; // 返回嫁接后的新节点 return predecessor; } } } // 删除操作的两个辅助函数 // 获取最大值、删除最大值 // 以前驱的方式 来辅助删除操作的函数 // 获取最大值 maximum(node) { // 再也不能往右了，说明当前节点已经是最大的了 if (!node.right) return node; // 将复杂的问题渐渐减小规模，从而求出小问题的解，最后用小问题的解构建出原问题的答案 return this.maximum(node.right); } // 删除最大值 removeMax(node) { // 解决最基本的问题 if (!node.right) { let leftNode = node.left; node.left = null; this.size--; return leftNode; } // 开始化归 node.right = this.removeMax(node.right); return node; } // 查询操作 返回查询到的元素 + get(key) { let node = this.getNode(this.root, key); if (!node) return null; return node.value; } // 修改操作 + set(key, value) { let node = this.getNode(this.root, key); if (!node) throw new Error(key + " doesn't exist."); node.value = value; } // 返回是否包含该key的元素的判断值 + contains(key) { return this.getNode(this.root, key) !== null; } // 返回映射中实际的元素个数 + getSize() { return this.size; } // 返回映射中是否为空的判断值 + isEmpty() { return this.size === 0; } // @Override toString() 2018-11-05-jwl toString() { let mapInfo = `MyBinarySearchTreeMap: size = ${ this.size}, data = [ `; document.body.innerHTML += `MyBinarySearchTreeMap: size = ${ this.size }, data = [ `; // 以非递归的前序遍历 输出字符串 let stack = new MyLinkedListStack(); stack.push(this.root); if (this.root === null) stack.pop(); while (!stack.isEmpty()) { let node = stack.pop(); if (node.left !== null) stack.push(node.left); if (node.right !== null) stack.push(node.right); if (node.left === null && node.right === null) { mapInfo += ` ${node.toString()} \r\n`; document.body.innerHTML += ` ${node.toString()} `; } else { mapInfo += ` ${node.toString()}, \r\n`; document.body.innerHTML += ` ${node.toString()}, `; } } mapInfo += ` ] \r\n`; document.body.innerHTML += ` ] `; return mapInfo; }}复制代码
红黑树的性能测试
- 测试用例的结果
- 结论是，
- 并非在任何情况下越复杂的算法或者看起来复杂度更低的算法就是更好的，
- 很多情况下对于比较简单的数据，或者对于比较少的数据，
- 可能简单的算法反而是更快一点，归并排序算法虽然是
O(nlogn)级别的， - 但是在数据规模比较小的情况下，很有可能插入排序法才是最优秀的选择，
- 红黑树本身并不是一个严格的平衡树，红黑树从根到叶子节点的高度最多会到 2logn，
- 所以是比 avl 树要高一些的，所以在查询这个操作中，红黑树并不占优势，
- 红黑树真正占优势的操作在于添加或者删除这两个操作上，
- 如果结合添加、删除、查询这三个操作，那么整体上红黑树的性能要比 AVL 树高一点，
- 如果比较偏重查询的过程，红黑树的优势体现不出来，
- 红黑树的实现其实还可以更加的优化一下。
性能测试总结
- 对于完全随机的数据，普通的二分搜索树不会退化成一个链表
- 所以还是很好用的，它的高度相对保持的比较好，
- 它的内部也不会有一些比较复杂的维持平衡的代码，
- 于是在一定程度上降低了它的开销。
- 缺点是在极端情况下会退化成链表，或者高度严重不平衡。
- 对于查询和修改操作比较多的使用情况，AVL 树比较好用。
- 对于添加删除操作比较多的使用情况，红黑树比较好用。
- 红黑树牺牲了平衡性（2logn 的高度），
- 所以红黑树并不完全满足平衡二叉树的定义 ，
- 这个高度肯定是比 AVL 树要高的，
- 红黑树的统计性能更优（综合增删改查所有的操作），
- 也正是如此，很多语言内部的容器类所实现有序的映射和集合，
- 比如 系统内置 的 Map、Set 的底层都是红黑树的，
- 红黑树本身还是一个二分搜索树，所以它也是有序的。
- 对于时间复杂度分析来说
- AVL 树与红黑树整体是在一个级别的，
- 但是平均的性能是红黑树比 AVL 树要高一点，
- 红黑树的添加和删除操作相对 AVL 树来说更有优势一些。
- 二分搜索树是有序性的
- 可以很方便的找到最大值、最小值、一个元素的前驱和后继等等，
- 所以基于二分搜索树实现的其它树如 AVL、红黑树都是有序的。
代码示例
-
Main
// main 函数class Main { constructor() { this.alterLine('RedBlackTree Comparison Area'); const n = 2000000; const myBSTMap = new MyBinarySearchTreeMap(); const myAVLTree = new MyAVLTree(); const myRedBlackTree = new MyRedBlackTree(); let performanceTest1 = new PerformanceTest(); const random = Math.random; let arrNumber = new Array(n); // 循环添加随机数的值 for (let i = 0; i < n; i++) arrNumber[i] = Math.floor(n * random()); this.alterLine('MyBSTMap Comparison Area'); const myBSTMapInfo = performanceTest1.testCustomFn(function() { // 添加 for (const word of arrNumber) myBSTMap.add(word, String.fromCharCode(word)); }); // 总毫秒数：4771 console.log(myBSTMapInfo + ' 节点个数：' + myBSTMap.getSize()); this.show(myBSTMapInfo + ' 节点个数：' + myBSTMap.getSize()); this.alterLine('MyAVLTree Comparison Area'); // const that = this; const myAVLTreeInfo = performanceTest1.testCustomFn(function() { for (const word of arrNumber) myAVLTree.add(word, String.fromCharCode(word)); }); // 总毫秒数：6226 console.log(myAVLTreeInfo + ' 节点个数：' + myAVLTree.getSize()); this.show(myAVLTreeInfo + ' 节点个数：' + myAVLTree.getSize()); this.alterLine('MyRedBlackTree Comparison Area'); const myRedBlackTreeInfo = performanceTest1.testCustomFn(function() { for (const word of arrNumber) myRedBlackTree.add(word, String.fromCharCode(word)); }); // 总毫秒数：6396 console.log( myRedBlackTreeInfo + ' 节点个数：' + myRedBlackTree.getSize() ); this.show( myRedBlackTreeInfo + ' 节点个数：' + myRedBlackTree.getSize() ); } // 将内容显示在页面上 show(content) { document.body.innerHTML += `${content}`; } // 展示分割线 alterLine(title) { let line = `--------------------${title}----------------------`; console.log(line); document.body.innerHTML += `${line}`; }}// 页面加载完毕window.onload = function() { // 执行主函数 new Main();};复制代码
更多和红黑树相关的话题
- 红黑树中删除节点
- 红黑树中的删除节点操作比添加节点操作还要复杂的多，
- 在面试中让你实现一个删除节点的操作几乎是不可能的，
- 就连添加节点的操作都很少让你实现，
- 只要是看你知不知道红黑树的本质是怎样的，
- 红黑树的本质就是，
- 红黑树与二三树之间是等价的，红黑树满足的那五条基本性质，
- 红黑树本质上是保持黑平衡的这样的一种数据结构，
- 它从某种程度上来讲牺牲了平衡性，
- 但是它的统计性能更优，添加及删除性能比 AVL 树好，
- 红黑树的添加操作是分各种情况来进行处理的，
- 红黑树的删除操作也是分各种情况来进行处理的，
- 删除节点的各种情况处理方式更加复杂，
- 就连红黑树发明人写的算法 4 里面都没有对红黑树的删除操作的逻辑进行一个详细的介绍，
- 删除操作的逻辑分杂琐碎，所以逻辑非常的复杂。
- 左倾红黑树和右倾红黑树
- 自己实现的红黑树属于左倾红黑树，
- 也是相对比较标准的一种红黑树，
- 也可以实现右倾红黑树，也就是红色节点作为右孩子节点，
- 实现出右倾红黑树就能够让你对红黑树内部的逻辑及运行机制有一个相当深刻的理解。
- 统计性能更优的树
- 红黑树是一种统计性能更优的树，
- 还有另外一种统计性能更优的树结构叫做伸展树(SplayTree)，
- 它的本质也是一种二叉树，它也可以维持自平衡，
- 这种树没有像 AVL 树那样严格的定义，它更重要的一点是运用了局部性的原理，
- 它假设通常在数据结构中存储的数据，
- 如果刚刚被访问的内容下次会有更高的概率去访问它，
- 基于这样的一个假设，
- 对这个树创建的过程以及查询、修改操作都会对这个树的结构进行一定的变化，
- 伸展树的实现要比红黑树的实现要简单。
- 基于红黑树的 Map 和 Set
- 系统内置的的 Map 和 Set 就是基于红黑树的。
- 红黑树的其它实现
- 自己实现的红黑树并不是红黑树唯一的实现方式，
- 虽然整体逻辑上原理是一样的，但是在具体实现上可以有更优化的一些实现方式，
- 算法导论中也有对红黑树的实现的描述，
- 面试中不会去考察红黑树实现的逻辑中某一个具体细节。