网站设置怎么删除,揭东建设局网站,服务器是什么设备,网站平台建设是什么1.树、二叉树 2.二叉查找树 3.平衡二叉树、红黑树 4.递归树
一#xff0c;什么是“平衡二叉查找树”
1#xff0c;定义#xff1a;二叉树中任意一个节点的左右子树的高度相差不能大于1。 所以#xff1a;完全二叉树#xff0c;满二叉树都是平衡二叉树#xff0c;非完全…1.树、二叉树 2.二叉查找树 3.平衡二叉树、红黑树 4.递归树
一什么是“平衡二叉查找树”
1定义二叉树中任意一个节点的左右子树的高度相差不能大于1。 所以完全二叉树满二叉树都是平衡二叉树非完全二叉树也有可能是平衡二叉树。 2平衡二叉查找树不仅满足上面平衡二叉树的定义还满足二叉查找树的特点。
3发明平衡二叉查找树这类数据结构的初衷是解决普通二叉查找树在频繁的插入删除等动态更新的情况下出现时间复杂度退化的问题。 所以平衡二叉查找树中“平衡”的意思其实就是让整棵树左右看起来比较“对称”比较“平衡”不要出现左子树很高右子树很矮的情况。这样就能让整颗树的高度相对低一些相应的插入删除查找等操作的效率高一些。
4若设计一个新的平衡二叉查找树只要树的高度不比log2n大很多如树的高度仍然是对数量级的尽管它不符合严格的平衡二叉查找树的定义但它仍然可以被认为是一个合格的平衡二叉查找树。
二如何定义一棵“红黑树”
1平衡二叉查找树有很多如Splay Tree(伸展树)Treap树堆等但是我们提到平衡二叉查找树听到的基本都是红黑树。他的出境率甚至要高于“平衡二叉查找树”这几个字甚至在有些时刻默认平衡二叉查找树就是红黑树
2红黑树英文“Red-Black-Tree”简称R-B Tree有如下特性 它是一种不严格的平衡二叉查找树。 红黑树中的节点一类别标记为黑色一类被标记为红色。
根节点是黑色的每个叶子节点都是黑色的空节点NIL,也就是说叶子节点不存储数据任何相邻的节点都不能同时为红色即红色节点都是被黑色节点隔开的每个节点从该节点到达其可达叶子节点的所有路径都包含相同数目的黑色节点
3二叉查找树很多操作的性能都跟树的高度成正比一课极其平衡的二叉树满二叉树或完全二叉树的高度大约是log2n,所以要证明红黑树是近似平衡的我们只需要分析红黑树的高度是否比较稳定地趋近log2n就好 。
4红黑树的高度分析 ①首先若将红色节点从红黑树中去除那单纯包含黑色节点的红黑树的高度比包含相同节点个数的完全二叉树的高度要小。所以去掉红色节点的“黑树”的高度也不会超过log2n。 ②在红黑树中红色节点不能相邻即有一个红色节点就要至少有一个黑色节点将它更其他红色节点隔开。 红黑树中包含最多黑色节点的路径不会超过log2n,所以加入红色节点之后最长路径不会超过2log2n即红黑树的高度近似2log2n ③红黑树的高度只比高度平衡的AVL树的高度log2n仅仅大了一倍在性能上下降的并不多。
三工程中大家都喜欢用红黑树这种平衡二叉查找树的原因
①TreapSplay Tree绝大部分情况下它们操作的效率都很高但是也无法避免极端情况下时间复杂度的退化。尽管这种情况出现概率不大但是对于单次操作时间非常敏感的场景来讲它们不适用。 ②AVL树是一种高度平衡的二叉树所以查找的效率非常高但是有利有弊AVL树为了维持这种高度平衡要付出更多代价每次插入删除都要做调整就比较复杂耗时。所以有频繁的插入删除操作的数据集合使用AVL树的代价就有点高了。 ③红黑树只是做到了近似平衡并不是严格的平衡所以维护平衡的成本上要比AVL树低。 所以红黑树的插入删除查找各种操作性能都比较稳定。对于工程应用来说结果状态可控可预期。
四、理解红黑树源码
使用递推思想 暂时无法理解
N、问题
动态数据结构支持动态的数据插入、删除、查找操作除了红黑树我们前面还学习过哪些呢能对比一下各自的优势、劣势以及应用场景吗 散列表插入删除查找都是O(1), 是最常用的但其缺点是不能顺序遍历以及扩容缩容的性能损耗。适用于那些不需要顺序遍历数据更新不那么频繁的。
跳表插入删除查找都是O(logn), 并且能顺序遍历。缺点是空间复杂度O(n)。适用于不那么在意内存空间的其顺序遍历和区间查找非常方便。
红黑树插入删除查找都是O(logn), 中序遍历即是顺序遍历稳定。缺点是难以实现去查找不方便。其实跳表更佳但红黑树已经用于很多地方了。
笔记整理来源 王争 数据结构与算法之美
