佛门广大，岂不容一癫僧！

参考

基本概念

二叉搜索树

平衡二叉树

AVL树

红黑树

红黑树性质

  1. 每个节点除了黑色就是红色

  2. 根节点和叶子节点（nil）是黑色

  3. 从根节点到叶子节点任何一条路径上不能有连续的红节点

  4. 从根节点到叶子节点任何一天路径上都包含数量相同的黑节点。

平衡操作

左旋

以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变

右旋

以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变

变色

结点的颜色由红变黑或由黑变红。