红黑树与平衡二叉树的区别

[shawlp]

平衡二叉树是为了解决二叉查找树退化成一颗链表而诞生了，平衡二叉树具有如下特点：

1. 二叉查找树的特点就是左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大
2. 每个节点的左子树和右子树的高度差至多等于1

由于平衡树要求每个节点的左子树和右子树的高度至多等于1，这个要求太严格了，导致每次进行插入/删除节点的时候，几乎都会破坏这个规则，所以需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树

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