树结构的经典问题之自平衡树
BST树存在一个问题：取决于你添加的节点数，树的一条边可能会非常深；也就是说，树的一条分支会有很多层，而其他的分支却只有几层，如下图所示
这样，在需要在某条边上添加、移除和搜索某个节点的时候，会引起一些性能问题。
为了解决这个问题，有一种树叫作Adelson-Velskii-Landi 树（AVL 树）。
AVL树是一种自平衡二叉搜索树，意思是任何一个节点左右两侧子树的高度之差最多为1。
理清基本概念
节点的高度
如上图所示：
根节点3的左侧除了一个子节点2再也没有其他子节点，而节点2本身也是叶节点，所以左侧子树的高度就为0；
根节点3的右侧有一个子节点6，子节点6下方左右两侧都有子节点，其左侧子节点5下方还有一个叶节点4，所以节点4的高度是0，节点5的高度是1；
节点6的右侧有一个子节点7，而节点7下面也没有其他子节点，所以节点7也是叶节点，所以节点7的高度也是0；
节点6作为节点5和节点7的父节点，它的高度要以左右两侧中最高的一方为准，所以节点6的高度要在节点5的高度1之上再加1，即节点6的高度为2；
而根节点3又作为节点2和节点6的父节点，节点3的高度也要以左右两侧中最高的一方为准，所以根节点3的高度要在节点6的高度2之上再加1，即根节点3的高度为3。
平衡因子
在AVL树中，需要对每个节点计算右子树高度（hr）和左子树高度（hl）之间的差值，该值（hr-hl）应为0、1或-1，如下图所示：
如果结果不是这三个值之一，则需要平衡该AVL树。这就是平衡因子的概念。
平衡操作
在对AVL树添加或移除节点后，要计算并验证树是否需要进行平衡。向AVL树插入节点时，可以执行单旋转或者双旋转两中平衡操作，分别对应四种场景：
场景一：
左左（LL）：向右的单旋转
此时又可细分为两种情况：
情况1：
节点的左侧子节点的右下方没有子节点且左侧偏重，如下图所示：
根节点3的左侧子节点2的左侧有子节点1，节点2的右侧没有子节点，此时只需要将节点2作为新的根节点，节点3变成新的根节点2的右侧子节点即可保持平衡
情况2：
节点的左侧子节点的左侧偏重，且左侧子节点的右侧有子节点，如下图所示：
根节点50的左侧子树30偏重，且左侧子树30的左侧子节点10的左下方也有子节点5，而左侧子树30的右侧子节点40没有子节点，自己就是叶节点。此时需要平衡的话：
第一步，先将左侧子树30与根节点50分离，如下图所示：
第二步，将节点30下方的右侧子节点40抽离出来，移植到节点50的左侧，成为节点50的左侧子节点，如下图所示：
第三步，将节点50这一系，整体移植到节点30右侧，成为节点30的右侧子树，这样就完成了平衡，如下图所示：
综上所述，LL使用场景为：节点的左侧子节点的高度大于右侧子节点的高度时，并且左侧子节点也是平衡或者左侧较重的情况。
场景二：
右右（RR）：向左的单旋转
此时又可细分为两种情况：
情况1：
节点的右侧子节点的左下方没有子节点且右侧偏重，如下图所示：
根节点1的右侧子节点2的右侧有子节点3，节点2的左侧没有子节点，此时只需要将节点2作为新的根节点，节点1变成新的根节点2的左侧子节点即可保持平衡
情况2：
节点的右侧子节点的右侧偏重，且右侧子节点的左侧有子节点，如下图所示：
根节点50的右侧子树70偏重，且右侧子树70的右侧子节点80的右下方也有子节点90，而右侧子树70的左侧子节点60没有子节点，自己就是叶节点。此时需要平衡的话：
第一步，先将右侧子树70与根节点50分离，如下图所示：
第二步，将节点70下方的左侧子节点60抽离出来，移植到节点50的右侧，成为节点50的右侧子节点，如下图所示：
第三步，将节点50这一系，整体移植到节点70左侧，成为节点70的左侧子树，这样就完成了平衡，如下图所示：
综上所述，RR使用场景为：节点的右侧子节点的高度大于左侧子节点的高度时，并且右侧子节点也是平衡或者右侧较重的情况。
场景三：
左右（LR）：向右的双旋转（先LL向右的单旋转，再RR向左的单旋转）
此时又可细分为两种情况：
情况1：
节点的左偏重，左侧子节点的右侧子节点是平衡的，如下图所示：
根节点3的左侧偏重，且左侧子节点1的右侧偏重，左侧子节点1的右侧子节点2下方没有子节点，所以节点2下方是平衡的，但是节点3、1、2整体是不平衡的，此时需要保持平衡的话：
第一步，先将节点2从原来的位置替换掉节点1的位置，并且将节点1变成节点2的左侧子节点，这样就变成了之前场景一（左左）中的情况1了，如下图所示：
第二步，像之前场景一（左左）中的情况1那样，将根节点3进行向右的单旋转，成为节点2的右侧子节点即可保持平衡，如下图所示：
流程图如下：
情况2：
节点的左侧子树偏重，左侧子树的右侧偏重，且左侧子树的右侧子节点的下方是不平衡的，如下图所示：
根节点50的左侧子树偏重，左侧子节点30的右侧子节点40的下方只有左边一侧有子节点35，所以此时子节点40是不平衡的，且整体也都是不平衡的，此时需要保持平衡的话：
第一步，先将根节点50与左侧子树分离，如下图所示：
第二步，将节点40的左侧子节点35替换到节点40原来的位置，此时节点35成为节点30右侧的新子节点，然后将节点40变成节点30的父节点，如下图所示：
第三步，将节点40这一系整体作为根节点50的左侧子树，这样就又变成了之前场景一（左左）中的情况1了（我知道上一步直接将节点50这一系变成节点40的右侧子树就能直接平衡，但是变回场景一中的情况1有利于代码层面的复用），如下图所示：
第四步，像之前场景一（左左）中的情况1那样，将根节点50连带着子节点70这一系整体进行向右的单旋转，作为节点40的右侧子树，这样整体就保持平衡，如下图所示：
整体流程如下：
LR使用场景：节点的左侧子节点高度大于右侧子节点的高度，并且左侧子节点的右侧较重的情况。
场景四：
右左（RL）：向左的双旋转（先RR向左的单旋转，再LL向右的单旋转）
此时又可细分为两种情况：
情况1：
节点的右偏重，右侧子节点的左侧子节点是平衡的，如下图所示：
根节点1的右侧偏重，且右侧子节点3的左侧偏重，右侧子节点3的左侧子节点2下方没有子节点，所以节点2下方是平衡的，但是节点1、3、2整体是不平衡的，此时需要保持平衡的话：
第一步，先将节点2从原来的位置替换掉节点3的位置，并且将节点3变成节点2的右侧子节点，这样就变成了之前场景二（右右）中的情况1了，如下图所示：
第二步，像之前场景二（右右）中的情况1那样，将根节点1进行向左的单旋转，成为节点2的左侧子节点即可保持平衡，如下图所示：
流程图如下：
情况2：
节点的右侧子树偏重，右侧子树的左侧偏重，且右侧子树的左侧子节点的下方是不平衡的，如下图所示：
根节点70的右侧子树偏重，右侧子节点80的左侧子节点72的下方只有右边一侧有子节点75，所以此时子节点72是不平衡的，且整体也都是不平衡的，此时需要保持平衡的话：
第一步，先将根节点70与右侧子树分离，如下图所示：
第二步，将节点72的右侧子节点75替换到节点72原来的位置，此时节点75成为节点80左侧的新子节点，然后将节点72变成节点80的父节点，如下图所示：
第三步，将节点72这一系整体作为根节点70的右侧子树，这样就又变成了之前场景二（右右）中的情况1了（我知道上一步直接将节点70这一系变成节点72的左侧子树就能直接平衡，但是变回场景二中的情况1有利于代码层面的复用），如下图所示：
第四步，像之前场景二（右右）中的情况1那样，将根节点70连带着子节点50这一系整体进行向左的单旋转，作为节点72的左侧子树，这样整体就保持平衡，如下图所示：
整体流程如下：
自平衡二叉树的自我实现
既然AVL树是一个BST树，我们可以扩展我们写的BST类，只需要覆盖用来维持AVL树平衡的方法，也就是insert、insertNode和removeNode方法。所有其他的BST方法将会被AVLTree类继承。
（如果代码看不懂，没太大关系，请千万要先把图中的转换看懂！用了一上午才做好的这些图，也不知道其他小伙伴能不能理解。）
// 先将之前实现的二叉搜索树直接copy过来：
// 树中每个存储数据的地方叫元素节点，所以要创建一个节点的类
class Node{
constructor(key){ // 这里的key不像是栈或者队列里面的索引，树的key直接对应的就是节点所存储的数据值
this.key = key // 存储节点值
this.left = null // 索引，指向左侧子节点，就像双向链表，链表是上下结构（指针域指向上和下），树是左右结构（指向左和右）
this.right = null // 索引，指向右侧子节点
}
}
// 二叉搜索树类
class BinarySearchTree{
constructor(){
this.root = null // 二叉树的根节点，默认值为null，初始化
}
insert(key){ // 往二叉树里面插入新的值
if(!this.root){ // 如果根节点没有值，那么就插到二叉树的根节点中
this.root = new Node(key)
}else{ // 如果根节点已经有了值，做判断，比较插入的子节点的值与父节点的值得大小，来决定是左侧子节点还是右侧子节点
this.insertNode(this.root,key) // this.root是因为要每次插入新值的时候，要从根节点开始做比较大小的判断并插入值
}
}
// insertNode方法是为了在已经有了大量数据的时候，能够递归地调用
insertNode(node,key){ // 往某个节点插入一个值，node表示父节点，key表示子节点的值，子节点的值要和父节点的值比较后决定左右侧
if(key < node.key){ // 如果待插入的值 比 父节点的值小，插左边
// 还要细分，如果该父节点的左边已经有了一个子节点（因为不可能每次都是插入根节点的子节点，万一有很多层），那么就要判断
if(node.left){ // 该父节点左侧已有子节点，待插入的值 就要成为 该子节点 的 子节点（不确定有多少层，所以要递归）
this.insertNode(node.left,key) // 递归调用往某个节点插入值的方法，这次是左侧子节点的值与待插入值比较大小
}else{ // 如果该父节点左侧没有子节点，直接插入成为该父节点的子节点
node.left = new Node(key)
}
}else{ // 大于或是等于插右边同样右侧子节点也要进行递归判断
if(node.right){ // 该父节点右侧已有子节点，待插入的值 就要成为 该子节点 的 子节点（不确定有多少层，所以要递归）
this.insertNode(node.right,key) // 递归调用往某个节点插入值的方法，这次是右侧子节点的值与待插入值比较大小
}else{ // 如果该父节点右侧没有子节点，直接插入成为该父节点的子节点
node.right = new Node(key)
}
}
}
min(){ // 查询整个二叉树的最小值，同样需要一个递归方法，因为无法得知哪个节点才是最小值
return this.minNode(this.root) // 返回 从根节点开始递归判断查找最小值的函数方法 的 返回值
}
// 注意区分min方法和minNode方法的区别，一个是查找整个树的最小值，一个是从某个节点开始往下的最小值（不一定是整个树的最小值）
minNode(node){ // 从某个指定的节点开始 递归地判断查找最小值方法，node表示传入的节点
let current = node // 将每一次当前传入的节点保存在变量中
while(current && current.left){ // 在 当前节点存在值 并且 当前节点的左侧子节点也存在值时，说明还有更小的值
current = current.left // 就将左侧子节点的变成当前节点，继续进行循环比较
}
// 否则直接进行返回，左侧没有子节点就表明当前节点就是最小值所在节点
return current
}
max(){ // 查询整个二叉树的最大值，同样需要一个递归方法，因为无法得知哪个节点才是最小值
return this.maxNode(this.root) // 返回 从根节点开始递归判断查找最小值的函数方法 的 返回值
}
// 注意区分max方法和maxNode方法的区别，一个是查找整个树的最大值，一个是从某个节点开始往下的最大值（不一定是整个树的最大值）
maxNode(node){ // 从某个指定的节点开始 递归地判断查找最大值方法，node表示传入的节点
let current = node // 将每一次当前传入的节点保存在变量中
while(current && current.right){ // 当 当前节点存在值 并且 当前节点的右侧子节点也存在值时，说明还有更大的值
current = current.right // 就将右侧子节点的变成当前节点，继续进行循环比较
}
// 否则直接进行返回，右侧没有子节点就表明当前节点就是最大值所在节点
return current
}
// 中序遍历
inOrderTraverse(cb){ // 接收一个回调函数，中序遍历排序
this.inOrderTraverseNode(this.root,cb) // 从根节点开始中序遍历排序
}
inOrderTraverseNode(node,cb){ // 中序遍历递归方法
if(node){ // 当该节点存在的时候才做遍历操作
this.inOrderTraverseNode(node.left,cb)
cb(node.key)
this.inOrderTraverseNode(node.right,cb)
}
}
// 先序遍历
preOrderTraverse(cb){ // 接收一个回调函数，先序遍历数据的结构
this.preOrderTraverseNode(this.root,cb) // 从根节点开始先序遍历
}
preOrderTraverseNode(node,cb){ // 先序遍历递归方法
if(node){ // 当该节点存在的时候才做遍历操作
cb(node.key)
this.preOrderTraverseNode(node.left,cb)
this.preOrderTraverseNode(node.right,cb)
}
}
// 后序遍历
postOrderTraverse(cb){ // 接收一个回调函数，后序遍历
this.postOrderTraverseNode(this.root,cb) // 从根节点开始后序遍历排序
}
postOrderTraverseNode(node,cb){ // 后序遍历递归方法
if(node){ // 当该节点存在的时候才做遍历操作
this.postOrderTraverseNode(node.left,cb)
this.postOrderTraverseNode(node.right,cb)
cb(node.key)
}
}
// 查找功能
searchKey(key){
return this.searchNode(this.root,key)
}
searchNode(node,key){ // 递归方法
// 先判断树里面有没有东西
if(node){ // 树中必须有节点才能进行搜索
// 再判断值的大小，决定从哪边搜
if(key < node.key){ // 如果传入的值比当前节点的值小，继续搜索左侧子节点
return this.searchNode(node.left,key)
}else if(key > node.key){ // 如果传入的值比当前节点的值大，继续搜索右侧子节点
return this.searchNode(node.right,key)
}else{ // 既不是大于也不是小于那就是搜到了
return true
}
}else{ // 如果节点都不存在那就不用搜了
return false
}
}
// 删除功能
removeKey(key){
this.root = this.removeNode(this.root,key)
}
removeNode(node,key){
if(node){ // 树里面有节点存在才能删
if(key < node.key){ // 从左侧开始搜
node.left = this.removeNode(node.left,key)
return node // 返回拼接后的节点
}else if(key > node.key){ // 从右侧开始搜
node.right = this.removeNode(node.right,key)
return node // 返回拼接后的节点
}else{ // 找到了要删除的对象
// 第一种情况：待删除的节点下面左右两侧都有子节点
if(node.left && node.right){
let target = this.minNode(node.right) // 将待删除节点的右侧子节点的所有子节点中最小的子节点找出来，即最小孙子节点
node.key = target.key // 最小孙子节点替补到被删除节点的位置上
node.right = this.removeNode(node.right,key) // 把那个找来做替补的最小孙子节点从原来的孙子位置上删掉
return node
}
// 第二种情况：待删除节点左侧或者右侧有子节点
if(node.left || node.right){
if(node.left){ // 如果待删除节点左侧有子节点，左侧子节点替代被删除节点
node = node.left
}
if(node.right){ // 同理
node = node.right
}
return node // 返回替代后的节点
}
// 第三种情况：待删除节点就是一个叶节点
node = null
return node
}
}else{
return null
}
}
// 修改功能
updateKey(key,key1){
return this.updateNode(this.root,key,kye1)
}
updateNode(node,key,key1){ // 递归方法
// 先判断树里面有没有东西
if(node){ // 树中必须有节点才能进行搜索
// 再判断值的大小，决定从哪边搜
if(key < node.key){ // 如果传入的值比当前节点的值小，继续搜索左侧子节点
return this.updateNode(node.left,key,key1)
}else if(key > node.key){ // 如果传入的值比当前节点的值大，继续搜索右侧子节点
return this.updateNode(node.right,key,key1)
}else{ // 既不是大于也不是小于那就是搜到了
node.key = key1
return true
}
}else{ // 如果节点都不存在那就不用搜了
return false
}
}
}
// 下面部分就是真正开始实现自平衡二叉树了
// 先定义一个平衡因子标准映射表，方便后期阅读
const BalanceFactor = {
UNBALANCED_RIGHT:-2, // 右边极其不平衡
SLIGHTLY_UNBALANCED_RIGHT:-1, // 右边有点不平衡
BALANCED:0, // 左右都平
UNBALANCED_LEFT:1, // 左边有点不平衡
SLIGHTLY_UNBALANCED_LEFT:2, // 左边极其不平衡
}
// 自平衡二叉树类 继承 二叉搜索树类
class AVLTree extends BinarySearchTree{
constructor(){
super()
}
getNodeHeight(node){ // 获取传入节点高度
if(node){ // 判断节点是否存在
return Math.max(this.getNodeHeight(node.left),this.getNodeHeight(node.right)) + 1 // 发生了隐式类型转换，递归入口
// 如果是根节点传入，左侧节点没有，返回-1，右侧节点也没有，返回-1，Math.max(-1,-1)取得就是-1，-1+1等于0
}else{
return -1 // 递归出口
}
}
getBalanceFactor(node){ // 计算平衡因子
const heightDifference = this.getNodeHeight(node.left) - this.getNodeHeight(node.right) // 用左边子树高度减去右边子树高度
switch(heightDifference){
case -2:
return BalanceFactor.UNBALANCED_RIGHT
case -1:
return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT
case 0:
return BalanceFactor.BALANCED
case 1:
return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
case 2:
return BalanceFactor.UNBALANCED_LEFT
}
}
// 整个左侧子树较重，将左侧子树右旋
rotationLL(node){ // 左左（LL）：向右的单旋转
let temp = node.left
node.left = temp.right
temp.right = node
return temp
}
// 整个右侧子树较重，将右侧子树左旋
rotationRR(node){ // 右右（RR）：向左的单旋转
let temp = node.right
node.right = temp.left
temp.left = node
return temp
}
// 左侧子树的右侧较重，先变成整个左侧子树较重，再将整个左侧子树右旋
rotationLR(node){ // 左右（LR）：向右的双旋转（先RR向左的单旋转，再LL向右的单旋转）
node.left = this.rotationRR(node.left) // 先把左侧子节点左单旋转，左侧子树传入RR就会变成先平衡左侧子树的右侧较重部分，使其变成整个左侧子树较重
return this.rotationLL(node) // 当整个左侧子树较重时，就进行向右的单旋转
}
// 右侧子树的左侧较重，先变成整个右侧子树较重，再将整个右侧子树左旋
rotationRL(node){ // 右左（RL）：向左的双旋转（先LL向右的单旋转，再RR向左的单旋转）
node.right = this.rotationLL(node.right) // 先把右侧子节点右单旋转，右侧子树传入LL就会变成先平衡右侧子树的左侧较重部分，使其变成整个右侧子树较重
return this.rotationRR(node) // 当整个右侧子树较重时，就进行向左的单旋转
}
// 插入新节点
insert(key) {
this.root = this.insertNode(this.root,key)
}
insertNode(node, key) { // 插入新节点的递归方法
if(!node){ // 如果node节点不存在，生成并返回node节点
return new Node(key)
}else if(key < node.key){ // 如果待插入的值小于当前节点的值，插入节点的左侧子节点
node.left = this.insertNode(node.left,key)
}else if(key > node.key){ // 如果待插入的值大于当前节点的值，插入节点的右侧子节点
node.right = this.insertNode(node.right,key)
}else{ // 如果值重复了，返回节点
return node
}
// 上面的代码和BST一模一样，现在下面重点来了
// 插入完成之后，判断当前节点是否平衡，如不平衡，则进行平衡操作
switch(this.getBalanceFactor(node)){ // 每次都平衡一点点，立马对新插入的节点进行平衡，而不是等全部插完再一次性平衡
// 只有极不平衡才需要被平衡，即高度差大于1时，左边极不平衡，右边极不平衡
case BalanceFactor.UNBALANCED_LEFT:
if(key < node.left.key){ // 插入的新值小于左侧子节点的值，需要进行LL平衡
node = this.rotationLL(node)
}else{ // 插入的新值大于父节点的值
node = this.rotationLR(node)
}
break
case BalanceFactor.UNBALANCED_RIGHT:
if(key < node.right.key){ // 插入的新值小于右侧子节点的值
node = this.rotationRL(node)
}else{
node = this.rotationRR(node)
}
break
}
return node // 将平衡好的node返回
}
removeNode(node, key) { // 删除节点的递归方法
if(!node){ // 如果要删除的节点压根不存在
return null
}
node = super.removeNode(node,key)
switch(this.getBalanceFactor(node)){ // 每次都平衡一点点，立马对新删除后剩下的的节点进行平衡，而不是等全部删完再一次性平衡
// 只有极不平衡才需要被平衡，即高度差大于1时，左边极不平衡，右边极不平衡
case BalanceFactor.UNBALANCED_LEFT:
if(
this.getBalanceFactor(node.left) === BalanceFactor.BALANCED ||
this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
){
node = this.rotationLL(node)
}else{ // 插入的新值大于父节点的值
node = this.rotationLR(node)
}
break
case BalanceFactor.UNBALANCED_RIGHT:
if(
this.getBalanceFactor(node.right) === BalanceFactor.BALANCED ||
this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
){
node = this.rotationRR(node)
}else{
node = this.rotationRL(node)
}
break
}
return node // 将平衡好的node返回
}
}
let treeData = new AVLTree()
treeData.insert(10)
treeData.insert(5)
treeData.insert(3)
treeData.insert(15)
treeData.insert(13)
treeData
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用？
- 本站所有资源版权均属于原作者所有，这里所提供资源均只能用于参考学习用，请勿直接商用。若由于商用引起版权纠纷，一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了？
- 找不到素材资源介绍文章里的示例图片？
- 模板不会安装或需要功能定制以及二次开发？
发表评论
还没有评论，快来抢沙发吧！