平坝网站建设,如何开天猫店铺,网站建设计入哪个科目,修改wordpress用户名写在前面 主要描述为什么有了二叉查找树/平衡树还需要红黑树 1、二叉查找树的缺点 二叉查找树#xff0c;相信大家都接触过#xff0c;二叉查找树的特点就是左子树的节点值比父亲节点小#xff0c;而右子树的节点值比父亲节点大#xff0c;如图 基于二叉查找树的这种特点相信大家都接触过二叉查找树的特点就是左子树的节点值比父亲节点小而右子树的节点值比父亲节点大如图 基于二叉查找树的这种特点我们在查找某个节点的时候可以采取类似于二分查找的思想快速找到某个节点。n 个节点的二叉查找树正常的情况下查找的时间复杂度为 Ologn。 之所以说是正常情况下是因为二叉查找树有可能出现一种极端的情况例如 这种情况也是满足二叉查找树的条件然而此时的二叉查找树已经近似退化为一条链表这样的二叉查找树的查找时间复杂度顿时变成了 O(n)可想而知我们必须不能让这种情况发生为了解决这个问题于是我们引申出了平衡二叉树。 2、平衡二叉树 平衡二叉树就是为了解决二叉查找树退化成一颗链表而诞生了平衡树具有如下特点 1、具有二叉查找树的全部特性。 2、每个节点的左子树和右子树的高度差至多等于1。 例如图一就是一颗平衡树了而图二则不是(节点右边标的是这个节点的高度) 对于图二因为节点9的左孩子高度为2而右孩子高度为0。他们之间的差值超过1了。 平衡树基于这种特点就可以保证不会出现大量节点偏向于一边的情况了。关于平衡树如何构建、插入、删除、左旋、右旋等操作这里不在说明具体可以看我之前写的一篇文章【漫画】以后在有面试官问你AVL树你就把这篇文章扔给他。 于是通过平衡树我们解决了二叉查找树的缺点。对于有 n 个节点的平衡树最坏的查找时间复杂度也为 O(logn)。 为什么有了平衡树还需要红黑树 虽然平衡树解决了二叉查找树退化为近似链表的缺点能够把查找时间控制在 O(logn)不过却不是最佳的因为平衡树要求每个节点的左子树和右子树的高度差至多等于1这个要求实在是太严了导致每次进行插入/删除节点的时候几乎都会破坏平衡树的第二个规则进而我们都需要通过左旋和右旋来进行调整使之再次成为一颗符合要求的平衡树。 显然如果在那种插入、删除很频繁的场景中平衡树需要频繁着进行调整这会使平衡树的性能大打折扣为了解决这个问题于是有了红黑树红黑树具有如下特点 1、具有二叉查找树的特点。 2、根节点是黑色的 3、每个叶子节点都是黑色的空节点NIL也就是说叶子节点不存数据。 4、任何相邻的节点都不能同时为红色也就是说红色节点是被黑色节点隔开的。 5、每个节点从该节点到达其可达的叶子节点是所有路径都包含相同数目的黑色节点。 例如下面的图片注意图片中黑色的、空的叶子节点没有画出图片来自极客时间 正是由于红黑树的这种特点使得它能够在最坏情况下也能在 O(logn) 的时间复杂度查找到某个节点。至于为什么就能够保证时间复杂度为 O(logn)我这里就不细讲了后面的文章可能会讲。 不过与平衡树不同的是红黑树在插入、删除等操作不会像平衡树那样频繁着破坏红黑树的规则所以不需要频繁着调整这也是我们为什么大多数情况下使用红黑树的原因。 不过如果你要说单单在查找方面的效率的话平衡树比红黑树快。 所以我们也可以说红黑树是一种不大严格的平衡树。也可以说是一个折中发方案。 总结 所以最后的答案是平衡树是为了解决二叉查找树退化为链表的情况而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况。 不过红黑树还有挺多其他的知识点可以考例如红黑树有哪些应用场景向集合容器中 HashMapTreeMap 等内部结构就用到了红黑树了。还有构建一棵节点个数为 n 的红黑树时间复杂度是多少红黑树与哈希表在不同应该场景的选择红黑树有哪些性质红黑树各种操作的时间复杂度是多少 转载于:https://www.cnblogs.com/chihirotan/p/11525400.html
