1.每个节点或是红色,或是黑色;
2.根节点是黑色的;
3.每个叶节点是黑色的;
4.每个红色节点的两个子节点都是黑色的;
5.对每个节点,到它所有的后代叶节点的简单路径中,有相同数量的黑色节点。
红黑树可能打破平衡二叉树的某些性质,平衡二叉树左右子树的高度差不超过1,但是红黑树的左右子树高度差可能超过1,但是黑节点的高度差是保持高度平衡的,所以说红黑树是黑平衡的二叉树。
本文共 242 字,大约阅读时间需要 1 分钟。
1.每个节点或是红色,或是黑色;
2.根节点是黑色的;
3.每个叶节点是黑色的;
4.每个红色节点的两个子节点都是黑色的;
5.对每个节点,到它所有的后代叶节点的简单路径中,有相同数量的黑色节点。
红黑树可能打破平衡二叉树的某些性质,平衡二叉树左右子树的高度差不超过1,但是红黑树的左右子树高度差可能超过1,但是黑节点的高度差是保持高度平衡的,所以说红黑树是黑平衡的二叉树。
转载于:https://www.cnblogs.com/wenbinshen/p/11178645.html