红黑树原理

大纲

1.红黑树怎么自平衡

2.什么时候需要左旋，什么时候需要右旋？

3.插入和删除破坏了树的平衡怎么处理

红黑树的定义和性质

红黑树是一种含有红黑节点并能够自平衡的二叉查找树，必须满足以下性质

1.节点要么是黑色要么是红色

2.根节点是黑节点

3.每个叶子节点（NIL）是黑色的

4.每个红色节点的两个子节点一定是黑色的

5.任意节点到每个叶子节点的路径都包含相同数量的黑节点

5.1如果一个节点存在黑子节点,那么该节点肯定有两个子节点

一颗简单的红黑树

叶子节点：nil，黑色，在java中，叶子节点都是null的节点

红黑树节点叫法

红黑树怎么实现自平衡？三种操作：左旋、右旋、变色

左旋：已最短路径，进行旋转
右旋：已最短路径，进行旋转
变色：节点的颜色从黑变成红或从红变成黑