江苏龙网

  1. 首页 > 生活 > >

红黑树与普通的平衡二叉树除了颜色到底有啥区别为啥要引入红黑树，它比普通的平衡二叉树究竟好在哪

先来自问几个问题：
什么是红黑树？
为什么要有红黑树？
红黑树RBT与平衡二叉树AVL如何选择？
一颗红黑树是如何保持平衡的？
什么是一颗红黑树的黑高（Black Height)?
为什么一颗红黑树的所有操作时间复杂度都是O(logn)?
红黑树有什么应用呢？
本文中你都将找到答案
需要你清楚二叉排序树BST还有AVL树！不懂的看下面图文
图解：什么是二叉排序树？图解：什么是AVL树？图解：什么是AVL树？（删除总结篇）接下来看看红黑树的精髓所在？如果你的基础比较好（对什么是黑高、为什么要有红黑树，红黑树RBT与平衡二叉树AVL有何区别，如何选择？红黑树是如何保持平衡的？都理解），直接看最后面部的内容！要不就耐心自上而下看下去
红黑树与普通的平衡二叉树除了颜色到底有啥区别为啥要引入红黑树，它比普通的平衡二叉树究竟好在哪

红黑树与普通的平衡二叉树除了颜色到底有啥区别为啥要引入红黑树，它比普通的平衡二叉树究竟好在哪

红黑树与普通的平衡二叉树除了颜色到底有啥区别为啥要引入红黑树，它比普通的平衡二叉树究竟好在哪

红黑树与普通的平衡二叉树除了颜色到底有啥区别为啥要引入红黑树，它比普通的平衡二叉树究竟好在哪

红黑树与普通的平衡二叉树除了颜色到底有啥区别为啥要引入红黑树，它比普通的平衡二叉树究竟好在哪

什么是红黑树？
红黑树（Red Black Tree）是一颗自平衡（self-balancing）的二叉排序树（BST），树上的每一个结点都遵循下面的规则（特别提醒，这里的自平衡和平衡二叉树AVL的高度平衡有别）：
每一个结点都有一个颜色，要么为红色，要么为黑色；树的根结点为黑色；树中不存在两个相邻的红色结点（即红色结点的父结点和孩子结点均不能是红色）；从任意一个结点（包括根结点）到其任何后代 NULL 结点（默认是黑色的）的每条路径都具有相同数量的黑色结点。红黑树与普通的平衡二叉树除了颜色到底有啥区别为啥要引入红黑树，它比普通的平衡二叉树究竟好在哪

这就是一颗典型的红黑树，树中的每个结点的颜色要么是黑色，要么是红色；根结点 6 为黑色结点；树中不存在两个相邻的红色结点，比如结点 15 为红色结点，其父亲节点 6 与两个孩子结点就一定是黑色，而不能是红色； 从结点到其后代的 NUll结点 的每条路径上具有相同数目的黑色结点，比如根结点 6 到其左子树的 NULL结点 包含三个黑色结点，到其右子树所有的 NULL 结点也包含三个黑色结点。 可能还不够清晰，为此我对上图做了修改为所有默认为黑色的 NULL 结点给了一个标记。
红黑树与普通的平衡二叉树除了颜色到底有啥区别为啥要引入红黑树，它比普通的平衡二叉树究竟好在哪

现在解释规则的第四条简直不能再清晰了！比如根结点 6 到 NULL结点 a 的路径 6→2→a 上的黑色结点为 3 个，从根结点 6 到结点 c 的路径 6→15→10→9→c 中包含的黑色结点个数也是 3 个，同理从根结点 6 到其他所有 NULL结点 的黑色结点数都是 3 。再举个栗子，从红色结点 15 到NULL结点 d 的路径 15→18→g 包含 2 个黑色结点，到NULL结点 c 的路径 15→10→9→c 也包含黑色结点 2 个，从结点 15 到其所有后代的 NULL结点的 黑色结点数目都是 2 。
红黑树与普通的平衡二叉树除了颜色到底有啥区别为啥要引入红黑树，它比普通的平衡二叉树究竟好在哪


推荐阅读


上一篇：想去中国当练习生，有啥意见吗可以分享一下

下一篇：有肉分享闲置物品是怎么样一种体验