红黑树也是一种自平衡二叉搜索树，通常处理一个包含多次插入和删除的自平衡树，入股插入和删除评论较低那么AVl树会比红黑树更好一点。

在红黑树中，每个节点都要遵循以下规则：

  • 每个节点不是红的就是黑的；
  • 树的根节点是黑色的；
  • 所有叶节点都是黑色额（用NULL引用表示节点）；
  • 如果一个节点是红的，那么它的两个子节点都是黑的；
  • 不能有两个相邻的红节点，一个红节点不能有红的父节点或子节点；
  • 从给定的节点到它的后代节点（NULL叶节点）的所有路径包含相同数量的黑色节点。

    向红黑树插入节点

    向红黑树插入节点和在二叉搜索树中是一样的，插入后还需要给节点插入一种颜色，并且颜色是否忙族红黑树的条件以及是否还是自平衡的。

在插入节点后验证红黑树属性

验证红黑树是否平衡要求：重新填色和旋转，需要改变父节点，祖父节点和树节点