查找概论3-平衡二叉树AVL
2014-08-08 本文已影响183人
eesly_yuan
概念
- 平衡二叉树：是一种二叉排序树，且其每一个节点的左子树与右子树的高度差<=1；
- 平衡因子（balance factor,BF)：节点的左子树与右子树的高度差，对于平衡二叉树只有可能是-1,0,1。
- 插入一个节点导致平衡二叉树失衡，距离这个插入节点最近的，且平衡因子绝对值大于1的节点为根的子树，称为最小不平衡子树，这个概念在构建平衡二叉树的时候很重要。
平衡二叉树构建
- 原理：在不断插入的过程中，若某一次导致失衡则，寻找最小不平衡子树，若其BF大于1则右旋，小于-1则左旋。若最小不平衡子树的BF和其子树的BF符号相反，则先将其子树进行一次反向旋转后，再按照上述规则对最小不平衡子树进行旋转。
- 算法实现：节点数据结构定义如下
struct BFNode
{
int data,BF;
BFNode * lhs,*rhs;
};
右、左旋操作如下图所示
void R_rotate(BFNode * T)
{
BFNode * Tl = T->lhs;
T->lhs = Tl->rhs;
Tl->rhs = T;
T = Tl;
}
void L_rotate(BFNode * T)
{
BFNode * Tr = T->rhs;
T->rhs = Tr->lhs;
Tr->lhs = T;
T = Tr;
}
右旋.jpg
2.jpg
具体的左平衡右平衡，还需要对BF进行相应的调整,具体过程参考
红黑树
- 红黑树，是一种二叉查找树，满足二叉查找树的一般性质。
1.在一棵二叉查找树上，执行查找、插入、删除等操作的最佳时间复杂度为O（logn）。
2.但若退化为一棵具有n个结点的线性链，则此些操作最坏情况运行时间为O（n）。
- 红黑树，能保证在最坏情况下，基本的动态几何操作的时间均为O（logn）。每个结点内含五个域，color，key，left，right。如果相应的指针域没有，则设为NULL。一棵红黑树是指一棵满足下述性质的二叉搜索树（BST, binary search tree）：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。 - 红黑树的统计效率是指：对于随机数据，它进行平衡旋转的次数少，因为它对于平衡的要求没那么严格。这一点提升了插入删除的性能。不过，如果插入数据是顺序数据，红黑树实际会差点。另外，对于查找性能，红黑树总是比AVL差一点，因为它的平均搜索深度会大一些。
- 一些别人的测试数据结果：AVL树在顺序插入和删除时有20%左右的性能优势，但随机性能反而落后15%左右，现实应用当然一般都是随机情况，所以红黑树得到了更广泛的应用。对AVL树和红黑树的个人理解
- 红黑树可以参考C#与数据结构--树论--红黑树（RED BLACK TREE）
Size Balanced Tree SBT
- Size Balanced Tree(简称SBT)是一种平衡二叉搜索树，它通过子树的大小s[t]来维持平衡性质。它支持很多动态操作，并且都能够在O(log n)的时间内完成。SBT
