合工大数据结构09查找研讨.ppt

* 9.3.1 二叉排序树 二叉排序树构造分析： 以下列数据序列作为输入构造一棵二叉排序树。 100，65，88，93，145，118，138，112，188，173，42，78，20，197 平均查找长度： （1＋2×2＋3×4＋4×7）/14 = 45/14 100 65 42 20 78 93 88 118 112 138 173 197 188 145 * 9.3.1 二叉排序树 二叉排序树构造分析： 再看以下列数据序列作为输入构造一棵二叉排序树。 20，42，65，78，88，93，100，112，118，138，145，173，188,197 平均查找长度： （1＋2＋…＋14）/14 = 105/14 20 42 65 78 .... 由此而提出平衡二叉树 * 9.3.1 二叉排序树 二叉排序树删除结点：删除二叉排序树中的结点 可分几种情况来实现 ： 叶子结点 —— 直接删除即可 非叶子结点 顶替法 重新连接法 100 65 42 20 78 93 88 118 112 138 173 197 188 145 删除叶子78 100 65 42 20 93 88 118 112 138 173 197 188 145 删除非叶子42 20 100 65 42 20 78 93 88 118 112 138 173 197 188 145 删除非叶子145 173 * 9.3 树表的查找 9.3.2 平衡二叉树 定义：平衡二叉树是一棵二叉排序树，或者为空， 或者满足以下条件： 1)左右子树高度差的绝对值不大于1； 2)左右子树都是平衡二叉树。 平衡因子： 左子树的高度减去右子树的高度， 显然，在平衡二叉树中， 每个结点的平衡因子的值为-1，0或1。 * 9.3 树表的查找—— 平衡二叉树 如何构造平衡二叉树（ＡＶＬ树） 在平衡的二叉排序树中插入一个结点，当出现不平衡时，根据不平衡情况分四种调整方法 ——假设最低不平衡结点为A，根据新插入结点与A的位置关系来命名调整方法： LL型：新插入结点在A的左孩子(L)的左子树(L)中； LR型：新插入结点在A的左孩子(L)的右子树(R)中； RL型：新插入结点在A的右孩子(R)的左子树(L)中； RR型：新插入结点在A的右孩子(R)的右子树(R)中。 * 9.3 树表的查找—— 平衡二叉树 LL型（图示）： A B C LL型 B C A A B BL BR AR h+2 h LL型 A B BL BR AR * 9.3 树表的查找—— 平衡二叉树 LR型（图示）： A B C LR型 C B A A B BL CL AR h+2 h LR型 A C CR AR C CR B BR CL * 9.3 树表的查找—— 平衡二叉树 RL型（图示）： A B C RL型 C A B A B AL CL BR h h+2 RL型 B C CR BR C CR A AR CL * 9.3 树表的查找—— 平衡二叉树 RR型（图示）： A B C RR型 B A C A B BL BR AR h+2 h RR型 A B BL AR BR * 9.3 树表的查找—— 平衡二叉树构造 [练习]：依次输入下列数据构造一棵平衡二叉树： 100，90，80，60，70，50，120，110，150，87。 100 90 80 LL型 90 80 100 60 70 LR型 90 70 100 60 80 50 LL型 90 70 100 60 80 50 120 110 * 9.3 树表的查找—— 平衡二叉树构造(续1) [练习]：依次输入下列数据构造一棵平衡二叉树： 100，90，80，60，70，50，120，110，150，87。 90 70 100 60 80 50 120 110 RL型 90 70 110 60 80 50 100 120 150 RR型 70 60 50 110 90 80 100 120 150 * 9.3 树表的查找—— 平衡二叉树构造(续2) [练习]：依次输入下列数据构造一棵平衡二叉树： 100，90，80，60，70，50，120，110，150，87。 70 60 50 110 90 80 100 120 150 87 RL型 70 60 50