数据结构——平衡二叉树（AVL）

数据结构——平衡二叉树（AVL）

​​平衡二叉树​​

​​定义​​​​存储结构​​​​平衡旋转​​

​​LL平衡旋转​​​​RR平衡旋转​​​​LR平衡旋转​​​​RL平衡旋转​​​​旋转操作特点​​

​​平衡二叉树插入算法思想​​​​平衡二叉树的查找性能分析​​

​​变种的AVL树——红黑树​​

平衡二叉树

世界需要平衡，破坏平衡的一方，也许会一时很强势的称霸，最终的结局逃不过孤立和落空

定义

左、右子树是平衡二叉树；所有结点的左、右子树深度之差的绝对值≤ 1

平衡因子:该结点左子树与右子树的高度差

任一结点的平衡因子只能取：-1、0 或 1；如果树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树就失去平衡，不再是AVL树；对于一棵有n个结点的AVL树，其高度保持在O(log2n)数量级，ASL也保持在O(log2n)量级。

存储结构

typedef struct BSTNode{ ElemType data; int bf; // 平衡因子 struct BSTNode* lchild, *rchild; } BSTNode, *BSTree;

平衡旋转

LL平衡旋转

在单向右旋平衡处理后BF(B)由1变为0，BF(A)由2变为0。

RR平衡旋转

在单向左旋平衡处理后BF(B)由-1变为0，BF(A)由-2变为0。

LR平衡旋转

LR型：在3的左子树根节点1的右子树上插入节点2导致不平衡，可使用双向旋转：先使其子树左旋再整棵树右旋，可记为左右->左右。

在双向旋转平衡处理后BF(A)由2变为-1，BF(B)由-1变为0，BF©由1变为0。

RL平衡旋转

RL型：在19的右子树根节点25的左子树上插入节点23导致不平衡，可使用双向旋转：先使其子树右旋再整棵树左旋，可记为右左->右左

在双向旋转平衡处理后BF(A)由-2变为0，BF(B)由1变为-1,BF©由1变为0。

旋转操作特点

对不平衡的最小子树操作。旋转后子树根节点平衡因子为0。旋转后子树深度不变故不影响全树，也不影响插入路径上所有祖先结点的平衡度。

依次插入的关键字为5, 4, 2, 8, 6, 9

平衡二叉树插入算法思想

若是空树，插入节点作为根节点，树深度加1。插入节点key值等于根节点key值，则不插入。插入节点key值小于根节点key值，插入在左子树上，左子树深加1并且：

插入节点key值大于根节点key值，插入在右子树上，方法类似

平衡二叉树的查找性能分析

在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡 树的深度。

在二叉平衡树上进行查找时， 查找过程中和给定值进行比较的关键字的个数和 log(n) 相当。

变种的AVL树——红黑树

颜色特征：每个结点为“黑色”或“红色”根特征：根结点永远是“黑色”的外部特征：扩充外部叶结点都是空的“黑色”结点内部特征：“红色”结点的两个子结点都是“黑色”的，即：不允许两个连续的红色结点深度特征：对于每个结点，从该结点到其所有子孙叶结点的路径中所包含的黑色结点数量必须相同

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。