iis7.5搭建网站,wordpress相册展示插件,青岛的网站设计公司,当前主流的网络营销方式对于二叉搜索树 #xff0c; 平衡二叉树 #xff0c; 以及红黑树 #xff0c; 目前只需要了解背后的原理 #xff0c; 不做代码实现的要求 #xff0c; 重要的就是了解各种操作的时间复杂度即可 #xff0c; 为set 与 map 做铺垫 一、二叉搜索树
1.1 基本概念 相较与于堆… 对于二叉搜索树 平衡二叉树 以及红黑树 目前只需要了解背后的原理 不做代码实现的要求 重要的就是了解各种操作的时间复杂度即可 为set 与 map 做铺垫 一、二叉搜索树
1.1 基本概念 相较与于堆二叉搜索树是大小关系更为严格的数据结构。但是并不需要必须是⼀棵完全二叉树也就是树的形态是任意的。如下图所示都是二叉搜索树 构造一棵二叉搜索树的目的 并不是为了排序而是为了提高查找和输入删除关键字的速度。 1.2 查找操作 二叉搜索树的查找是从根结点开始 沿某个分支逐层向下比较的过程若二叉搜索树非空先将给定值与根结点的关键字比较若相等则查找成功若不等如果小于根结点的关键字则在根结点的左子树上查找否则在根结点的右子树上查找。二这也是⼀个递归的过程。 根据BST的特性左 根 右 ) 从根结点开始一路向下找 最坏情况下会从根节点开始查找到叶子结点。因此时间复杂度是和树的高度有关的而树高最差会 变成一条单链表因此时间复杂度为 O(N) 1.3 插入操作 根据BST的特性左 根 右 ) 从根结点开始一路向下找找到合适的位置就直接插入 插入与查找的过程一致因此时间复杂度为 O(N) 1.4 构造 BST 树 二叉搜索树的构建就是不断向原来的树中插入新的结点即可。 根据序列 a {51, 68, 59, 27, 25, 33, 75, 70} 构造⼀棵二叉排序树 所以时间复杂度最优的情况下是 O(logN) 根据序列 a {25, 27, 33, 59, 75, 51, 70, 68} 构造⼀棵二叉排序树 在极端条件下 时间复杂度为 O(N) --- oh my god ! 骤增了 在上面两个构造二叉排序树的过程中 虽然结点的值都相同 不同的构造顺序会有不同的二叉搜索树 会影响查找和插入的效率 。 并且 构造序列越有序 二叉搜索树的查找效率就越低 。 1.5 删除操作 对于第三个删除结点的情况 我们一般是把它变成情况一或二
1若被删除结点是叶子结点则直接删除
---- 此时依旧会保持二叉搜索树的性质 2若被删除结点只有左子树或者右子树让左子树或者右子树替代 ---- 此时依旧会保持二叉搜索树的性质 3若被删除结点有左子树和右子树 删除 50 这个结点并用直接前驱来替代 删除 50 这个结点并用直接后继来替代 删除10这个结点 注意我们创建二叉搜索树其实并不是为了排序 而是为了快速插入、删除 以及查找元素。因为BST不是那么极端的话 树高维持在 logN 的范围 上述的各种操作其实是很快的 。 但是二叉搜索树的特性并不杜绝极端情况的出现 二、平衡二叉树 在介绍二叉搜索树的时候 在某些特定的情况下 二叉搜索树是会退化成单链表 并且各种操作的效率也会明显下降 。因此我们需要一些特别的手段保证这个二叉搜素树的“平衡”进而保证各种操作的效率 。 2.1 基本概念 平衡二叉树 也称AVL树 它是具有以下性质的二叉搜索树 1 左右子树的高度差的绝对值不超过1 2 左右子树分别也是平衡二叉树 如下图所示 结点上方的数字表示平衡因子 。 左图是一棵平衡二叉树右图不是 2.2 查找操作 平衡二叉树的查找 、 插入 以及 删除操 作基本上与二叉搜索树一致 但是需要处理操作之后的“失衡” 。 重点需要掌握两种处理失衡的操作 1 左旋 2 右旋 由于平衡二叉树会限制树的高度不会过高 趋近于 log n 级别 因此时间复杂度为 O(logN 左旋结点1的时候遇到结点2 “挡着了” 1 结点1 成为右孩子的左子树 2 右孩子原本的左子树结点2成为该结点结点1的右子树 右旋结点1的时候遇到结点2 “挡着了” 1 结点1 成为左孩子的右子树 2 左孩子原本的右子树结点2成为该结点结点1的左子树 2.3 插入操作 最小不平衡子树 在⼆叉搜索树中插入新结点之后插入路径的点中可能存在很多平衡因子的绝对值大于 1 的此时找到 距离插入结点最近的不平衡的点 以这个点为根的 子树 就是 最小不平衡子树 。 2.3.1 LL型 - 右单旋 LL 表示 新结点由于插入在 T 结点的左孩子(L)的左子树(LL)中 从而导致失衡。如下图所示 T失衡了 --- 让失衡点右旋 案例 2.3.2 RR型 - 左单旋 RR 表示新结点由于插入在 T 结点的右孩子(R)的右子树(RR)中从而导致失衡。如下图所示 T失衡了--- 让失衡点左旋 案例 2.3.3 LR型 - 左右双旋 LR 表示新结点由于插入在 T 结点的左孩子(L)的右子树(LR)中从而导致失衡。如下图所示 T失衡了 --
1 失衡点左孩子左旋
2 失衡点右旋 案例 2.3.4 RL型 - 右左双旋 RL 表示新结点由于插入在 T 结点的右孩子(R)的左子树(RL)中从而导致失衡。如下图所示 T失衡了 --
1 失衡点的右孩子右旋
2 失衡点左旋 案例 2.4 构造ALV树 平衡二叉树的构造 就是不断向数中插入新的结点 根据序列 a {15, 6, 10, 17, 11, 13, 9, 20, 16, 22} 构造一棵二叉排序树 2.5 删除操作 与插入操作的思想类似都是先按照二叉搜索树的形式操作然后想办法使其平衡。具体步骤 删除结点的时候 调整可能不止一次 因为插入的时候我们是从根结点开始查找合适的插入位置 是符合BST的特性 但是删除操作的时候 是随机的 。 例一删除 30 叶子结点直接删除删除之后向上到根节点所有结点都没有失衡直接结束。 例二删除 10 第⼀次调整从 10 向上找第⼀个不平衡子树是以 49 为根的子树高度最高的儿子是 59高度最高的孙子是 69呈现右孩子右孩子因此仅需对 59 左旋⼀次。 没有第二次调整了因为所有都已经平衡了 例三删除 57 第⼀次调整从 57 向上找第⼀次出现的不平衡子树是以 49 为根的子树高度最高的儿子是 45高度最高的孙子是 47呈现左孩子右孩子因此需要让 47 左旋⼀次然后再右旋⼀次 第二次调整从 47 向上找发现 59 失衡找到最高的孩子为 69 号结点最高的孙子为 76 号结 点呈现的关系是右孩子右孩子因此将 69 左旋⼀次 调整结束因为已经到了根结点并且根节点是平衡的。
