Day7：查找——Part3：树型查找 1.二叉排序树 1）二叉排序树的定义 二叉排序树：具有以下特性的二叉树①若左子树非空，则左子树上所有结点的值均小于根结点的值②若右子树非空，则右子树上所有结点的值均大于根节点的值③左、右子树也分别是一棵二叉排序树 左子树结点值<根结点值<右子树结点值 2）二叉排序树的查找 算法(非递归)： 3）二叉排序树的插入 二叉排序树作为一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字值等于给定值的结点时再进行插入的。 算法描述： 4）二叉排序树的构造 算法： 5）二叉排序树的删除 ①若被删除的结点z是叶结点，则直接删除，不会破坏二叉排序树的性质②若结点z只有一棵左子树或者右子树，则让z的子树称为z父结点的子树，替代z的位置③若结点z有左右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。 6）二叉排序树的查找效率分析 二叉排序树的查找效率主要取决于树的高度。 2.平衡二叉树 1）平衡二叉树的定义 平衡二叉树（平衡树）：二叉排序树的左、右子树高度之差的绝对值不超过1.平均查找长度为O(log2(n))。平衡因子：定义结点左子树和右子树的高度差。 2）平衡二叉树的插入 保证平衡的基本思想：每当在二叉排序树中插入（或删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作导致了不平衡。若导致了不平衡，则先找到插入路径上离插入节点最近的平衡因子的绝对值大于1的结点A,再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。 调整的规律：①LL旋转（右单旋转）：在结点A的左孩子B的左子树上插入新结点，将A的左孩子B向右上旋转替代A作为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。②RR旋转（左单旋转）：在结点A的右孩子B的右子树上插入新结点，将A的右孩子B向左上旋转替代A作为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。③LR平衡旋转（先左后右双旋转）：在结点A的左孩子的右子树上插入新结点，将A的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后把该C结点向右上旋转到A的位置。④RL平衡旋转（先右后左双旋转）：在结点A的右孩子的左子树上插入新结点，将A的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后把该C结点向左上旋转到A的位置。 3）平衡二叉树的删除 步骤（以删除结点w为例）：①用二叉排序树的方法对结点w执行删除操作②从结点w开始，向上回溯，找到第一个不平衡的结点z（即最小不平衡子树）；y为结点z的高度最高的孩子结点；x为结点y的高度最高的孩子结点③然后对以z为根的进行平衡调整，其中x、y、z可能的位置有四种情况：1.y是z的左孩子，x是y的左孩子（LL）2.y是z的左孩子，x是y的右孩子（LR）3.y是z的右孩子，x是y的右孩子（RR）4.y是z的右孩子，x是y的左孩子（RL） 4）平衡二叉树的查找 含有n个结点的平衡二叉树的最大深度为O(log2(n))，因此平衡二叉树的平均查找长度为O(log2(n))。 查找过程与二叉排序树的相同。 3.红黑树 1）红黑树的定义 红黑树：满足红黑性质的二叉排序树①每个结点或是红色或是黑色的②根结点是黑色的③叶结点（虚构的外部结点、NULL结点）都是黑色的④不存在两个相邻的红结点（红结点的父结点和孩子结点都是黑色的）⑤对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数量相同。 引入的目的：为了保持AVL树的平衡性，插入和删除操作后，非常频繁地调整全树整体拓扑结构，代价较大。为此在AVL树的平衡标准上进一步放宽条件，引入红黑树的结构。 黑高：从某结点出发（不含该结点）到达一个叶结点的任一简单路径上的黑结点总数。根结点的黑高称为称为红黑树的黑高。 结论1：从根到叶结点的最长路径不大于最短路径的2倍结论2：有n个内部结点的红黑树的高度h≤2log2(n+1) 2）红黑树的插入 结论3：新插入红黑树中的结点初始着红色 插入过程（以z为例）：①用二叉查找树插入法插入，并将结点z着为红色。若结点z的父结点是黑色的，无须做任何调整，此时就是一颗标准的红黑树②若z是根结点，将z着为黑色（树的黑高增1），结束③若结点z不是根结点，，并且z的父结点z.p是红色的，则分为三种情况，区别在于z的叔结点y的颜色不同，因为z.p是红色的，插入前的树是合法的，根据性质②和④，爷结点z.p.p必然存在且为黑色。性质④只在z和z.p之间被破坏了。情况1：z的叔结点y是黑色的，且z是一右孩子（LR）情况2：z的叔结点y是黑色的，且z是一左孩子（LL）情况3：z的叔结点y是红色的（无影响） 3）红黑树的删除 删除一个节点的情况：①待删结点没有孩子②待删结点只有右子树或左子树 ①若待删结点只有右子树或左子树，则只有两种情况。子树只有一个结点，且必然是红色的，否则会破坏性质⑤②若待删结点没有孩子，若该结点是红色的，直接删除，无须做调整。③若待删结点没有孩子，且该结点是黑色的。任务变成将双黑结点恢复为普通结点。情况1：x（x是用来替换y的结点，双黑结点）的兄弟结点w为红色（先左旋）情况2：x的兄弟结点w是黑色的，w的左孩子是红色的，右孩子是黑色的（RL）情况3：x的兄弟结点w是黑色的，w的右孩子是红色的（RR）情况4：x的兄弟结点w是黑色的，且w的两个孩子是黑色的
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/87008.html
