红黑树 定义: 红黑树是一颗平衡二叉搜索树,而且必须有以下规则: 每个节点不是红色就是黑色; 根结点为黑色; 如果节点为红,其子节点必须为黑; 任一节点至NULL的任何路径,所含黑节点数必须相同。 所以: 根据规则4,新增节点必须为红; 根据规则3,新增节点之父节点必须为黑。