![](https://pics6.baidu.com/feed/314e251f95cad1c88cf4a168e581eb0cc83d5172.jpeg?token=83aa8414fca495512fdd06a729ee6107&s=B2B5716CC8E2D05F412E80100300409B)
作者 | 宋广泽
责编 | 伍杏玲
出品 | CSDN(ID:CSDNnews)
平衡二叉树,又称AVL树,指的是左子树上的所有节点的值都比根节点的值小,而右子树上的所有节点的值都比根节点的值大,且左子树与右子树的高度差最大为1。因此,平衡二叉树满足所有二叉排序(搜索)树的性质。至于AVL,则是取自两个发明平衡二叉树的科学家的名字:G. M. Adelson-Velsky和E. M. Landis。
二叉搜索树
平衡二叉树是在二叉排序树的基础上发展而来的,那为什么要引入二叉搜索树呢?
所谓二叉搜索树(Binary Search Tree),又叫二叉排序树,简单而言就是左子树上所有节点的值均小于根节点的值,而右子树上所有结点的值均大于根节点的值,左小右大,并不是乱序,因此得名二叉排序树。
一个新事物不能凭空产生,那二叉搜索树又有什么用呢?
有了二叉搜索树,当你要查找一个值,就不需要遍历整个序列或者说遍历整棵树了,可以根据当前遍历到的结点的值来确定搜索方向,这就好比你要去日本,假设你没有见过世界地图,你不知道该往哪个方向走,只能满地球找一遍才能保证一定能够到达日本;而如果你见过世界地图,你知道日本在中国的东边,你就不会往西走、往南走、往北走。这种思维在搜索中被叫做“剪枝”,把不必要的分枝剪掉可以提高搜索效率。在二叉搜索树中查找值,每次都会把搜索范围缩小,与二分搜索的思维类似。
![](https://pics0.baidu.com/feed/adaf2edda3cc7cd943e48266a5bead3aba0e918d.jpeg?token=37b08ed2ec0aa0d1c50e114633054a21&s=EBD0C91A115A61CE44FCA1C2030060B7)
如下图所示的二叉搜索树:
![](https://pics0.baidu.com/feed/9922720e0cf3d7ca3a57dd116fa0320c6a63a97d.png?token=5501bf9c3284d38423dfc047fa7bec94&s=79A834724182D945487C11DA030070B1)
要想查找到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]这样的顺序插入,其流程是这样的:
![](https://pics3.baidu.com/feed/e61190ef76c6a7efd137d9ea60452354f2de6629.png?token=21dd2cc1d69927ddd63519700d903ac2&s=58283C7215525FCC046051CF0300E032)
若按照[1,3,5,8,9,13]这样的顺序插入,其流程是这样的:
![](https://pics6.baidu.com/feed/f9dcd100baa1cd1181b2e0a326ad44f9c2ce2d76.png?token=23307625e5d4996efc77622b6b1bfa42&s=58243C721D03584504D451CA0300C0B3)
如果在上面的二叉搜索树中查找13,是要将所有节点都遍历一遍的,时间复杂度就变成了O(n),几乎就是一个链表。
细心的朋友可能已经发现,插入的序列越接近有序,生成的二叉搜索树就越像一个链表。
为了避免二叉搜索树变成“链表”,我们引入了平衡二叉树,即让树的结构看起来尽量“均匀”,左右子树的节点数尽量一样多。
生成平衡二叉树
那给定插入序列,如何生成一棵平衡二叉树呢?
先按照生成二叉搜索树的方法构造二叉树,直至二叉树变得不平衡,即出现这样的节点:左子树与右子树的高度差大于1。至于如何调整,要看插入的导致二叉树不平衡的节点的位置。主要有四种调整方式:LL(左旋)、RR(右旋)、LR(先左旋再右旋)、RL(先右旋再左旋)。
节点的声明如下:
structnode{//值int val;//左孩子node *left;//右孩子 node *right;};求树的高度的函数:intdepth(node *root){if(root==NULL) {return0; }int dep1=depth(root->left);int dep2=depth(root->right);return (dep1>dep2?dep1:dep2)+1;}
代码解析:二叉树的高度取决于高度大的子树,为高度大的子树的高度+1。空树的高度为0。
所谓LL(左旋)就是向左旋转一次,下图所示为最简洁的左旋(插入3导致值为1的节点不平衡):
![](https://pics0.baidu.com/feed/4ec2d5628535e5ddc9caa275ea792beacc1b62fe.png?token=fafd0b11a4b1755199e8c0327587d51b&s=7AAC3C620B505A454C4C34C40300F0B1)
然而更多时候根节点并不是只有一个子树,下图为复杂的LL(左旋,插入13导致值为4的节点不平衡):
![](https://pics2.baidu.com/feed/6609c93d70cf3bc7f09fdfe84fbf36a4cc112a5f.png?token=c793114ab3c691ff091740cc5d172741&s=1FA674229B644D130265A9E103005033)
红色节点为插入后不平衡的节点,黄色部分为需要改变父节点的分支,左旋后,原红色节点的右孩子节点变成了根节点,红色节点变成了它的左孩子,而它原本的左孩子(黄色部分)不能丢,而此时红色节点的右孩子是空的,于是就把黄色部分放到了红色节点的右孩子的位置上。调整后该二叉树还是一棵二叉排序(搜索)树,因为黄色部分的值大于原来的根节点的值,而小于后来的根节点的值,调整后,黄色部分还是位于原来的根节点(红色节点)和后来的根节点之间。
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的节点不平衡):
![](https://pics4.baidu.com/feed/77094b36acaf2eddbafc4db22caf8dec380193a4.png?token=b6915fefdb25b4b8e7c4d17efe0f89c8&s=5EAC3C620B1160414CE4FCDC0300C0B3)
然而更多时候根节点并不是只有一个子树,下图为复杂的RR(右旋,插入1导致值为9的节点不平衡):
![](https://pics2.baidu.com/feed/95eef01f3a292df5e812ff43218ed06536a873d3.png?token=4b931e56f6b13975124dd33538f203fa&s=13967C2293B74C224275ECF003005030)
红色节点为插入后不平衡的节点,黄色部分为需要改变父节点的分支,右旋后,原红色节点的左孩子节点变成了根节点,红色节点变成了它的右孩子,而它原本的右孩子(黄色部分)不能丢,而此时红色节点的左孩子是空的,于是就把黄色部分放到了红色节点的左孩子的位置上。调整后该二叉树还是一棵二叉排序(搜索)树,因为黄色部分的值小于原来的根节点的值,而大于后来的根节点的值,调整后,黄色部分还是位于后来的根节点和原来的根节点(红色节点)之间。
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的节点不平衡):
![](https://pics2.baidu.com/feed/9f510fb30f2442a780a5ad8d4ffc214ed01302b7.png?token=309459d56ceb89bb31591c4aa3624563&s=5AA43C621F956C435E5CA8D40300C0B3)
然而更多时候根节点并不是只有一个子树,下图为复杂的LR旋转(插入8导致值为9的节点不平衡):
![](https://pics7.baidu.com/feed/4d086e061d950a7b9d5a23eb946eeedcf3d3c9f3.png?token=ba42411935c6e12e3b9a58f7e57b2e2e&s=592E3C7215527DCC42FD71CA0300B0B0)
先将红色节点的左子树左旋,红色节点的左子树的根原本是值为4的节点,左旋后变为值为6的节点,原来的根节点变成了左旋后根节点的左孩子,左旋后根节点原本的左孩子(蓝色节点)变成了原来的根节点的右孩子;再整体右旋,原来的根节点(红色节点)变成了右旋后的根节点的右孩子,右旋后的根节点原本的右孩子(黄色节点)变成了原来的根节点(红色节点)的左孩子。旋转完成后,仍然是一棵二叉排序(搜索)树。
LR旋转代码如下:
node *LeftRightRotate(node *root){//先对root的左子树左旋再对root右旋 root->left=LeftRotate(root->left);return RightRotate(root);}
代码解析:返回的是LR旋转后的根节点,先对根节点的左子树左旋,再整体右旋。root对应上图中值为9的节点。
所谓RL(先右旋再左旋)就是先将右子树右旋,再整体左旋,下图为最简洁的RL旋转(插入2导致值为1的节点不平衡):
![](https://pics4.baidu.com/feed/f7246b600c3387445e24767accb055fcd62aa01c.png?token=63b61f934d7e559ef1f52496accb16d9&s=18207C3203B46C215E5CA8D0030090B3)
然而更多时候根节点并不是只有一个子树,下图为复杂的RL旋转(插入8导致值为4的节点不平衡):
![](https://pics7.baidu.com/feed/4d086e061d950a7b9d5a23eb946eeedcf3d3c9f3.png?token=ba42411935c6e12e3b9a58f7e57b2e2e&s=592E3C7215527DCC42FD71CA0300B0B0)
先将红色节点的右子树右旋,红色节点的右子树的根原本是值为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==NULL) { root=new node; root->val=v; root->left=NULL; root->right=NULL; }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(NULL), right(NULL) {} * }; */class Solution {public:int depth(TreeNode *root) {if(root==NULL) { return 0; }int dep1=depth(root->left);int dep2=depth(root->right); return (dep1>dep2?dep1:dep2)+1; } bool isBalanced(TreeNode* root) {if(root==NULL) { 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); } }};
代码解析:递归进行判断就好啦,先判断以下左子树是不是平衡二叉树,再判断一下右子树是不是平衡二叉树,两个子树有一个不是平衡二叉树则该树就不是平衡的。空树一定是平衡的。
![](https://pics4.baidu.com/feed/8ad4b31c8701a18b681bddfc01908b0d2a38fed3.png?token=39da4be0cba4af0f563a4c07d2413266&s=CCAA3073C5326D205A7D04DA0000C0B2)
![](https://pics6.baidu.com/feed/71cf3bc79f3df8dc844bfe0e50aefe8e4610287b.png?token=7d3f8920d241a81ec8bb5c256dc0773e&s=18A07C32C3B3402B4844F4D4030080B1)
在这金九银十的Offer收割季,衷心祝愿大家都收到想要的Offer,去想去的公司,当上CTO,迎娶白富美。