音视频开发之旅（28) 算法序列 - 平衡二叉树
2021-02-02 本文已影响0人
yabin小站
目录
- 平衡二叉树
- 左旋转、右旋转、双旋转的原理
- 代码实现
- 资料
- 收获
上一篇我们学习实践了二叉查找树,其结合了链表的灵活性和二分查找的高效性。但是可能会出现左右子树的深度不一致或者差别很大，最差的情况是只有一系列的左/右子树，插入和删除速度没有影响，但查询操作将会很慢。
对应的解决解决方案就是平衡二叉树
一、平衡二叉树（AVL树）
平衡二叉树是在二叉查找树的基础上，增加了以下规则：
要么是空树，要么左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1.
平衡因子BF（Balance Factor）：二叉树上的结点上左子树的深度值减去右子树的深度值。平衡二叉树的平衡因子的绝对值小于等于1
平衡二叉树的常见树有红黑二叉树、AVL、伸展树等，保证查找的高效率。
二、左旋转、右旋转、双旋转的原理
左旋转
当右子树的高度比左子树的高度要大时，要进行左旋转
具体步骤
1. 创建一个新的结点newNode，值等于当前结点的值（比如根结点）
2. 把新结点的左子树设置为当前结点的左子树 newNode.left= curNode.left
3. 把新结点的右子树设置为当前结点右子树的左子树 newNode.right=curNode.right.left
4. 把当前结点的值换为当前结点右子树的值
5. 把当前结点的右子树设置为当前结点的右子树的右子树 curNode.right = curNode.right.right
6. 把当前结点的左子树设置为新结点
实现左旋转。
案例分析a= 4,3,6,5,7,8
下面来画图一步步拆解
**右旋转 **
1. 创建一个新的结点newNode，值等于当前结点的值
2. 把新结点的右子结点设置为当前结点的右子结点 newNode.right=cur.right
3. 把新结点的左子结点设置为当前结点左子树的右子树 newNode.left = curNode.left.right
4. 把当前结点的值换为当前结点的左子结点的值
5. 把当前结点的左子树设置为当前结点的左子树的左子树 curNode.left=curNode.left.left
6. 把当前结点的右子树设置为新结点
案例分析 a= 10,12,8,9,7,6
基本流程和左旋转一致，下面来画图一步步拆解
双旋转
当符合右旋转条件
如果当前结点左子树的右子树的高度大于左子树的高度
先对当前结点的左子树这个结点进行左旋转
然后对当前结点进行右旋转。
或者符合左旋转条件
如果当前结点右子树的左子树结点的高度大于右子树的高度
先对当前结点的右子树这个结点进行右旋转
然后对当前结点进行左旋转。
案例分析 a=10,11,7,6,8,9
下面来画图一步步拆解
三、代码实现
rightRotate和leftRoate的具体实现，比上一小节中画的步骤拆解更精简了些，具体见如下代码实现以及注释
#include <cstdlib>
#include <iostream>
using namespace std;
//定义平衡二叉树模版类
template <typename T>
class AVLTree
{
private:
//定义二叉平衡树的结点
struct AVLNode
{
T element; //元素值
AVLNode* left; //左子结点
AVLNode* right; //右子结点
int height; //该结点距离所有可达的叶子结点的最大值
//定义结点的构造方法
AVLNode(const T & theElement, AVLNode *lt,
AVLNode *rt, int h = 0)
: element(theElement), left(lt), right(rt), height(h) {}
};
//根结点对象
AVLNode *root;
/**
* 构造平衡二叉树树
*
* 插入一个值为x的结点到 以t为根结点的树中
*/
void insert(const T & x, AVLNode * & t)
{
//如果插入结点为空，以当前插入的结点为该结点
if(t == NULL)
{
t = new AVLNode(x, NULL, NULL);
}
else if(x < t->element) //如果插入的值小于当前结点的值，进行递归操作，插入到当前结点的左子树中
{
//递归 插入到合适的位置
insert(x, t->left);
//
if(height(t->left) - height(t->right) == 2)
{
rightRotate(t);
}
}
else if(t->element < x) //如果插入的值大于当前结点的值，进行递归操作，插入到当前结点的右子树中
{
insert(x, t->right);
if( height(t->right) - height(t->left) == 2)
{
leftRotate(t);
}
}
else
; // 如果插入的值和当前结点的值相同，不处理。是的结点中的值不重复
// 计算当前结点的height值
t->height = max(height(t->left), height(t->right)) + 1;
cout<<"insert element="<<t->element<<" height="<<t->height<<endl;
}
/**
* Internal method to remove in a subtree.
* x is the item to remove.
* t is the node that roots the subtree.
* Set the new root of the subtree.
*/
void remove(const T & x, AVLNode * & t)
{
if(t == NULL) //no such element
{
return;
}
else if(x < t->element) //find in left subtree
{
remove(x, t->left);
if(height(t->right) - height(t->left) == 2)
{
leftRotate(t);
}
}
else if(t->element < x) //find in right subtree
{
remove(x, t->right);
if( height(t->left) - height(t->right) == 2)
{
rightRotate(t);
}
}
else //delete node *t，
{
if(t->left == NULL)
{
AVLNode* q = t;
t = t->right;
delete q;
}
else if(t->right == NULL)
{
AVLNode* q = t;
t = t->left;
delete q;
}
else
{
t->element = findMax(t->left)->element;
remove(t->element,t->left);
}
}
if(t)
t->height = max(height(t->left), height(t->right)) + 1;
}
/**
* 查找以该结点为根结点的树中 值最小的结点
*/
AVLNode * findMin(AVLNode *t) const
{
if(t == NULL)
return NULL;
if(t->left == NULL)
return t;
return findMin(t->left);
}
/**
* 查找以该结点为根结点的树中 值最大的结点
*/
AVLNode * findMax(AVLNode *t) const
{
if(t != NULL)
while(t->right != NULL)
t = t->right;
return t;
}
/**
* 查找以t为根结点的树中是否右只为x的结点
*/
bool contains(const T & x, AVLNode *t) const
{
if( t == NULL )
return false;
else if( x < t->element )
return contains( x, t->left );
else if( t->element < x )
return contains( x, t->right );
else
return true; // Match
}
/**
* 清空以t为根结点的树
*/
void makeEmpty(AVLNode * & t)
{
if(t != NULL)
{
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
t = NULL;
}
//结点-左子结点-右子结点，没有排序的数组的方式打印
void preOrder(AVLNode *t)const
{
if(t)
{
cout<<t->element<<" ";
preOrder(t->left);
preOrder(t->right);
}
}
//左-中-右，中序遍历，以有序的方式打印
void inOrder(AVLNode *t)const
{
if(t)
{
inOrder(t->left);
cout<<t->element<<" ";
inOrder(t->right);
}
}
/**
* Internal method to print a subtree rooted at t in sorted order.
*/
void printTree(AVLNode *t) const
{
if(t)
{
cout<<"preOrder: "<<endl;
preOrder(t);
cout<<endl;
cout<<"inOrder: "<<endl;
inOrder(t);
cout<<endl;
}
}
/**
* 深copy
*/
AVLNode * clone(AVLNode *t) const
{
if( t == NULL )
return NULL;
else
return new AVLNode(t->element, clone(t->left), clone(t->right), t->height );
}
/**
* 该结点距离所有可达的叶子结点的最大值
*/
int height(AVLNode *t) const
{
return t == NULL ? -1 : t->height;
}
int max(int lhs, int rhs) const
{
return lhs > rhs ? lhs : rhs;
}
/**
* 右旋转
*
* 和上面的流程图稍微有些不同，简化了流程。
* 1. 新建一个结点。把当前结点的
*/
void singleRightRotate(AVLNode * & k2)
{
AVLNode *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max(height(k2->left), height(k2->right)) + 1;
k1->height = max( height(k1->left), k2->height) + 1;
k2 = k1;
}
/**
* 左旋转
*
* 文章中第二小节中的方案也可行。这个是其进行简化
*/
void singleLeftRotate(AVLNode * & k1)
{
//创建一个新结点，把当前结点的右子结点赋值为新结点
AVLNode *k2 = k1->right;
//当前结点的右结点指向 当前结点右子结点的左子结点
k1->right = k2->left;
//新创建的结点的左结点指向当前结点
k2->left = k1;
//计算当前结点和新结点的height
k1->height = max(height(k1->left), height(k1->right)) + 1;
k2->height = max(height(k2->right), k1->height) + 1;
//把新结点指向当前结点
k1 = k2;
}
/**
* 双旋转
* 先左子结点左旋转
* 在父节点右旋转
*/
void doubleWithLeftChild(AVLNode * & k3)
{
singleLeftRotate( k3->left );
singleRightRotate( k3 );
}
/**
* Double rotate binary tree node: first right child.
* with its left child; then node k1 with new right child.
* For AVL trees, this is a double rotation for case 3-RL.
* Update heights, then set new root.
*/
void doubleWithRightChild(AVLNode * & k1)
{
singleRightRotate(k1->right);
singleLeftRotate(k1);
}
/**
* 右旋转
*
* 结点的左子树的height减去右子树的height大于1，要进行调节
* 如果左子树的左子树的height减去左子树的右子树小于等于-1（对于左子树就要在减1），这种情况就要双旋转
* 否则进行单旋转
*/
void rightRotate(AVLNode *& t)
{
AVLNode* lc = t->left;
//1. 如果左子树的左子树的height减去左子树的右子树小于等于-1（对于左子树就要在减1），这种情况就要双旋转
if(height(lc->left) - height(lc->right) == -1)
{
doubleWithLeftChild(t); //先子结点左旋转，再父结点右旋转
}
else
{
singleRightRotate(t); //单右旋转
}
}
/**
* 左旋转
*
* right balance the subtree with root t
* this method can use for both insert and delete
*/
void leftRotate(AVLNode *& t)
{
AVLNode* rc = t->right;
if(height(rc->left) - height(rc->right) == 1)
{
doubleWithRightChild(t); //先子结点右旋转、再父结点左旋转
}
else
{
singleLeftRotate(t); //单左旋转
}
}
public:
AVLTree() : root(NULL){}
AVLTree(const AVLTree & rhs) : root(NULL)
{
*this = rhs;
}
~AVLTree()
{
makeEmpty();
}
/**
* 查找当前树中最小值
*/
const T & findMin() const
{
if(!isEmpty())
{
return findMin(root)->element;
}
}
/**
* 查找当前树中最大值
*/
const T & findMax() const
{
if(!isEmpty())
{
return findMax(root)->element;
}
}
/**
* 查找当前树中是否包含值为x的结点
*/
bool contains(const T & x) const
{
return contains(x, root);
}
/**
* 是否是空树
*/
bool isEmpty() const
{
return root == NULL;
}
/**
* 打印树中所有结点的值
*/
void printTree() const
{
if(isEmpty())
{
cout << "Empty tree" << endl;
}
else
{
printTree(root);
}
}
/**
* 清空结点
*/
void makeEmpty()
{
makeEmpty(root);
}
/**
* 插入值为x的结点到树中
*/
void insert(const T & x )
{
insert(x,root);
}
/**
* 从树中溢出值为x的结点
*/
void remove(const T & x)
{
remove(x,root);
}
/**
* 深copy
*/
const AVLTree & operator=(const AVLTree & rhs)
{
if( this != &rhs )
{
makeEmpty( );
root = clone(rhs.root);
}
return *this;
}
};
int main(int argc, char *argv[])
{
const int N = 3;
AVLTree<int> t;
//insert
t.insert(4);
t.insert(3);
t.insert(6);
t.insert(5);
t.insert(7);
t.insert(8);
cout<<"after insert:"<<endl;
t.printTree();
cout<<endl<<endl;
//remove
t.remove(6);
cout<<"after remove:"<<endl;
t.printTree();
cout<<endl<<endl;
t.makeEmpty();
system("PAUSE");
return EXIT_SUCCESS;
}
四、资料
《算法》
[尚硅谷Java数据结构与java算法（Java数据结构与算法）] : https://www.bilibili.com/video/BV1E4411H73v?p=132
[【C语言描述】《数据结构和算法》（小甲鱼）-二叉排序树] : https://www.bilibili.com/video/BV1jW411K7yg?p=76
[平衡二叉树（C++实现）] : https://blog.csdn.net/qq_39559641/article/details/83720734
[c++ 平衡二叉树的实现] : https://cloud.tencent.com/developer/article/1120359
五、 收获
- 理解二叉查找树存在的问题，以及平衡二叉树对其优化的规则
- 通过画图一步步拆解理解其实现原理
- 代码实现平衡二叉树的左旋转、右旋转、双旋转
看似比较复杂的过程，耐心的拆解其流程，逐步对其实现。就像音视频开发之旅一样，内容系统很庞大，拆分成几个系列，每个系列再细分为具体的知识点，逐一学习实践。因为相信，所以看见。
感谢你的阅读
下一篇我们学习实践该算法系列的最后一篇“散列表”，欢迎关注公众号“音视频开发之旅”，一起学习成长。
欢迎交流
