请你说说红黑树的特性，为什么要有红黑树

[问答题]

请你说说红黑树的特性，为什么要有红黑树

Tim1127

1.根节点和叶子结点是黑的 2.从根到叶子结点的路径上不能连续两个红色节点，黑色节点数要相等。

发表于 2023-02-26 14:55:32 回复(0)

hcodeboy

虽然平衡树解决了二叉树退化为近似链表的缺点，能够把查找时间控制在O(logn)，不过却不是最佳的，因为平衡二叉树要求左子树和右子树的高度差至少等于1，这个要求实在是太严格了，导致每次进行插入/删除节点的术后，都会破坏这个平衡，需要我么进行左旋和右旋调整，使之再成为一个符合要求的平衡二叉树，但当插入、删除很多时，就需要频繁的进行左旋和右旋，这会使平衡树的性能大打折扣，于是就有了红黑树。红黑树的特点如下： 1. 具有二叉查找树的特点 2. 根节点是黑色的 3. 每个叶子结点都是黑色节点（NIL），也就是说，叶子节点不存数据 4. 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的 5. 每个节点，从该节点到达其可达的叶子节点的所有路径，都包含相同数目的黑色节点。

发表于 2023-08-17 09:50:29 回复(0)

coder_u15337_m70992

红黑树对平衡性要求较低，效率更高

发表于 2023-02-27 21:11:59 回复(0)

雏鹰划空

1. 解决的问题：二叉树在极端情况下会退化成链表。于是出现了平衡二叉树，但是平衡二叉树会导致调整过程很麻烦，因为它要求左右子树的高度不超过1。 2. 红黑树的特点： =》根节点必须是黑的。 =》两个红色的节点不可以连续。也就是，红节点的子节点必须是黑节点。 =》任意节点到其某个叶节点的所有路径上的黑色节点的数量是相同的。 =》叶子节点不存数据，默认为黑节点。

发表于 2023-11-11 12:33:26 回复(0)

_helios_

由于平衡树要求太严，在插入、删除很频繁的场景中，平衡树需要频繁进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树，红黑树具有如下特点： 1、具有二叉查找树的特点； 2、根节点是黑色的； 3、每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存数据； 4、任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的； 5、每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点。

发表于 2024-05-21 10:40:52 回复(0)

vwei

红黑树的特点： 1、具有二叉搜索树的特点 2、根节点是黑色的（即不存数据） 3、每个树叶节点是黑色的 4、任何相邻的节点不能都是红色 5、每个节点到其可达节点的所有路径都包含相同数目的黑色节点要有红黑树的原因：平衡二叉搜索树几乎每次插入删除都要进行左旋右旋，在插入删除操作频繁的应用场景中，频繁的调整会使得平衡树的性能大打折扣，为了解决这个问题，就有了红黑树

发表于 2024-04-08 20:24:21 回复(0)

牛客387239580号

std::shared_ptr<myclass> sp1 = std::make_shared<myclass>(); std::shared_ptr<myclass> sp2 = std::make_shared<myclass>(); // sp1和sp2相互引用，形成循环引用 sp1->other = sp2; sp2->other = sp1; // 将sp1转换成weak_ptr std::weak_ptr<myclass> wp1 = sp1; // 通过wp1获取sp1指向的对象 if (std::shared_ptr<myclass> sp3 = wp1.lock()) { // 使用sp3指向的对象 } </myclass></myclass></myclass></myclass></myclass></myclass>

编辑于 2023-04-02 12:09:23 回复(1)

提交观点

问题信息

C++

上传者：real1993

难度：

7条回答 72收藏 1536浏览

请你说说红黑树的特性，为什么要有红黑树

问题信息

热门推荐

相关试题