前言
【从蛋壳到满天飞】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，，光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。
本文章适合 对数据结构想了解并且感兴趣的人群，文章风格一如既往如此，就觉得手机上看起来比较方便，这样显得比较有条理，整理这些笔记加源码，时间跨度也算将近半年时间了，希望对想学习数据结构的人或者正在学习数据结构的人群有帮助。
平衡二叉树与 AVL 树
-
在之前实现的二分搜索树的问题
- 当你按照顺序添加
[1, 2, 3, 4, 5, 6]后， - 二分搜索树会退化成一条链表，
- 因为你第一个添加的 1 成为了根节点，
- 二分搜索树的性质是，当前节点的左子树小于当前节点，
- 当前节点的右子树大于当前节点，
- 后面的值都是按照+1 的顺序增大，
- 那么都会是在新增加的节点的右子树上不断新增节点，
- 这样就会形成一棵向右扩张的树，这棵树就像链表一样。
- 当你按照顺序添加
-
在现有的二分搜索树中添加一些机制，从而能够维持平衡二叉树的性质，
- AVL 树就是一种最为经典的平衡二叉树，
- 这种树之所以叫做 AVL 树是因为这三个字母是 AVL 树的发明人
- G.M.
Adelson-Velsky 和 E.M.Landis， - 就是这两个发明人的名字的首字母的缩写，
- 诶地欧斯-喂斯 K 和兰迪斯这两个人，
- 这两个人都是俄罗斯的计算机科学家，
- AVL 这种树结构是由它们在 1962 年首次发表的论文中提出的，
- 通常都认为 AVL 树是一种最早的自平衡二分搜索树结构。
-
平衡二叉树
- 一棵满的二叉树一定是一棵平衡二叉树，
- 满的二叉树的高度可以让整棵树的高度达到最低的状态，
- 所谓的满二叉树是指，除了叶子节点之外，
- 所有的其它的节点都有左右两个子树，通常数据不会填满一棵二叉树。
-
在自己实现的堆中引入了完全二叉树的概念，
- 对于一棵完全二叉树来说，
- 就是将所有的元素按照二叉树的形状一层一层的铺开，
- 最终得到的结果就是一棵完全的二叉树，对于完全的二叉树来说，
- 有可能有一个非叶子的节点它的右子树是空的，
- 整体而言对于完全二叉树来说，
- 它空缺节点的部分一定在整棵树的右下部分，
- 相应的对于一棵完全二叉树来说，
- 整棵树的叶子节点最大的深度值和最小的深度值相差不会超过一，
- 也就是说所有的叶子节点要不然就是在这棵树的最后一层，
- 要不然就是在这棵树的倒数第二层。
-
自己实现的线段树也是一种平衡二叉树
- 虽然它不是一个完全二叉树，
- 这是因为线段树空出来的地方不一定是在整棵树的右下角的位置，
- 但是整体在一棵线段树上，
- 叶子节点或者在最后一层或者在倒数第二层，
- 那么对于整棵树来说所有的叶子节点的深度相差不会超过一。
-
无论是堆还是线段树都是平衡二叉树的例子
- 无论是满二叉树、完全二叉树、线段树这样的一种平衡二叉树，
- 叶子节点它们之间的差距不会超过一，
- 相对来说都是比较理想的情况，这样的二叉树它的平衡是非常高的，
- 在 AVL 树中维护的这种平衡二叉树它的条件更加宽松一些，
-
在 AVL 树中定义平衡二叉树
- 对于任意一个节点来说，
- 它的左子树的高度和右子树的高度相差不能超过一，
- 这句话和之前实现的堆的完全二叉树还是线段树这样的一种二叉树
- 差不多，
- 但是实际上他们是有区别的，对于堆和线段树来说，
- 可以保证任意
一个叶子节点相应的高度差都不能超过一， - 而 AVL 定义的任意
一个节点它的左右子树高度差不能超过一， - 在这个定义下相应的得到的这棵平衡二叉树，
- 有可能看起来不是那么的平衡，因为它只是满足 AVL 定义的平衡二叉树，
- 显然这样的情况不会出现在堆或者线段树这两种树结构中，
- 这种树看起来稍微有一点的偏斜，但是仔细的去验证每一个节点，
- 会发现它是满足这个条件的，
- 任意一个节点的左子树和右子树的高度差并没有超过一，
- 如下图，节点 12 的左子树的高度为 3，右子树的高度为 2，
- 节点 12 的左右子树高度差没有超过一；节点 8 的左子树高度为 2，
- 右子树的高度 1，所以节点 8 的左右子树高度差没有超过一；
- 节点 18 的左子树的高度为 1，右子树的高度为 0，
- 所以节点 18 的左右子树的高度差没有超过一；
- 其它的节点也是一样的性质，虽然这棵树好像有一些偏斜，
- 但是 AVL 定义下的一棵平衡二叉树，对于你定义的这种平衡二叉树，
- 他也是满足平衡二叉树的高度和节点数量之间的关系是
O(logn)级别的。
// 满足AVL定义的平衡二叉树// (12)// / \// (8) (18)// /\ /// (5)(11)(17)// /// (4)复制代码
-
对上面图中的 AVL 平衡二叉树进行添加节点
- 比如添加一个节点 2，根据原来自己实现的二分搜索树的性质，
- 那么这个节点 2 就会从根节点开始一路找下来，
- 最终添加到节点 4 的左子树的位置，
- 相应的如何再添加一个节点 7，这个节点 7 会被添加到节点 5 的右子树中，
- 当树变成这个样子，那么就不再是一棵 AVL 平衡二叉树了，
- 在节点 8 这个位置，左子树的高度是 3，而右子树的高度是 1，
- 左右子树的高度差为 2，所以打破了 AVL 平衡二叉树的条件，
- 同理在节点 12 这个位置，左子树的高度是 4，而右子树的高度是 2，
- 左右子树的高度差为 2，也打破了这个条件，
- 所以现在所绘制的这棵二叉树不再是一棵 AVL 平衡二叉树。
// 添加节点2和节点7后的树// (12)// / \// (8) (18)// / \ /// (5) (11) (17)// / \// (4) (7)// /// (2)//复制代码
-
让上面图中的树维持一个平衡
- 为了让上面图中的树保持一个平衡，
- 那么必须保证在插入节点的时候相应的也要顾及这棵树右侧的部分，
- 因为现在整棵树看起来是向左偏斜的，
- 必须相应的填补这棵树右侧的空间上的一些节点，
- 只有这样才能够让整棵树继续维持这个 AVL 平衡二叉树的
- 左右子树高度差不超过一这样的性质，
- 所以基于这样定义下的平衡二叉树来说，虽然有可能看起来有一些偏斜，
- 但是实际上为了维持住这个性质，
- 那么整棵平衡二叉树左右两边都必须有一定数量的节点，
- 而不可能太过偏斜，而上图中的那棵树就是太过偏斜了，
- 导致打破了这棵 AVL 平衡二叉树左右子树高度差不超过一这样的性质，
- 所以整体而言，在这个性质下，
- 也可以保证这棵二叉树它的高度和节点数量之间的关系是
O(logn)这个级别的， - 在具体编程过程中由于跟踪每一个节点的高度是多少，
- 只有这样才方便来判断当前的这棵二叉树是否是平衡的。
-
对于之前所实现的二分搜索树来说，
-
实现这个 AVL 平衡二叉树相应的每一个节点都记录一下这个节点所在的高度，
-
其实这个记录非常的简单，对于叶子节点来说它所对应的高度就是 1，
-
也就是节点 2 对应的高度为 1；节点 4 下面只有一个叶子节点，那么对应的高度就是 2；
-
节点 7 也是一个叶子节点，所以它的高度值也是 1；
-
但是对于节点 5 来说它有左右两棵子树，左边的子树高度为 2，右边的子树高度为 1，
-
相应的节点 5 这个节点它的高度就是左右两棵子树中最高的那棵树再加上自身的 1，
-
那么这样一来节点 5 它的高度就是 2+1=3；非常好理解，节点 11 它的高度就是 1，
-
其它的如此类推，如下图的标注所示。
// 节点名称加高度 小括号中的是节点名称，中括号中的是高度值// 【5】(12)// / \// 【4】(8) (18)【2】// / \ /// 【3】(5) 【1】(11) (17)【1】// / \// 【2】(4) (7)【1】// /// 【1】(2)//复制代码
-
平衡因子
-
对整棵树每一个节点都标注上高度值之后，
-
相应的计算一个称之为平衡因子的这样的一个数，
-
这个名词虽然听起来比较复杂，实际上非常的简单，
-
它就是指对于每一个节点而言，它的左右子树的高度差，
-
计算高度值的差可以使用左子树的高度减去右子树的高度差。
-
对于节点 2 来说它是要给叶子节点，
-
它的左右两棵子树相当于是两棵空树，空树的高度值可以记为 0，
-
相应的叶子节点的平衡因子其实就是
0 - 0 = 0，最后的结果也为 0； -
对于节点 4 来说它的左子树对应的高度值为 1，右子树为空所对应的高度值为 0，
-
那么它的平衡因子就是
1 - 0 = 1，最后的结果为 1； -
节点 7 是个叶子节点，那么它的平衡因子就是 0；
-
节点 5 两棵子树的高度差是
2 - 1 = 1，最终的结果为 1； -
节点 11 是叶子节点，所以他的平衡因子为 0；
-
节点 8 的两棵子树的高度查实
3 - 1 = 2，最终的结果为 2。 -
这就意味着节点 8 这个左右子树的高度差已经超过了一，
-
通过这个平衡因子就可以看出来这棵树已经不是一棵平衡二叉树了，
-
如下图这样标注出平衡因子之后，
-
一旦在一棵树中有一个节点它的平衡因子是大于等于 2 或者小于等于-2 的，
-
换句话说它的绝对值是等于 2，那么整棵树就不再是一棵平衡二叉树了。
-
如下图所示，节点 12 和节点 8 的平衡因子的绝对值都是 2，
-
那么就说明这两个节点破坏了平衡二叉树对应的那个性质，
-
这个对应的性质就是 左右子树的高度差超过了一，
-
一旦可以计算出每一个节点的平衡因子，
-
相应的也可以看出来当前的这棵树是否是一棵平衡二叉树，
-
不仅如此在后续的 AVL 实现中也会借助每一个节点
-
它对应的平衡因子来决定是否要进行一些特殊的操作，
-
从而来维持整棵树是否是一棵平衡二叉树。
// 1. 节点名称 加高度值 加平衡因子值// 1. 小括号中的是节点名称，// 2. 中括号中的是高度值，// 3. 大括号中的是平衡因子//// 2. 平衡因子值 = 左右子树的高度差// 3. 左右子树的高度差 = 左子树的高度值 - 右子树的高度值// {2}【5】(12)// / \// {2}【4】(8) (18)【2】{1}// / \ /// {1}【3】(5) {0}【1】(11)(17)【1】{0}// / \// {1}【2】(4) (7)【1】{1}// /// {0}【1】(2)//复制代码 -
通过对每一个节点标注相应的高度
-
然后通过这个高度非常简单的计算出平衡因子，
-
最后在通过平衡因子来决定是否进行一些特殊的操作，
-
从而维持整棵树是一棵平衡二叉树的性质。
计算节点的高度和平衡因子
- 对原先实现的二分搜索树的代码进行修改
- 让它可以记录每一个节点的高度值，
- 同时来处理来计算这个平衡因子。
- AVL 树整体的框架和二分搜索树映射版相似。
- 所以 MyBSTMap 中的代码可以拿过来修改一下，
- 整体 AVL 树就是在二分搜索树代码的基础上补充一些代码，
- 其实就是添加上自平衡的机制，
- 使得原先实现的二分搜索树在对节点进行操作的时候可以保证整棵树是平衡的，
- 这里平衡的定义就是对于每一个节点左右子树的高度差不超过一。
- 在 AVLTree 中进行修改
- 在 AVLTree 的 Node 中添加一个新属性 height，
- 同时要对这个新的成员变量进行维护，也就是新增一个 getHeight 方法，
- 传入一个节点然后返回这个节点对应的高度值；
- 添加方法中，每添加一个节点，无论是在左子树中进行添加，
- 还是在右子树中进行添加，添加完了这个节点之后，
- 对于当前的这个 node 来说它的 height 都有可能会发生变化，
- 这是因为对于当前的 node 来说不管是左子树还是右子树来说，
- 多了一个节点之后，相应的它自身的高度就有可能发生变化，
- 所以需要对当前的这个 node 的 height 进行一个更新，
- 也就是 1 + 左右子树中 height 值最大的那个 height 值，
- 也就是当前节点的 height 等于自己左右子树中最大的那个高度值；
- 更新了节点的高度值之后，就可以计算平衡因子了，
- 也就是当前节点的左子树的高度减去当前右子树的高度，
- 取高度的差的绝对值，如果大于 1，那么就说明不符合 AVL 平衡二叉树的性质了。
- 通过对不符合要求的平衡因子值后，你会发现二分搜索树中不符合要求的节点非常多，
- 虽然在之前的测试中二分搜索树的性能已经很好了，但是在随机性的角度出发，
- 不符合要求的平衡因子也是非常多的，也就是说还是会出现高度的不平衡的，
- 所以也就是说还是有很大的优化空间的。
代码示例
-
AVLTree
// 自定义AVL树节点 AVLTreeNodeclass MyAVLTreeNode { constructor(key = null, value = null, left = null, right = null) { this.key = key; this.value = value; this.left = left; this.right = right; this.height = 1; } // @Override toString 2018-11-24-jwl toString() { return this.key + '--->' + this.value + '--->' + this.height; }}// 自定义AVL树 AVLTreeclass MyAVLTree { constructor() { this.root = null; this.size = 0; } // 比较的功能 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; } // 获取某个节点的高度 - getHeight(node) { // 节点为空 返回0 if (!node) return 0; // 直接返回这个节点的高度 return node.height; } // 获取一个节点的平衡因子 - getBalanceFactor(node) { // 节点为空 返回0 if (!node) return 0; // 左右子树的高度值 const leftHeight = this.getHeight(node.left); const rightHeight = this.getHeight(node.right); // 左子树的高度 - 右子树高度的值 = 平衡因子 return leftHeight - rightHeight; } // 根据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); } // 添加操作 递归算法 - recursiveAdd(node, key, value) { // 解决最简单的问题 if (node === null) { this.size++; return new MyAVLTreeNode(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; // 在这里对节点的高度进行重新计算 节点本身高度为1 // 计算方式： 1 + 左右子树的height值最大的那个height值 node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right)); // 计算一个节点的平衡因子 const balanceFactor = this.getBalanceFactor(node); // 如果平衡因子的绝对值大于1 说明不满足AVL平衡二叉树的性质了 if (Math.abs(balanceFactor) > 1) { console.log( node.toString() + ' unbalanced : ' + balanceFactor + '\r\n' ); document.body.innerHTML += node.toString() + ' unbalanced : ' + balanceFactor + ''; } 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; }}复制代码 -
Main
// main 函数class Main { constructor() { this.alterLine('AVLTree Area'); // 千级别 const openCount = 100; // 操作数 const rank = 10000000; // 生成同一份测试数据的辅助代码 const random = Math.random; const array = new Array(openCount); // 生成同一份测试数据 for (var i = 0; i < openCount; i++) array[i] = Math.floor(random() * rank); // 创建AVL树实例 const avl = new MyAVLTree(); for (const value of array) avl.add(value); } // 将内容显示在页面上 show(content) { document.body.innerHTML += `${content}`; } // 展示分割线 alterLine(title) { let line = `--------------------${title}----------------------`; console.log(line); document.body.innerHTML += `${line}`; }}// 页面加载完毕window.onload = function() { // 执行主函数 new Main();};复制代码
检查二分搜索树性能和平衡性
- 自己实现的二分搜索树不符合要求 AVL 平衡二叉树性质的节点非常多，
- 所以会出现高度的不平衡，也就说明了有很大的优化空间，
- 这个优化空间就是，让自己实现的 AVL 树可以维持自平衡。
- 改进的方式和原理
- 需要对节点进行一下判断，
- 是不是二分搜索树同时是不是平衡二叉树，
- 对于 AVL 树来说它是对二分搜索树的一个改进，
- 改进的地方是二分搜索树有可能会退化为一个链表的这种情况，
- 因为就引入了平衡因子这个概念，
- AVL 树要保持对于每一个节点来说左右子树的高度差不能超过一，
- 但是在这种情况下要注意，AVL 树同时也是一个二分搜索树，
- 所以它也要满足二分搜索树的性质，也就是对于每一个节点来说，
- 左子树所有的节点都要小于这个节点的值，右子树所有的节点都要大于这个节点的值，
- 也就是说它的左右子树依然是二分搜索树，那么在添加 AVL 树自平衡的机制的时候，
- 如果你的代码有问题的话很有可能会打破这个性质，所以可以设置一个函数，
- 能够方便的检查当前的这棵 AVL 树它是不是依然可以保证它是一个棵二分搜索树。
- 通过二分搜索树的顺序性，也就是中序遍历，然后将结果存到一个动态数组中，
- 数组中的元素会是从小到大升序的排列，
- 以循环的方式检查这个数组中前一个元素值是否比当前元素值小，
- 如果符合要求就证明这就是一棵二分搜索树，
- 否则就不是，通过返回相应的判断值即可。
- 除了要判断这棵树是否是一棵二分搜索树之外，还要判断这棵树是不是一棵平衡二叉树，
- AVL 平衡二叉树的定义是，对于每一个节点的左右子树的高度差不能超过一，
- 这个定义是一个递归的定义，需要从根节点开始判断它的左右子树的高度差不能超过一，
- 然后再去看它的左右子树的根节点是否同样满足这个条件，
- 所以需要又要写一个递归辅助函数，这个辅助函数是以前序遍历的方式
- 判断当前节点的及其左右子树是否符合平衡二叉树的定义，
- 如果全部符合返回 true，否则就返回 false。
- 当你对 AVL 树进行相应的操作之后依然可以维持二分搜索树和平衡二叉树的性质
- 以上的操作都是准备工作，只有满足这样的两种性质才能算是 AVL 树。
代码示例
-
AVLTree
// 自定义AVL树节点 AVLTreeNodeclass MyAVLTreeNode { constructor(key = null, value = null, left = null, right = null) { this.key = key; this.value = value; this.left = left; this.right = right; this.height = 1; } // @Override toString 2018-11-24-jwl toString() { return this.key + '--->' + this.value + '--->' + this.height; }}// 自定义AVL树 AVLTreeclass MyAVLTree { constructor() { this.root = null; this.size = 0; } // 比较的功能 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; } // 获取某个节点的高度 - getHeight(node) { // 节点为空 返回0 if (!node) return 0; // 直接返回这个节点的高度 return node.height; } // 获取一个节点的平衡因子 - getBalanceFactor(node) { // 节点为空 返回0 if (!node) return 0; // 左右子树的高度值 const leftHeight = this.getHeight(node.left); const rightHeight = this.getHeight(node.right); // 左子树的高度 - 右子树高度的值 = 平衡因子 return leftHeight - rightHeight; } // 根据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); } // 添加操作 递归算法 - recursiveAdd(node, key, value) { // 解决最简单的问题 if (node === null) { this.size++; return new MyAVLTreeNode(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; // 在这里对节点的高度进行重新计算 节点本身高度为1 // 计算方式： 1 + 左右子树的height值最大的那个height值 node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right)); // // 计算一个节点的平衡因子 // const balanceFactor = this.getBalanceFactor(node); // // 如果平衡因子的绝对值大于1 说明不满足AVL平衡二叉树的性质了 // if (Math.abs(balanceFactor) > 1) { // console.log(node.toString() + " unbalanced : " + balanceFactor + "\r\n"); // document.body.innerHTML += node.toString() + " unbalanced : " + balanceFactor + ""; // } 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; } // 判断当前这棵树是否是一棵二分搜索树，有二分搜索树顺序性 isBanarySearchTree() { // 如果节点为空 那么这就是一棵空的二分搜索树 if (!this.root) return true; // 存储二分搜索树中的key const list = new Array(); // 中序遍历后，添加到list中的值会是以从小到大升序的样子排列 this.inOrder(this.root, list); // 从前往后判断 list中的值是否是从小到大升序的排列 // 验证 当前树是否符合二分搜索树的性质 for (var i = 1; i < list.length; i++) if (list[i - 1] > list[i]) return false; return true; } // 中序遍历 辅助函数 - inOrder(node, list) { // 递归到底的情况 if (!node) return; // 中序遍历时，添加到数组中的值会是以从小到大升序的样子排列 this.inOrder(node.left, list); list.push(node.key); this.inOrder(node.right, list); } // 判断该二叉树是否一棵平衡二叉树 isBalanced() { return this.recursiveIsBalanced(this.root); } // 递归判断某一个节点是否符合平衡二叉树的定义 辅助函数 - recursiveIsBalanced(node) { // 能够递归到底，说明符合要求 // 空的节点左右孩子高度差肯定为0， // 因为空树没有左右子树，更加谈不上下面去判断它的左右子树高度差是否会超过一。 if (!node) return true; // 如果当前节点的高度差大于1 说明不符合要求 if (Math.abs(this.getBalanceFactor(node)) > 1) return false; // 递归的去判断当前节点的 左右子树是否符合要求 return ( this.recursiveIsBalanced(node.left) && this.recursiveIsBalanced(node.right) ); } // @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; }}复制代码 -
Main
// main 函数class Main { constructor() { this.alterLine('AVLTree Area'); // 千级别 const openCount = 100; // 操作数 const rank = 10000000; // 生成同一份测试数据的辅助代码 const random = Math.random; const array = new Array(openCount); // 生成同一份测试数据 for (var i = 0; i < openCount; i++) array[i] = Math.floor(random() * rank); // 创建AVL树实例 const avl = new MyAVLTree(); for (const value of array) avl.add(value); // 输出当前这棵avl树是否是一个二分搜索树 this.show('Is Binary Search Tree : ' + avl.isBanarySearchTree()); console.log('Is Binary Search Tree : ' + avl.isBanarySearchTree()); // 输出当前这棵avl树是否是一个平衡二叉树 this.show('Is Balanced : ' + avl.isBalanced()); console.log('Is Balanced : ' + avl.isBalanced()); } // 将内容显示在页面上 show(content) { document.body.innerHTML += `${content}`; } // 展示分割线 alterLine(title) { let line = `--------------------${title}----------------------`; console.log(line); document.body.innerHTML += `${line}`; }}// 页面加载完毕window.onload = function() { // 执行主函数 new Main();};复制代码
AVL 树 旋转基本原理
-
AVL 树是通过两个主要的机制来实现自平衡的
- 左旋转和右旋转
-
AVL 树维护自平衡在什么时候发生
- 在二分搜索树中如果想要插入一个节点，
- 必须从根节点开始一路寻找到这个节点正确的插入位置，
- 只有在你新添加一个节点才有可能导致整棵二分搜索树不再满足平衡性，
- 相应的这个不平衡的节点只有可能发生在插入的这个位置一直到其父祖节点这些节点中，
- 这是因为是插入了这个节点之后才破坏了整棵树的平衡性，
- 破环的这个平衡性会反应到这个节点相应的父亲节点或者祖先节点上，
- 因为新插入了这个节点之后，
- 它的父亲节点或者祖先节点相应的左右子树的高度值就需要进行更新，
- 在更新之后，有可能平衡因子就会
大于1或者小于-1， - 也就是左右子树的高度差超过了一，
- 所以维护平衡的时机应该是加入节点之后，沿着这个节点向上去回溯来维护这个平衡性，
- 因为这个整体代码是一个递归代码，
- 所以沿着这个节点向上维护平衡性本身也是非常容易的，
- 在 add 方法中显示递归到底的代码块儿，然后是选择插入节点的位置进行递归调用，
- 最后是更新节点的高度以及计算平衡因子，
- 计算出平衡因子之后就可以开始维护这个平衡性等一些特殊的操作，
- 维护完平衡性之后对应的 node 进行返回，返回给递归调用的上一层，
- 这就是一个回溯的过程，对每一个节点都维护一下平衡性，
- 维护完平衡性之后，到递归的上一层，也就是看当前处理的这个节点相应的它的父亲节点，
- 在递归的上一层如果发现它的平衡因子依然不满足要求，也就是大于一或者小于负一，
- 然后再在这里维护平衡性，维护以后再将相应的根节点返回给上一层，依次类推，
- 这里就是维护二分搜索树的平衡性相应的时机所在的这个位置，
- 可以使用宏观的角度去理解一下整个添加节点的递归函数在做什么，
- 然后可以再从微观的角度可以使用一些相对小的数据集来看一下这个具体的执行过程。
-
AVL 树维护平衡性的原理
- 假如当前这棵树为空，在这种情况下先添加一个节点，这个节点叫节点 12，
- 此时对这个节点来说，它的平衡因子就是 0，
- 在这个节点的基础上再添加一个元素，这个节点叫做节点 8，
- 因为节点 8 比节点 12 小，所以就在这个节点 12 的左子树上，
- 现在节点 8 的平衡因子就变成了 0，相应的节点 12 这个节点它对应的平衡因子就变成了 1。
- 这个平衡因子更新的过程就是在模拟程序执行的过程，
- 添加这个节点 8 的时候在节点 12 的左子树中添加这个新的节点，
- 一个新的节点，它的平衡因子默认就为 0，之后由于新添加了一个节点，
- 这个新的节点它的祖辈节点相应的平衡因子就会发生改变，
- 所以就回到了节点 12 更新了它的平衡因子，所以节点 12 的平衡因子变成了 1。
- 然后再在这棵树中添加一个节点 5，由于 5 比 8 要小，
- 所以它会一路下来最终成为节点 8 的左子树，此时节点 5 是一个叶子节点，
- 它的平衡因子为 0，那么回到父节点 8 这里，由于节点 8 的左子树多了一个节点，
- 它的平衡因子就变成了 1，那么在回到节点 12 这里，节点 12 的平衡因子相应的也要更新，
- 此时就变为了 2，那么在节点 12 上，它的平衡因子的绝对值已经大于了 1，
- 所以就需要对它进行一个平衡的维护，
- 那么这就是对于一个节点它的平衡性被打破的一个最一般的情况，
- 也就是添加节点是不停的向一侧添加，形成了一条链表的形状，
- 显然它会不平衡，这样的一种情况不仅仅可能出现在初始的情况，
- 还有可能出现在对一个非空的树进行节点添加的情况，
- 其实都是插入的元素在不平衡的节点的左侧的左侧，
- 换句话说，就是一直在向整棵树的左侧添加元素，最终导致父祖辈节点的平衡因子大于一，
- 也就是左子树的高度比右子树的高度要高，而且高出来的幅度是比一还要大的，
- 与此同时这个不平衡节点的左子树它的平衡因子也是大于 0 的，
- 换句话来说，对于这个不平衡节点的左子树的高度也是大于右子树的，
- 也就是插入的元素是在最终形成不平衡节点的左侧的左侧，
- 那么它就会满足不符合 AVL 树性质的样子，此时就可以进行平衡的维护。
- 添加每一个节点之后，就会更新这个节点的高度值，同时计算出这个节点的平衡因子，
- 这个平衡因子就有可能打破平衡二叉树的条件，也就是平衡因子的绝对值大于一，
- 所以就需要在下面进行平衡的维护。
-
右旋转操作
- 在上面分析的情况中，如果这个节点的平衡因子比一还要大，
- 也就是左子树比右子树的高度差是超过了一的，并且是左边要高的，
- 与此同时再来看一下当前这个节点的左子树的平衡因子，
- 如果左子树的平衡因子对应的是大于等于 0 的，
- 在这种情况下也就是说明了当前这个节点不平衡的原因，
- 是在于它的左侧的左侧多添加了一个节点，所以要针对这种情况进行一个平衡的维护，
- 那么这种平衡的维护操作叫做右旋转，
- 先取出当前节点的左子树的右子树进行保存，
- 然后让当前节点变成当前节点的左子树的右子树，
- 最后让当前节点的左子树变成之前保存的右子树，
- 那么最开始的当前节点左子树就变成了新的二叉树的根节点，
- 这样的一个过程就叫做右旋转，
- 这个过程其实相当于最开始的当前节点顺时针的转到了
- 当前节点的左子树的右子树的位置，
- 从当前节点的左子树的角度看就是当前节点顺时针的向右进行了一个旋转，
- 此时得到的这棵新的二叉树即满足二分搜索树的性质，
- 又满足平衡二叉树的性质，如下图，承载的元素是一致的。
// 最开始这棵树是这种情况 T1 < Z < T2 < X < T3 < Y < T4// (Y)// / \// (X) (T4)// / \// (Z) (T3)// / \// (T1) (T2)// 右旋转后是这样子，依然是T1 < Z < T2 < X < T3 < Y < T4// (X)// / \// (Z) (Y)// / \ / \// (T1) (T2)(T3)(T4)复制代码
代码示例
- AVLTree
// 自定义AVL树节点 AVLTreeNodeclass MyAVLTreeNode { constructor(key = null, value = null, left = null, right = null) { this.key = key; this.value = value; this.left = left; this.right = right; this.height = 1; } // @Override toString 2018-11-24-jwl toString() { return this.key + '--->' + this.value + '--->' + this.height; }}// 自定义AVL树 AVLTreeclass MyAVLTree { constructor() { this.root = null; this.size = 0; } // 比较的功能 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; } // 获取某个节点的高度 - getHeight(node) { // 节点为空 返回0 if (!node) return 0; // 直接返回这个节点的高度 return node.height; } // 获取一个节点的平衡因子 - getBalanceFactor(node) { // 节点为空 返回0 if (!node) return 0; // 左右子树的高度值 const leftHeight = this.getHeight(node.left); const rightHeight = this.getHeight(node.right); // 左子树的高度 - 右子树高度的值 = 平衡因子 return leftHeight - rightHeight; } // 根据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); } // 添加操作 递归算法 - recursiveAdd(node, key, value) { // 解决最简单的问题 if (node === null) { this.size++; return new MyAVLTreeNode(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; // 在这里对节点的高度进行重新计算 节点本身高度为1 // 计算方式： 1 + 左右子树的height值最大的那个height值 node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right)); // 计算一个节点的平衡因子 const balanceFactor = this.getBalanceFactor(node); // 平衡维护 右旋转操作 平衡因子为正数则表示左倾 反之为右倾 if (balanceFactor > 1 && this.getBalanceFactor(node.left) >= 0) { } // // 如果平衡因子的绝对值大于1 说明不满足AVL平衡二叉树的性质了 // if (Math.abs(balanceFactor) > 1) { // console.log(node.toString() + " unbalanced : " + balanceFactor + "\r\n"); // document.body.innerHTML += node.toString() + " unbalanced : " + balanceFactor + ""; // } 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; } // 判断当前这棵树是否是一棵二分搜索树，有二分搜索树顺序性 isBanarySearchTree() { // 如果节点为空 那么这就是一棵空的二分搜索树 if (!this.root) return true; // 存储二分搜索树中的key const list = new Array(); // 中序遍历后，添加到list中的值会是以从小到大升序的样子排列 this.inOrder(this.root, list); // 从前往后判断 list中的值是否是从小到大升序的排列 // 验证 当前树是否符合二分搜索树的性质 for (var i = 1; i < list.length; i++) if (list[i - 1] > list[i]) return false; return true; } // 中序遍历 辅助函数 - inOrder(node, list) { // 递归到底的情况 if (!node) return; // 中序遍历时，添加到数组中的值会是以从小到大升序的样子排列 this.inOrder(node.left, list); list.push(node.key); this.inOrder(node.right, list); } // 判断该二叉树是否一棵平衡二叉树 isBalanced() { return this.recursiveIsBalanced(this.root); } // 递归判断某一个节点是否符合平衡二叉树的定义 辅助函数 - recursiveIsBalanced(node) { // 能够递归到底，说明符合要求 // 空的节点左右孩子高度差肯定为0， // 因为空树没有左右子树，更加谈不上下面去判断它的左右子树高度差是否会超过一。 if (!node) return true; // 如果当前节点的高度差大于1 说明不符合要求 if (Math.abs(this.getBalanceFactor(node)) > 1) return false; // 递归的去判断当前节点的 左右子树是否符合要求 return ( this.recursiveIsBalanced(node.left) && this.recursiveIsBalanced(node.right) ); } // @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; }}复制代码 - Main
// main 函数class Main { constructor() { this.alterLine('AVLTree Area'); // 千级别 const openCount = 100; // 操作数 const rank = 10000000; // 生成同一份测试数据的辅助代码 const random = Math.random; const array = new Array(openCount); // 生成同一份测试数据 for (var i = 0; i < openCount; i++) array[i] = Math.floor(random() * rank); // 创建AVL树实例 const avl = new MyAVLTree(); for (const value of array) avl.add(value); // 输出当前这棵avl树是否是一个二分搜索树 this.show('Is Binary Search Tree : ' + avl.isBanarySearchTree()); console.log('Is Binary Search Tree : ' + avl.isBanarySearchTree()); // 输出当前这棵avl树是否是一个平衡二叉树 this.show('Is Balanced : ' + avl.isBalanced()); console.log('Is Balanced : ' + avl.isBalanced()); } // 将内容显示在页面上 show(content) { document.body.innerHTML += `${content}`; } // 展示分割线 alterLine(title) { let line = `--------------------${title}----------------------`; console.log(line); document.body.innerHTML += `${line}`; }}// 页面加载完毕window.onload = function() { // 执行主函数 new Main();};复制代码 AVL 树 左旋转和右旋转的实现
-
右旋转
- 先取出当前节点的左子树的右子树进行保存，
- 然后让当前节点变成当前节点的左子树的右子树，
- 最后让当前节点的左子树变成之前保存的右子树，
- 那么最开始的当前节点左子树就变成了新的二叉树的根节点，
- 这样的一个过程就叫做右旋转。
- 右旋转是当前节点的平衡因子大于正一并且
- 左子树的平衡因子大于等于 0 的时候才进行的特殊操作，
- 右旋转之后要更新一下对应节点的高度值，只需要更新 x 和 y 的高度值即可，
- 重新计算一下 x 和 y 的左右子树的最大高度值然后+1 即可。
// 对节点y进行向右旋转操作，返回旋转后新的根节点x// y x// / \ / \// x T4 向右旋转 (y) z y// / \ - - - - - - - -> / \ / \// z T3 T1 T2 T3 T4// / \// T1 T2复制代码
-
左旋转
- 与右旋转对应的是左旋转，
- 右旋转是插入的元素在不平衡的节点的左侧的左侧，
- 而左旋转是插入的元素在不平衡的节点的右侧的右侧，
- 左旋转和右旋转是一个左右对称的情况，
- 也就是当前节点的右子树的高度值比左子树的高度值相差大于一，
- 换句话说就是左子树的高度值减去右子树的高度值小于了负一，
- 在这种情况下就需要进行左旋转，
- 先将当前节点的右子树的左子树保存起来，
- 然后让当前节点的右子树的左子树等于当前节点，
- 最后让当前节点的右子树等于之前保存的左子树，
- 这个过程就是左旋转，最终得到的二叉树一样即满足而二分搜索树的性质，
- 同时也满足了平衡二叉树的性质。
- 左旋转和右旋转是一个完全对称的关系。
- 左旋转是 当前节点的平衡因子小于负一并且
- 右子树的平衡因子小于等于 0 的时候才进行的特殊操作，
- 也就是整棵树整体上是向右进行倾斜的，
- 左旋转之后要更新一下对应节点的高度值，只需要更新 x 和 y 的高度值即可，
- 重新计算一下 x 和 y 的左右子树的最大高度值然后+1 即可。
// 最开始这棵树是这种情况 T4 < Y < T3 < X < T1 < Z < T2// (Y)// / \// (T4) (X)// / \// (T3) (Z)// / \// (T1) (T2)// 左旋转后是这样子，依然是T4 < Y < T3 < X < T1 < Z < T2// (X)// / \// (Y) (Z)// / \ / \// (T4)(T3)(T1)(T2)复制代码
-
无论是左旋转还是右旋转都是一种情况
- 就是以当前节点为根的向一侧偏斜，
- 不过是向左偏斜还是向右偏斜对应了是使用左旋转还是右旋转，
- 向左偏斜就向右旋转，向右偏斜就向左旋转。
-
使用了左旋转和右旋转来进行平衡性的维护之后
- 其实还有另外两种情况需要考虑，
- 只有这样才能够将所有的节点的平衡因子的绝对值小于等于一。
代码示例
-
AVLTree
// 自定义AVL树节点 AVLTreeNodeclass MyAVLTreeNode { constructor(key = null, value = null, left = null, right = null) { this.key = key; this.value = value; this.left = left; this.right = right; this.height = 1; } // @Override toString 2018-11-24-jwl toString() { return this.key + '--->' + this.value + '--->' + this.height; }}// 自定义AVL树 AVLTreeclass MyAVLTree { constructor() { this.root = null; this.size = 0; } // 比较的功能 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; } // 获取某个节点的高度 - getHeight(node) { // 节点为空 返回0 if (!node) return 0; // 直接返回这个节点的高度 return node.height; } // 获取一个节点的平衡因子 - getBalanceFactor(node) { // 节点为空 返回0 if (!node) return 0; // 左右子树的高度值 const leftHeight = this.getHeight(node.left); const rightHeight = this.getHeight(node.right); // 左子树的高度 - 右子树高度的值 = 平衡因子 return leftHeight - rightHeight; } // 根据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; } } // 对节点y进行向右旋转操作，返回旋转后新的根节点x // y x // / \ / \ // x T4 向右旋转 (y) z y // / \ - - - - - - - -> / \ / \ // z T3 T1 T2 T3 T4 // / \ // T1 T2 rightRotate(y) { const x = y.left; const T3 = x.right; // 向右旋转的过程 y.left = T3; x.right = y; // 更新节点的height值 只需要更新x和y的即可 y.height = 1 + Math.max(this.getHeight(y.left), this.getHeight(y.right)); x.height = 1 + Math.max(this.getHeight(x.left), this.getHeight(x.right)); // 返回 新节点 x return x; } // 对节点y进行向左旋转操作，返回旋转后新的根节点x // y x // / \ / \ // T1 x 向左旋转 (y) y z // / \ - - - - - - - -> / \ / \ // T2 z T1 T2 T3 T4 // / \ // T3 T4 leftRotate(y) { const x = y.right; const T2 = x.left; // 向左旋转的过程 y.right = T2; x.left = y; // 更新节点的height值 只需要更新x和y的即可 y.height = 1 + Math.max(this.getHeight(y.left), this.getHeight(y.right)); x.height = 1 + Math.max(this.getHeight(x.left), this.getHeight(x.right)); // 返回 新节点 x return x; } // 添加操作 + add(key, value) { this.root = this.recursiveAdd(this.root, key, value); } // 添加操作 递归算法 - recursiveAdd(node, key, value) { // 解决最简单的问题 if (node === null) { this.size++; return new MyAVLTreeNode(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; // 在这里对节点的高度进行重新计算 节点本身高度为1 // 计算方式： 1 + 左右子树的height值最大的那个height值 node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right)); // 计算一个节点的平衡因子 const balanceFactor = this.getBalanceFactor(node); // 如果平衡因子的绝对值大于1 说明不满足AVL平衡二叉树的性质了 if (Math.abs(balanceFactor) > 1) { console.log( node.toString() + ' unbalanced : ' + balanceFactor + '\r\n' ); document.body.innerHTML += node.toString() + ' unbalanced : ' + balanceFactor + ''; } // 平衡维护 右旋转操作 平衡因子为正数则表示左倾 反之为右倾 if (balanceFactor > 1 && this.getBalanceFactor(node.left) >= 0) return this.rightRotate(node); // 平衡维护 右旋转操作 平衡因子为负数则表示右倾 反之为左倾 if (balanceFactor < -1 && this.getBalanceFactor(node.left) <= 0) return this.leftRotate(node); 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; } // 判断当前这棵树是否是一棵二分搜索树，有二分搜索树顺序性 isBanarySearchTree() { // 如果节点为空 那么这就是一棵空的二分搜索树 if (!this.root) return true; // 存储二分搜索树中的key const list = new Array(); // 中序遍历后，添加到list中的值会是以从小到大升序的样子排列 this.inOrder(this.root, list); // 从前往后判断 list中的值是否是从小到大升序的排列 // 验证 当前树是否符合二分搜索树的性质 for (var i = 1; i < list.length; i++) if (list[i - 1] > list[i]) return false; return true; } // 中序遍历 辅助函数 - inOrder(node, list) { // 递归到底的情况 if (!node) return; // 中序遍历时，添加到数组中的值会是以从小到大升序的样子排列 this.inOrder(node.left, list); list.push(node.key); this.inOrder(node.right, list); } // 判断该二叉树是否一棵平衡二叉树 isBalanced() { return this.recursiveIsBalanced(this.root); } // 递归判断某一个节点是否符合平衡二叉树的定义 辅助函数 - recursiveIsBalanced(node) { // 能够递归到底，说明符合要求 // 空的节点左右孩子高度差肯定为0， // 因为空树没有左右子树，更加谈不上下面去判断它的左右子树高度差是否会超过一。 if (!node) return true; // 如果当前节点的高度差大于1 说明不符合要求 if (Math.abs(this.getBalanceFactor(node)) > 1) return false; // 递归的去判断当前节点的 左右子树是否符合要求 return ( this.recursiveIsBalanced(node.left) && this.recursiveIsBalanced(node.right) ); } // @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; }}复制代码 -
Main
// main 函数class Main { constructor() { this.alterLine('AVLTree Area'); // 千级别 const openCount = 100; // 操作数 const rank = 10000000; // 生成同一份测试数据的辅助代码 const random = Math.random; const array = new Array(openCount); // 生成同一份测试数据 for (var i = 0; i < openCount; i++) array[i] = Math.floor(random() * rank); // 创建AVL树实例 const avl = new MyAVLTree(); for (const value of array) avl.add(value); // 输出当前这棵avl树是否是一个二分搜索树 this.show('Is Binary Search Tree : ' + avl.isBanarySearchTree()); console.log('Is Binary Search Tree : ' + avl.isBanarySearchTree()); // 输出当前这棵avl树是否是一个平衡二叉树 this.show('Is Balanced : ' + avl.isBalanced()); console.log('Is Balanced : ' + avl.isBalanced()); } // 将内容显示在页面上 show(content) { document.body.innerHTML += `${content}`; } // 展示分割线 alterLine(title) { let line = `--------------------${title}----------------------`; console.log(line); document.body.innerHTML += `${line}`; }}// 页面加载完毕window.onload = function() { // 执行主函数 new Main();};复制代码