当前位置:C++技术网 > 资讯 > 教你如何快速学会数据结构中平衡二叉排序树

教你如何快速学会数据结构中平衡二叉排序树

更新时间:2016-04-24 21:19:05浏览次数:1+次

在这里感谢《平衡二叉树(解惑)》的作者,不得不说,我也是从这篇文章里面学会的。
下面,我们进入正题:
有四种平衡二叉树,分别是LL,RR,LR,RL型四种,下面,我将借鉴上面我提到过的作者的图片来讲解:

对于LL型的平衡二叉树,其旋转是这么判断的,左边的图,以a为轴,将x顺时针转动,构成平衡二叉树,右边的图也是以a为轴,将x顺时针旋转,而原来的a的右子树变成了x的左子树。(x是插入的数据元素y的最近的不平衡二叉树的树结点)

对于RR型的平衡二叉树,其旋转是这么判断的。两边的图都是以a为旋转轴,x逆时针旋转,而右边的图a的左子树,变成了x的右子树。

对于LR型的平衡二叉树,其旋转需要经过两次(两张图都是一样的旋方向)。先是以a为轴,将y逆时针旋转,然后,以y为轴,将x顺时针转动。右边的图,c的右子树y变成了x的左子树。

对于RL型的平衡二叉树,其旋转是这么判断的(两张图都是一样的旋方向)。先是以a为轴顺时针,而后以y为轴逆时针旋转。右边的图,c的右子树y变成了a的左子树。
那么如何来判断平衡二叉树是哪种型别?很简单,首先,我们看离插入点最近的不平衡二叉树(x)的结点的平衡因子,而后就是结点b的平衡因子来判断。结点x的平衡因子为2,x的左孩子a的平衡因子为1,应采用LL型;若,a的平衡因子是-1,则表示是LR型。结点x的平衡因子为-2,x的右孩子a的平衡因子为-1,应采用RR型;若,a的平衡因子是1,则表示是RL型。