第二十六讲-2 平衡二叉树B树B+树.ppt

* 滨州学院计算机科学技术系 B+树的结构特点： ※ 每个叶子结点中含有 n 个关键字和 n 个指向记录的指针；并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点； * 滨州学院计算机科学技术系 ※ 每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值； ※ 所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 ?m/2?和 m 之间。 * 滨州学院计算机科学技术系 查找过程 ※在 B+ 树上，既可以进行缩小范围的查 找，也可以进行顺序查找； ※ 在进行缩小范围的查找时，不管成功 与否，都必须查到叶子结点才能结束； ※若在结点内查找时，给定值≤Ki， 则 应继续在 Ai 所指子树中进行查找。 * 滨州学院计算机科学技术系 插入和删除的操作 类似于B-树进行，即必要时，也需要进行结点的“分裂”或“归并”。 * 滨州学院计算机科学技术系 50 96 15 50 62 78 96 71 78 84 89 96 56 62 20 26 43 50 3 8 15 sq root 滨州学院计算机科学技术系 数据结构 系内数据结构学习网站： 00:8080/ds 滨州学院计算机科学技术系 * 滨州学院计算机科学技术系 第九章 查 找 平衡二叉树 * 滨州学院计算机科学技术系 本讲内容 平衡二叉树 概念 基本操作 查找 插入 建立 性能分析 B-树 概念 查找 * 滨州学院计算机科学技术系 平衡二叉树 何谓“二叉平衡树”？ 二叉平衡树的查找性能分析 如何建立“二叉平衡树”？ * 滨州学院计算机科学技术系 平衡二叉树（AVL树）的定义 一棵AVL树或者是空树，或者是具有下列性质的二叉树：它的左子树和右子树都是AVL树，且左子树和右子树的高度之差的绝对值不超过1。 高度不平衡的二叉排序树 高度平衡的二叉排序树 * 滨州学院计算机科学技术系 二叉平衡树的特点为： 树中每个结点的左、右子树深度之差的绝对值不大于1 给每个结点附加一个数字，为该结点左子树的高度减去右子树的高度所得的差。这个数字即为结点的平衡因子(Balance Factor )。 根据AVL树的定义，任一结点的平衡因子只能取 -1，0和 1。 * 滨州学院计算机科学技术系 如何建立平衡二叉树？ 如果一棵二叉排序树是高度平衡的，它就成为 AVL树。如果它有 n 个结点，其高度可保持在O(logn)，平均查找长度也可保持在O(logn)。 * 滨州学院计算机科学技术系 平衡化旋转-1 如果在一棵平衡的二叉排序树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。 平衡化旋转有两类： 单旋转 (左旋和右旋) 双旋转 (左平衡和右平衡) * 滨州学院计算机科学技术系 每插入一个新结点时，AVL树中相关结点的平衡状态会发生改变。因此，在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子(左、右子树的高度差)。如果在某一结点发现高度不平衡，停止回溯。 平衡化旋转-2 * 滨州学院计算机科学技术系 从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。 如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转，其中一个是另一个的镜像，其方向与不平衡的形状相关。 如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。 平衡化旋转-3 * 滨州学院计算机科学技术系 左单旋转 (RotateLeft ) h h h A C E B D (a) (b) (c) h h h + 1 B A C E D h h h + 1 C E A B D 如果在子树E中插入一个新结点，该子树高度增1导致结点A的平衡因子变成+2，出现不平衡。 沿插入路径检查三个结点A、C和E。它们处于一条方向为“\”的直线上，需要做左单旋转。 以结点C为旋转轴，让结点A反时针旋转。 -1 -2 0 -1 0 0 * 滨州学院计算机科学技术系 右单旋转 (RotateRight ) h h h A C E B D (a) (b) (c) h h + 1 B A C E D h h h + 1 C E A B D 在左子树D上插入新结点使其高度增1，导致结点A的平衡因子增到 -2，造成了不平衡。 为使树恢复平衡，从