本节内容 1. 平衡二叉树的定义 2.平衡化旋转 3.平衡二叉排序树的插入操作 昆山爱达人信息技术有限公司

Presentation on theme: "本节内容 1. 平衡二叉树的定义 2.平衡化旋转 3.平衡二叉排序树的插入操作 昆山爱达人信息技术有限公司"— Presentation transcript:

1 本节内容 1. 平衡二叉树的定义 2.平衡化旋转 3.平衡二叉排序树的插入操作 昆山爱达人信息技术有限公司 www.bcdaren.com
QQ: 本节内容 1. 平衡二叉树的定义 2.平衡化旋转 3.平衡二叉排序树的插入操作

2 昆山爱达人信息技术有限公司 QQ: 平衡二叉树的定义 平衡二叉树的定义 平衡二叉树(balanced binary tree)是由阿德尔森一维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。 定义：平衡二叉树一种满足下面性质的二叉树 （1）是一棵空树或满足（2）、（3）的非空二叉树 （2）左子树和右子树深度之差的绝对值不大于1 （3）左子树和右子树也都是平衡二叉树

3 昆山爱达人信息技术有限公司 QQ: 平衡二叉树的定义 平衡二叉树的定义 平衡因子(Balance Factor):二叉树上结点的左子树的深度减去右子树的深度称为该结点的平衡因子。 因此，平衡二叉树上每个结点的平衡因子只可能是-1,0和1,否则，只要有一个结点的平衡因子的绝对值大于1，该二叉树就不是平衡二叉树。 如果一棵二叉树既是二叉排序树又是平衡二叉树称为平衡二叉排序树

4 昆山爱达人信息技术有限公司 QQ: 平衡二叉树的定义 平衡二叉树的定义

5 昆山爱达人信息技术有限公司 QQ: 平衡化旋转 平衡二叉树的旋转

6 昆山爱达人信息技术有限公司 QQ: 平衡化旋转 平衡二叉树的旋转 可见，一般的二叉排序树是不平衡的，需要对二叉排序树进行修正使其即保持有序性，又具有平衡性。这种修正的方法称为平衡化旋转。 在对AVL树进行插入和删除一个结点后，通常会影响到从根结点到插入（或删除）结点的路径上的某些结点。这些结点的子树可能发生变化。以插入结点为例,影响有如下可能： 1.某些结点深度发生了变化 2.某些结点平衡因子发生了变化 3.某些结点失去平衡

7 昆山爱达人信息技术有限公司 QQ: 平衡化旋转 LL型平衡化旋转

8 昆山爱达人信息技术有限公司 QQ: 平衡化旋转 RR型平衡化旋转

9 昆山爱达人信息技术有限公司 QQ: 平衡化旋转 LR型平衡化旋转

10 平衡化旋转 RL型平衡化旋转 以上的平衡化旋转的规则可以保证二叉排序树的次序不变 昆山爱达人信息技术有限公司 www.bcdaren.com
QQ: 平衡化旋转 RL型平衡化旋转 以上的平衡化旋转的规则可以保证二叉排序树的次序不变

11 平衡二叉排序树的插入操作 平衡二叉排序树的插入操作 平衡二叉排序树的插入操作是在二叉排序树的基础上完成以下工作：
昆山爱达人信息技术有限公司 QQ: 平衡二叉排序树的插入操作 平衡二叉排序树的插入操作 平衡二叉排序树的插入操作是在二叉排序树的基础上完成以下工作： 1.判断插入结点后的二叉排序树是否产生不平衡 2.找出失去平衡的最小子树 3.判断旋转类型，然后做相应调整

12 平衡二叉排序树的插入操作 平衡二叉排序树的插入操作 算法思想： 1.按照二叉排序树的定义，将结点s插入
昆山爱达人信息技术有限公司 QQ: 平衡二叉排序树的插入操作 平衡二叉排序树的插入操作 算法思想： 1.按照二叉排序树的定义，将结点s插入 2.在查找结点s的插入位置的过程中，记录离结点s最近且平衡因子不为0的结点a,若该结点不存在，则结点a指向根结点 3.修改结点a到结点s路径上所有结点的平衡因子 4.判断是否产生不平衡，若不平衡，则确定旋转类型并做相应调整

13 平衡二叉排序树的插入操作 平衡二叉排序树的插入操作 演示： 昆山爱达人信息技术有限公司 www.bcdaren.com
QQ: 平衡二叉排序树的插入操作 平衡二叉排序树的插入操作 演示：