• 红黑树
  • 红黑树的五大性质
  • 查询节点
  • 插入节点
  • 删除节点

红黑树

红黑树的五大性质

（1）每个节点或者是黑色，或者是红色。

（2）根节点是黑色。

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

（4）每个红色结点的两个子结点一定都是黑色。

（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

查询节点

类似二叉搜索树查询

插入节点

插入元素，如果元素在树中存在，则替换value；如果元素不存在，则插入到对应的位置，再平衡树。

插入的元素默认都是红色，因为插入红色元素只违背了第4条特性，那么我们只要根据这个特性来平衡就容易多了。

根据不同的情况有以下几种处理方式：

• 插入的元素如果是根节点，则直接涂成黑色即可，不用平衡；

• 插入的元素的父节点如果为黑色，不需要平衡；

• 插入的元素的父节点如果为红色，则违背了特性4，需要平衡，平衡时又分成下面三种情况：

删除节点

如果需要删除的节点有两个儿子，那么问题可以被转化成删除另一个只有一个儿子的节点的问题

(在删除带有两个非叶子儿子的节点的时候，我们要么找到它左子树中的最大元素、要么找到它右子树中的最小元素，并把它的值转移到要删除的节点中，接着删除要删除的节点)

接下来我们讨论只有没有子节点和只有一个子节点的问题。

如果要删除的节点没有子节点，且为黑色，需要重平衡。

如果要删除的节点和它的子节点均为黑色，需要重平衡。