首页 / 算法 / 剑指offer39：平衡二叉树
剑指offer39：平衡二叉树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了剑指offer39：平衡二叉树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5969字，纯文字阅读大概需要9分钟。
内容图文
1 题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
2 思路和方法
平衡二叉树，又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。https://blog.csdn.net/qq_43091156/article/details/88558966
从叶节点开始，依次往上求其子树高度，如果在某一子树上不满足要求，则一路返回，不再继续遍历。即，先依次遍历左子树，如果左子树是平衡二叉树，再依次遍历右子树。时间最坏O(n)，空间O(n)。
3 C++核心代码
1
class
Solution {
2
public
:
3
//
返回值：树的深度
4
bool IsBalanced_Solution(TreeNode* pRoot){
5if (pRoot == nullptr)
6returntrue; // ko 7return TreeDepth(pRoot)!=-1;
8 }
910// 返回值：
11// -1：子树不平衡
12// >0：子树深度13int TreeDepth(TreeNode* pRoot){
14if (pRoot == nullptr)
15return0;
1617int left = TreeDepth(pRoot->left);
18if(left==-1) //若左子树不满足平衡，则整个树已不是平衡二叉树了，直接返回，不处理右子树19return -1;
20int right = TreeDepth(pRoot->right);
21if(right ==-1)
22return -1;
23if(left-right > 1 || left - right <-1)
24return -1;
25return left>right ? left+1:right+1;
26 }
27 };
4 AVL平衡二叉树的代码
1 #include <iostream>
2 #include <algorithm>
3 4usingnamespace std;
5 6class AVLNode{
7public:
8int data;
9int height;//结点的高度，叶子结点高度为1 10 AVLNode* lChild;
11 AVLNode* rChild;
12public:
13 AVLNode(int data) :data(data), height(1), lChild(0), rChild(0){}
14};
15 16class AVL{
17public:
18 AVLNode* root;
19public:
20 AVL(){
21 root = nullptr;
22 }
23 ~AVL(){
24delete root;
25 }
26int height(AVLNode* root){
27if (root){
28return root->height;
29 }
30return0;
31 }
32//找到树中最大结点并将其返回 33 AVLNode* finMaxNode(AVLNode* root){
34//一直往右找 35if (root->rChild){
36 root = root->rChild;
37 }
38return root;
39 }
40//找到树中最小结点并将其返回 41 AVLNode* finMinNode(AVLNode* root){
42//一直往左找 43if (root->lChild){
44 root = root->lChild;
45 }
46return root;
47 }
48//以p为根结点右旋转，返回新的根结点 49 AVLNode* llRotate(AVLNode* p){
50 AVLNode* pleft = p->lChild;
51 p->lChild = pleft->rChild;
52 pleft->rChild = p;
53//结点的高度由该节点的子树唯一决定，所以只有子树发生变化的结点才需要更新高度值 54 pleft->height = max(height(pleft->lChild), height(pleft->rChild)) + 1;
55 p->height = max(height(p->lChild), height(p->rChild)) + 1;
56return pleft;
57 }
58//左旋转 59 AVLNode* rrRotate(AVLNode* p){
60 AVLNode* pright = p->rChild;
61 p->rChild = pright->lChild;
62 pright->lChild = p;
63 pright->height = max(height(pright->lChild), height(pright->rChild)) + 1;
64 p->height = max(height(p->lChild), height(p->rChild)) + 1;
65return pright;
66 }
67//先左，再右 68 AVLNode* lrRotate(AVLNode* p){
69 AVLNode* pleft = rrRotate(p->lChild);
70return llRotate(p);
71 }
72//先右，再左 73 AVLNode* rlRotate(AVLNode* p){
74 AVLNode* pright = llRotate(p->rChild);
75return rrRotate(p);
76 }
77//插入新结点，保持平衡 78void insert(int data, AVLNode*& root){
79if (!root){
80 root = new AVLNode(data);
81 }
82else{
83if (data < root->data){
84 insert(data, root->lChild);
85//插入新结点后，如果打破平衡，则需要动态调整 86if (height(root->lChild) - height(root->rChild) == 2){
87if (data < root->lChild->data)
88 root = llRotate(root);
89else 90 root = lrRotate(root);
91 }
92 }
93elseif (data > root->data){
94 insert(data, root->rChild);
95//插入新结点后，如果打破平衡，则需要动态调整 96if (height(root->rChild) - height(root->lChild) == 2){
97if (data > root->rChild->data)
98 root = rrRotate(root);
99else100 root = rlRotate(root);
101 }
102 }
103else{
104 cout << "AVL中已存在该值:" << data << endl;
105 }
106 }
107//平衡后，需要更新根结点的高度值108 root->height = max(height(root->lChild), height(root->rChild)) + 1;
109 }
110//删除结点，保持平衡 111void del(int data, AVLNode*& root){
112if (data < root->data){
113 del(data, root->lChild);
114//删除点之后，若AVL树失去平衡，则进行调整115if (height(root->rChild) - height(root->lChild) == 2){
116 AVLNode* r = root->rChild;
117if (height(r->lChild) > height(r->rChild))
118 root = rlRotate(root);
119else120 root = rrRotate(root);
121 }
122 }
123elseif (data > root->data){
124 del(data, root->rChild);
125//删除点之后，若AVL树失去平衡，则进行调整126if (height(root->lChild) - height(root->rChild) == 2){
127 AVLNode* l = root->lChild;
128if (height(l->lChild) > height(l->rChild))
129 root = llRotate(root);
130else131 root = lrRotate(root);
132 }
133 }
134else{
135//此时root为要删除的点 136if (root->lChild && root->rChild){
137if (height(root->lChild) > height(root->rChild)){
138// 如果root的左子树比右子树高；
139// 则(01)找出root的左子树中的最大节点
140// (02)将该最大节点的值赋值给root。
141// (03)删除该最大节点。
142// 这类似于用"root的左子树中最大节点"做"root"的替身；
143// 采用这种方式的好处是：删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。144 AVLNode* maxNode = finMaxNode(root->lChild);
145 root->data = maxNode->data;
146 del(maxNode->data, root->lChild);
147 }
148else{
149 AVLNode* minNode = finMinNode(root->rChild);
150 root->data = minNode->data;
151 del(minNode->data, root->rChild);
152 }
153 }
154else{
155if (root->lChild){
156 root->data = root->lChild->data;
157 root->lChild = nullptr;
158 }
159elseif (root->rChild){
160 root->data = root->rChild->data;
161 root->rChild = nullptr;
162 }
163else{
164 root = nullptr;//参数是引用，所以此处修改了主函数中的root值 165 }
166 }
167 }
168 }
169void inOrder(AVLNode* root){
170if (root){
171 inOrder(root->lChild);
172 cout << root->data << endl;
173 inOrder(root->rChild);
174 }
175 }
176};
177178int main(){
179 AVL tree;
180 tree.insert(5, tree.root);
181 tree.insert(15, tree.root);
182 tree.insert(25, tree.root);
183 tree.insert(35, tree.root);
184 tree.insert(45, tree.root);
185 tree.insert(55, tree.root);
186 tree.del(55, tree.root);
187 tree.inOrder(tree.root);
188189 system("pause");
190return0;
191 }
参考资料
https://blog.csdn.net/qq_39559641/article/details/83720734（代码很详细全面，写的很好，知识点讲解详细）
https://blog.csdn.net/zjwreal/article/details/88833908
https://blog.csdn.net/qq_43091156/article/details/88558966
https://blog.csdn.net/vaemusicsky/article/details/81607251（AVL平衡二叉树的代码）
原文：https://www.cnblogs.com/wxwhnu/p/11421525.html
内容总结
以上是互联网集市为您收集整理的剑指offer39：平衡二叉树全部内容，希望文章能够帮你解决剑指offer39：平衡二叉树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】