学习quot;平衡二叉树quot;之摘录

附上链接:https://www.cnblogs.com/zhangbaochong/p/5164994.html

一、平衡二叉树又被称为AVL树(有别于AVL算法),且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

平衡二叉树大部分操作和二叉查找树类似，主要不同于插入删除的时候平衡二叉树的平衡可能被改变，并且只有从那些插入点到根节点的路径上的节点的平衡性可能被改变，因为只有这些节点的子树可能变化。

平衡二叉树不平衡的情形:

把需要重新平衡的节点叫做a,由于任意两个节点最多只有两个儿子，因此高度不平衡时，a节点的两棵子树的高度相差2，容易看出，这种不平衡可能出现下面4种情况中:

  1.对a的左儿子的左子树进行一次插入

  2.对a的左儿子的右子树进行一次插入

  3.对a的右儿子的左子树进行一次插入

  4.对a的右儿子的右子树进行一次插入

  情形1和情形4是关于a的镜像堆成，情形2和情形3也是关于a的镜像对称，因此理论上看只有两种情况，但编程的角度看还是四种情形。

  第一种情况是插入发生在"外边"的情形(左左或右右),该情况可以通过一次单旋转完成调整;第二种情况是插入发生在"内部"的情形(左右或右左),这种情况比较复杂，需要通过双旋转来调整。

 调整措施:

 一、单旋转

     上图是左左的情况，k2节点不满足平衡性，它的左子树k1比右子树z深两层，k1子树中更深的是k1的左子树x,因此属于左左情况。

      为了恢复平衡，我们把x上移一层，并把z下移一层，但此时实际已经超出了AVL树的性质要求。为此，重新安排节点以形成一棵等价的树。为使树恢复平衡，我们把k2变成这棵树的根节点，因为k2大于k1,把k2置于k1的右子树上，而原本在k1右子树的Y大于k1,小于k2,就把Y置于k2的左子树上，这样既满足了二叉查找树的性质，又满足了平衡二叉树的性质。

二、双旋转

    对于左右和右左两种情况，单旋转不能解决问题，要经过两次旋转。

    对于上图情况，为使树恢复平衡，我们需要进行两步，第一步，把k1作为根，进行一次右右旋转，旋转之后变成了左左情况，所以第二步再进行一次左左旋转，最后得到了一棵以k2为根的平衡二叉树。

AVL树的删除操作:

    同插入操作一样，删除节点时也可能破坏平衡性，这就要求我们删除的时候要进行平衡性调整.

    删除分为以下几种情况：

    首先在整个二叉树中搜索要删除的节点，如果没有搜索到直接返回不作处理，否则执行以下操作:

    1.要删除的节点时当前根节点T。

    如果左右子树都非空，在高度较大的子树中实施删除操作。

    分两种情况:

     (1) 左子树高度大于右子树高度，将左子树中最大的那个元素赋给当前根节点，然后删除左子树中元素值最大的那个节点。

     (1)、左子树高度小于右子树高度，将右子树中最小的那个元素赋给当前根节点，然后删除右子树中元素值最小的那个节点。

     如果左右子树中有一个为空，那么直接用那个非空子树或者是NULL替换当前根节点即可。

     2.要删除的节点元素值小于当前根节点T值，在左子树中进行删除。

        递归调用，在左子树中实施删除。

        这个是需要判断当前根节点是否仍然满足平衡条件，如果满足平衡条件，只需要更新当前根节点T的高度信息;否则，需要进行旋转调整:

        如果T的左子节点的左子树的高度大于T的左子节点的右子树的高度，进行相应的单旋转。否则进行双旋转。

     3.要删除的节点元素值大于当前根节点T值，在右子树中进行删除。

   下面给出详细代码实现:

AvlTree.h

#include 
#include 
using namespace std;
#pragma once//平衡二叉树节点
template 
struct AvlNode {T data;int height;//节点所在高度AvlNode *left;AvlNode *right;AvlNode(const T theData) : data(theData),left(NULL), right(NULL), height(0){}
};//AvlTree
template  
class AvlTree
{public:AvlTree(){}~AvlTree(){}AvlNode *root;//插入节点void Insert(AvlNode *&t, T x);//删除节点bool Delete(AvlNode *&t, T x);//查找是否存在给定值的节点bool Contains(AvlNode *t, const T x) const;//中序遍历void InorderTraversal(AvlNode *t);//前序遍历void PreorderTravelsal(AvlNode *t);//最小值节点AvlNode *FindMin(AvlNode *t) const;//最大值节点AvlNode *FindMax(AvlNode *t) const;private://求树的高度int GetHeight(AvlNode *t);//单旋转 左AvlNode *LL(AvlNode *t);//单旋转 右AvlNode *RR(AvlNode *t);//双旋转 右左AvlNode *LR(AvlNode *t);//双旋转 左右AvlNode *RL(AvlNode *t);
};template 
AvlNode *AvlTree::FindMax(AvlNode *t) const
{if (t == NULL) return NULL;if (t->right == NULL) return t;return FindMax(t->right);
}template 
AvlNode *AvlTree::FindMin(AvlNode *t) const
{if (t == NULL) return NULL;if (t->left == NULL) return t;return FindMin(t->left);
}template 
int AvlTree::GetHeight(AvlNode *t) 
{if (t == NULL) return -1;else return t->height;
}//单旋转
//左左插入导致的不平衡
template 
AvlNode *AvlTree::LL(AvlNode *t)
{AvlNode *q = t->left;  //此时t指向最高的节点，而q指向最高节点的左子树t->left = q->right;//把最高节点的左子树的右子树给到最高节点的左子树q->right = t;//把最高节点给到次高层的左子树节点的右子树t = q;//根指向最高节点的左子树的节点t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;q->height = max(GetHeight(q->left), GetHeight(q->right)) + 1;return q;
}//单旋转
//右右插入导致的不平衡
template 
AvlNode *AvlTree::RR(AvlNode *t) 
{AvlNode *q = t->right;t->right = q->left;q->left = t;t = q;t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;q->height = max(GetHeight(q->left), GetHeight(q->right)) + 1;return q;
}//双旋转
//插入点位于t的左儿子的右子树
template 
AvlNode *AvlTree::LR(AvlNode *t) 
{//双旋转可以通过两次单旋转实现//对t的左节点进行RR旋转，再对根节点进行LL旋转RR(t->left);return LL(t);
}//双旋转
//插入点位于t的右儿子的左子树
template 
AvlNode *AvlTree::RL(AvlNode *t) 
{LL(t->right);return RR(t);
}template 
void AvlTree::Insert(AvlNode *&t, T x)
{if (t == NULL)t = new AvlNode(x);else if (x < t->data) {Insert(t->left, x);//判断平衡情况if (GetHeight(t->left) - GetHeight(t->right) > 1) {//分两种情况 左左或右右if (x < t->left->data) //如果左右子树的深度大于1，而且插入的值x小于左子树节点的值，则左左t = LL(t);else   //左右t = LR(t);}}else if (x > t->data) {Insert(t->right, x);if (GetHeight(t->right) - GetHeight(t->left) > 1) {if (x > t->right->data)t = RR(t);elset = RL(t);}}else;//数据重复t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
}template 
bool AvlTree::Delete(AvlNode *&t, T x) 
{//t为空 未找到要删除的节点if (t == NULL) return false;//找到了要删除的节点else if (t->data == x) {//左右子树都非空if (t->left != NULL && t->right != NULL) {//在高度更大的那个子树上进行删除操作//左子树高度大，删除左子树中值最大的节点，将其赋给根节点if (GetHeight(t->left) > GetHeight(t->right)){t->data = FindMax(t->left)->data;Delete(t->left, t->data);}else { //右子树高度更大，删除右子树中值最小的节点，将其赋给根节点t->data = FindMin(t->right)->data;Delete(t->right, t->data);}}else {//左右子树有一个不为空，直接用需要删除的节点的子节点替换即可AvlNode *old = t;t = t->left ? t->left : t->right;//t赋值为不空的子节点delete old;}}else if (x < t->data) { //要删除的节点在左子树上//递归删除左子树上的节点Delete(t->left, x);//判断是否仍然满足平衡条件if(GetHeight(t->right) - GetHeight(t->left) > 1){if (GetHeight(t->right->left) > GetHeight(t->right->right)) {//RL双旋转t = RL(t);} else {//RR单旋转t = RR(t);}}else {//满足平衡条件，调整高度信息t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;}}else {//要删除的节点在右子树上//递归删除右子树节点Delete(t->right, x);//判断平衡情况if (GetHeight(t->left) - GetHeight(t->right) > 1) {if (GetHeight(t->left->right) > GetHeight(t->left->left)) {//LR双旋转t = LR(t);}else {//LL单旋转t = LL(t);}}else {//满足平衡性，调整高度t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;}}return false;
}//查找节点
template 
bool AvlTree::Contains(AvlNode *t, const T x) const 
{if (t == NULL)return false;if (x < t->data)return Contains(t->left, x);else if (x > t->data)return Contains(t->right, x);elsereturn true;
}//中序遍历
template 
void AvlTree::InorderTraversal(AvlNode *t)
{if (t) {InorderTraversal(t->left);cout << t->data << ' ';InorderTraversal(t->right);}
}//前序遍历
template 
void AvlTree::PreorderTraversal(AvlNode *t) 
{if (t) {cout << t->data << ' ';PreorderTraversal(t->left);PreorderTraversal(t->right);}
}

main.cpp

#include "AvlTree.h"int main()
{AvlTree tree;int value, tmp;cout << "请输入整数建立二叉树(-1结束):" << endl;while (cin >> value) {if (value == -1) break;tree.Insert(tree.root, value);}cout << "中序遍历";tree.InorderTraversal(tree.root);cout << "\n前序遍历:";tree.PreorderTraversal(tree.root);cout << "\n请输入要查找的节点:";cin >> tmp;if (tree.Contains(tree.root, tmp))cout << "已找到" << endl;elsecout << "值为" << tmp << "的节点不存在" << endl;cout << "请输入要删除的节点:";cin >> tmp;tree.Delete(tree.root, tmp);cout << "删除后的中序遍历:";tree.InorderTraversal(tree.root);cout << "\n删除后的前序遍历:";tree.PreorderTraversal(tree.root);
}

附录:这里贴出另一个链接(可参考着看代码，印象更深):http://lib.csdn.net/article/datastructure/9204

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！