音视频开发之旅(28) 算法序列 - 平衡二叉树

2016-05-26

目录

  1. 平衡二叉树

  2. 左旋转、右旋转、双旋转的原理

  3. 代码实现

  4. 资料

  5. 收获

上一篇我们学习实践了二叉查找树,其结合了链表的灵活性和二分查找的高效性。但是可能会出现左右子树的深度不一致或者差别很大,最差的情况是只有一系列的左/右子树,插入和删除速度没有影响,但查询操作将会很慢。


对应的解决解决方案就是平衡二叉树

一、平衡二叉树(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

五、 收获

  1. 理解二叉查找树存在的问题,以及平衡二叉树对其优化的规则

  2. 通过画图一步步拆解理解其实现原理

  3. 代码实现平衡二叉树的左旋转、右旋转、双旋转

看似比较复杂的过程,耐心的拆解其流程,逐步对其实现。就像音视频开发之旅一样,内容系统很庞大,拆分成几个系列,每个系列再细分为具体的知识点,逐一学习实践。因为相信,所以看见。

感谢你的阅读

下一篇我们学习实践该算法系列的最后一篇“散列表”,欢迎关注公众号“音视频开发之旅”,一起学习成长。

欢迎交流


相关文章

544,剑指 Offer-平衡二叉树

2021-09-22
问题描述输入一棵二叉树的根节点,判断该树是不是平衡二叉树.如果某二叉树中任意节点的左右子树的高度相差不超过1,那么它就...

红黑树、自平衡二叉树、AVL树、B树的比较

2021-09-22
1. 红黑树和自平衡二叉(查找)树区别1.红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下...

python——有序表生成平衡二叉树

2021-09-22
print("生成的平衡二叉树为:", tree) print("树的顶点:", entry(tree)) print("树的左子树:", left_branch(tree))...

程序员面试之必考题(三):平衡二叉树的基本概念

2021-09-22
平衡二叉树是二叉树的一种应用,在介绍平衡二叉树之前,首先来看一看什么是二叉排序树. 二叉排序树二叉排序树(BST)或者是一...

不怕面试被问了!二叉树算法大盘点 | 原力计划

2021-09-22
树是一种平衡二叉树,平衡二叉树递归定义如下:左右子树的高度差小于等于 1.其每一个子树均为平衡二叉树.为了保证二叉树的平...

有图有真相!平衡二叉树AVL实现

2021-09-22
平衡二叉树(AVL),是一个二叉排序树,同时任意节点左右两个子树的高度差(或平衡因子,简称BF)的绝对值不超过1,并且左右...

【数据结构】平衡二叉树(AVL树)

2021-09-22
平衡二叉树(AVL树):它或者是一棵空树;或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树...

如何使用 JavaScript 实现二叉树,二叉平衡树和红黑树

2021-09-22
包含二叉树,二叉查找树,平衡二叉查找树(AVL树,红黑树),均已es6语法实现.查阅前默认你已经具备树相关的的基本概念,如...

Go 数据结构和算法篇(十八):平衡二叉树

2021-09-22
平衡二叉树要求每个节点的左子树和右子树的高度差至多等于 1,这个高度差的值叫做平衡因子 BF,也就是说 BF 的值不能大于1,否...

leetcode | 110.平衡二叉树

2021-09-22
本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 . 示例输入:root = [3,9,20,...

随机推荐

PHP面试100题汇总【81-100题】

2020-09-02
//得到/phpinfo.php参考server.php http://lesson.com/test/server.php?id=184、写出session的运行机制.session创建时,是否会在服务端...

如何自学软件编程?零基础自学编程入门指南

2020-08-01
基础自学编程入门指南 一:确定一个方向,编程语言太多了:java、C++、python、PHP、C等,需要确定方向,从基础学起,小编建...

PHP代码优化24条真经

2020-05-01
echo比print快.使用echo的多重参数代替字符串连接.在执行for循环之前确定最大循环数,不要每循环一次都计算最大值,最好运用foreach代替.

好课分享:从原理到场景 系统讲解PHP缓存技术,网盘下载

2020-04-13
为你准备好了:我们组织了很多爱好学习的伙伴,一起组建了社群每日共享全网好课,期待你的加入~百度云网盘下载 ,爱好此款网课...

explode:爆炸

2020-01-18

皋兰新闻

2016-01-20
内容提要2021年2月4日(农历十二月廿三)星期四1、胡俊锋副市长来皋督查节前安全生产工作 ;2、中共石洞镇第十五届代表大会第...

82% 用户仍在使用 Java 8,这对 Java 10 意味着什么?

2015-10-03
转自:开源中国Java 10 发布之后,不少开发者纷纷发声:Java 迭代太快了,我还停留在 Java 5,6,7,8......呢!相关阅读:如约而至,...

(今夕荷夕)荷兰新闻短平快(宜家召回巧克力产品等)— 7月28日

2015-09-30
GODIS CHOKLADKROKANT和CHOKLAD LINGON & BLABÄR可能含有牛奶和坚果; CHOKLAD LJUS、CHOKLAD NÖT 和GODIS ...

【21考研】这所广东名校由408改考数据结构,复试数据库!

2015-04-24
(04)911数据结构复试笔试课程:(01)C程序设计参考资料:【2019更新版】南京审计大学计算机软件考研信息汇总中国人民大学...

二级房建资质转让需要规避哪些风险?

2015-01-03
避免没有调查清楚转让方情况 二级房建资质是建筑企业立足房建工程市场的根本,资质办理、升级难度大、要求高,如果不是因为迫不得已的情况...避免不了解当地政策,盲目办理转让 二级房建资质转让,特别是跨地区转让特别需要注意的是...避免签订内容不详的转让合同 二级房建资质转让涉及金额较大,办理流程较为复杂,所以一定要在资质转让协议中,明确好各项事宜...