1.jdk中TreeMap,TreeSet底层用的什么数据结构?
红黑树
2.红黑树的数据结构怎么定义的?

enum Color  
{  
          RED = 0,  
          BLACK = 1  
};  
struct RBTreeNode  
{  
           struct RBTreeNode*left, *right, *parent;  
           int   key;  
           int data;  
           Color color;  
};  

3.红黑树有哪些性质?
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个叶节点(NIL节点,空节点)是黑色的。
性质4 每个红色节点的两个子节点都是黑色。从每个叶子到根的所有路径上不能有两个连续的红色节点。
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

4.红黑树的各种操作的时间复杂度是多少?
能保证在最坏情况下,基本的动态几何操作的时间均为O(lgn)

5.左旋转:
逆时针旋转红黑树的两个节点,使得父节点被自己的右孩子取代,而自己成为自己的左孩子。

left.png

右旋转:
顺时针旋转红黑树的两个节点,使得父节点被自己的左孩子取代,而自己成为自己的右孩子。

right.png