红黑树是一颗二叉搜索树每个结点都增加了一个位置用来表示结点的颜色红色或者黑色颜色规则每个节点要么是红色要么是黑色。根节点规则根节点必须是黑色。叶子节点规则所有叶子节点NIL节点都是黑色的。这里的叶子节点指的是空节点而不是传统意义上的没有子节点的节点。红色节点规则如果一个节点是红色的那么它的两个子节点必须是黑色的。这意味着在红黑树中不会有连续的红色节点。黑色节点规则对于任意一个节点从该节点到其所有叶子节点的每条路径上黑色节点的数量是相同的为了保证跟最短路径的黑色结点数量一样最长路径只能加红色结点所以最长路径一定是一黑一红组成的最长路径就是2*hh为黑高就是路径上黑色结点数量这里的黑色结点不包含根节点而是将末端null结点当做黑色结点因此最长路径不会大于最短路径的二倍结点数量2的h次方-1 到 2的2h次方-1一个全是黑的完美二叉树一个全是红黑相间的完美二叉树最长路径就是 2*logN因为结点数量为 2的h次方-1 N 2的2h次方-1)就能推算得到时间复杂度还是Ologn