平衡二叉树（平衡二叉树和完全二叉树的区别）

作者 | 宋广泽

责编 | 伍杏玲

出品 | CSDN(ID：CSDNnews)

平衡二叉树，又称AVL树，指的是左子树上的所有节点的值都比根节点的值小，而右子树上的所有节点的值都比根节点的值大，且左子树与右子树的高度差最大为1。因此，平衡二叉树满足所有二叉排序（搜索）树的性质。至于AVL，则是取自两个发明平衡二叉树的科学家的名字：G. M. Adelson-Velsky和E. M. Landis。

平衡二叉树（平衡二叉树和完全二叉树的区别）

二叉搜索树

平衡二叉树是在二叉排序树的基础上发展而来的，那为什么要引入二叉搜索树呢？

所谓二叉搜索树（Binary Search Tree），又叫二叉排序树，简单而言就是左子树上所有节点的值均小于根节点的值，而右子树上所有结点的值均大于根节点的值，左小右大，并不是乱序，因此得名二叉排序树。

一个新事物不能凭空产生，那二叉搜索树又有什么用呢？

有了二叉搜索树，当你要查找一个值，就不需要遍历整个序列或者说遍历整棵树了，可以根据当前遍历到的结点的值来确定搜索方向，这就好比你要去日本，假设你没有见过世界地图，你不知道该往哪个方向走，只能满地球找一遍才能保证一定能够到达日本；而如果你见过世界地图，你知道日本在中国的东边，你就不会往西走、往南走、往北走。这种思维在搜索中被叫做“剪枝”，把不必要的分枝剪掉可以提高搜索效率。在二叉搜索树中查找值，每次都会把搜索范围缩小，与二分搜索的思维类似。

平衡二叉树（平衡二叉树和完全二叉树的区别）

如下图所示的二叉搜索树：

平衡二叉树（平衡二叉树和完全二叉树的区别）

要想查找到8，则是先到达根节点，其值为5，8比5大因此继续往右子树上找，到达9，8比9小因此往左子树上找，最终找到8；

要想查找4，则是先到达根节点其值为5，4比5小因此往左子树上找，到达1，4比1大因此往右子树上找，到达3，4比3大因此往右子树上找，而值为3的节点的右子树是空的，因此该搜索二叉树中不存在值为4的节点。

有了二叉排序树就可以使插入、搜索效率大大提高了，为什么还要引入平衡二叉树？

二叉搜索树的结构与值的插入顺序有关，同一组数，若其元素的插入顺序不同，二叉搜索树的结构是千差万别的。举个例子，给出一组数[1,3,5,8,9,13]。

若按照[5,1,3,9,13,8]这样的顺序插入，其流程是这样的：

平衡二叉树（平衡二叉树和完全二叉树的区别）

若按照[1,3,5,8,9,13]这样的顺序插入，其流程是这样的：

平衡二叉树（平衡二叉树和完全二叉树的区别）

如果在上面的二叉搜索树中查找13，是要将所有节点都遍历一遍的，时间复杂度就变成了O(n)，几乎就是一个链表。

细心的朋友可能已经发现，插入的序列越接近有序，生成的二叉搜索树就越像一个链表。

为了避免二叉搜索树变成“链表”，我们引入了平衡二叉树，即让树的结构看起来尽量“均匀”，左右子树的节点数尽量一样多。

平衡二叉树（平衡二叉树和完全二叉树的区别）

生成平衡二叉树

那给定插入序列，如何生成一棵平衡二叉树呢？

先按照生成二叉搜索树的方法构造二叉树，直至二叉树变得不平衡，即出现这样的节点：左子树与右子树的高度差大于1。至于如何调整，要看插入的导致二叉树不平衡的节点的位置。主要有四种调整方式：LL（左旋）、RR（右旋）、LR（先左旋再右旋）、RL（先右旋再左旋）。

节点的声明如下：

  
   struct node
   {
   //值
   int val;
   //左孩子
   node *left;
   //右孩子
   node *right;
   };
   求树的高度的函数：
   int depth(node *root)
   {
   if(root==)
   {
   return 0;
   }
   int dep1=depth(root->left);
   int dep2=depth(root->right);
   return (dep1>dep2?dep1:dep2)+1;
   }

代码解析：二叉树的高度取决于高度大的子树，为高度大的子树的高度+1。空树的高度为0。

所谓LL（左旋）就是向左旋转一次，下图所示为最简洁的左旋（插入3导致值为1的节点不平衡）：

平衡二叉树（平衡二叉树和完全二叉树的区别）

然而更多时候根节点并不是只有一个子树，下图为复杂的LL（左旋，插入13导致值为4的节点不平衡）：

平衡二叉树（平衡二叉树和完全二叉树的区别）

红色节点为插入后不平衡的节点，黄色部分为需要改变父节点的分支，左旋后，原红色节点的右孩子节点变成了根节点，红色节点变成了它的左孩子，而它原本的左孩子（黄色部分）不能丢，而此时红色节点的右孩子是空的，于是就把黄色部分放到了红色节点的右孩子的位置上。调整后该二叉树还是一棵二叉排序（搜索）树，因为黄色部分的值大于原来的根节点的值，而小于后来的根节点的值，调整后，黄色部分还是位于原来的根节点（红色节点）和后来的根节点之间。

LL（左旋）代码如下：

  
   node *LeftRotate(node *root)
   {
   //左旋
   node *temp=root->right;
   root->right=temp->left;
   temp->left=root;
   return temp;
   }

代码解析：返回的是左旋后的根节点，左旋后的根节点是原来根节点的右孩子，左旋后的根节点的左孩子需要嫁接到原来根节点的右孩子上，原来的根节点嫁接到左旋后根节点的左孩子上。temp对应上图中值为8的节点，root对应上图中值为4的节点。

所谓RR（右旋）就是向右旋转一次，下图所示为最简洁的右旋（插入1导致值为3的节点不平衡）：

平衡二叉树（平衡二叉树和完全二叉树的区别）

然而更多时候根节点并不是只有一个子树，下图为复杂的RR（右旋，插入1导致值为9的节点不平衡）：

平衡二叉树（平衡二叉树和完全二叉树的区别）

红色节点为插入后不平衡的节点，黄色部分为需要改变父节点的分支，右旋后，原红色节点的左孩子节点变成了根节点，红色节点变成了它的右孩子，而它原本的右孩子（黄色部分）不能丢，而此时红色节点的左孩子是空的，于是就把黄色部分放到了红色节点的左孩子的位置上。调整后该二叉树还是一棵二叉排序（搜索）树，因为黄色部分的值小于原来的根节点的值，而大于后来的根节点的值，调整后，黄色部分还是位于后来的根节点和原来的根节点（红色节点）之间。

RR（右旋）代码如下：

  
   node *RightRotate(node *root)
   {
   //右旋
   node *temp=root->left;
   root->left=temp->right;
   temp->right=root;
   return temp;
   }

代码解析：返回的是右旋后的根节点，右旋后的根节点是原来根节点的左孩子，右旋后的根节点的右孩子需要嫁接到原来根节点的左孩子上，原来的根节点嫁接到右旋后根节点的右孩子上。temp对应上图中值为5的节点，root对应上图中值为9的节点。

所谓LR（先左旋再右旋）就是先将左子树左旋，再整体右旋，下图为最简洁的LR旋转（插入2导致值为3的节点不平衡）：

平衡二叉树（平衡二叉树和完全二叉树的区别）

然而更多时候根节点并不是只有一个子树，下图为复杂的LR旋转（插入8导致值为9的节点不平衡）：

平衡二叉树（平衡二叉树和完全二叉树的区别）

先将红色节点的左子树左旋，红色节点的左子树的根原本是值为4的节点，左旋后变为值为6的节点，原来的根节点变成了左旋后根节点的左孩子，左旋后根节点原本的左孩子（蓝色节点）变成了原来的根节点的右孩子；再整体右旋，原来的根节点（红色节点）变成了右旋后的根节点的右孩子，右旋后的根节点原本的右孩子（黄色节点）变成了原来的根节点（红色节点）的左孩子。旋转完成后，仍然是一棵二叉排序（搜索）树。

LR旋转代码如下：

  
   node *LeftRightRotate(node *root)
   {
   //先对root的左子树左旋再对root右旋
   root->left=LeftRotate(root->left);
   return RightRotate(root);
   }

代码解析：返回的是LR旋转后的根节点，先对根节点的左子树左旋，再整体右旋。root对应上图中值为9的节点。

所谓RL（先右旋再左旋）就是先将右子树右旋，再整体左旋，下图为最简洁的RL旋转（插入2导致值为1的节点不平衡）：

平衡二叉树（平衡二叉树和完全二叉树的区别）

然而更多时候根节点并不是只有一个子树，下图为复杂的RL旋转（插入8导致值为4的节点不平衡）：

先将红色节点的右子树右旋，红色节点的右子树的根原本是值为9的节点，右旋后变为值为6的节点，原来的根节点变成了右旋后根节点的右孩子，右旋后根节点原本的右孩子（蓝色节点）变成了原来的根节点的左孩子；再整体左旋，原来的根节点（红色节点）变成了左旋后的根节点的左孩子，左旋后的根节点原本的左孩子（黄色节点）变成了原来的根节点（红色节点）的右孩子。旋转完成后，仍然是一棵二叉排序（搜索）树。

RL旋转代码如下：

  
   node *RightLeftRotate(node *root)
   {
   //先对root的右子树右旋再对root左旋
   root->right=RightRotate(root->right);
   return LeftRotate(root);
   }

代码解析：返回的是RL旋转后的根节点，先对根节点的右子树右旋，再整体左旋。root对应上图中值为4的节点。

构造平衡二叉树是一个边插入边调整的过程，插入一个看看是否造成了不平衡，造成了不平衡就立即调整。代码如下：

  
   node *Insert(node *root,int v)
   {
   if(root==)
   {
   root=new node;
   root->val=v;
   root->left=;
   root->right=;
   }
   else
   {
   if(v<root->val)
   {
   //插到左子树上
   root->left=Insert(root->left,v);
   if(depth(root->left)-depth(root->right)>=2)
   {
   //左边高右边低
   if(v<root->left->val)
   {
   //右旋
   root=RightRotate(root);
   }
   else
   {
   //先对其左子树左旋再右旋
   root=LeftRightRotate(root);
   }
   }
   }
   else
   {
   //插到右子树上
   root->right=Insert(root->right,v);
   if(depth(root->right)-depth(root->left)>=2)
   {
   if(v>root->right->val)
   {
   //左旋
   root=LeftRotate(root);
   }
   else
   {
   //先对其右子树右旋再左旋
   root=RightLeftRotate(root);
   }
   }
   }
   }
   return root;
   }

代码解析：

出现不平衡时到底是执行LL、RR、LR、RL中的哪一种旋转，取决于插入的位置。可以根据值的大小关系来判断插入的位置。插入到不平衡节点的右子树的右子树上，自然是要执行LL旋转；插入到不平衡节点的左子树的左子树上，自然是要执行RR旋转；插入到不平衡节点的左子树的右子树上，自然是要执行LR旋转；插入到不平衡节点的右子树的左子树上，自然是要执行RL旋转。

向一棵平衡二叉树tree中插入值temp的用法是这样的：

tree=Insert(tree,temp);

最后给大家推荐一道经典面试算法题——判断一棵树是不是平衡二叉树：https://leetcode-cn.com
/problems/balanced-binary-tree/

给大家分享以下我的代码：

  
   /**
   * Definition for a binary tree node.
   * struct TreeNode {
   * int val;
   * TreeNode *left;
   * TreeNode *right;
   * TreeNode(int x) : val(x), left, right {}
   * };
   */
   class Solution {
   public:
   int depth(TreeNode *root)
   {
   if(root==)
   {
   return 0;
   }
   int dep1=depth(root->left);
   int dep2=depth(root->right);
   return (dep1>dep2?dep1:dep2)+1;
   }
   bool isBalanced(TreeNode* root) {
   if(root==)
   {
   return true;
   }
   int dep1=depth(root->left);
   int dep2=depth(root->right);
   if(abs(dep1-dep2)>1)
   {
   return false;
   }
   else
   
    
    

   
   {
   return isBalanced(root->left)&&isBalanced(root->right);
   }
   }
   };