红黑树
红黑树的性质
- 每个节点的颜色非红即黑
- 根节点是黑色
- 每个叶子节点(NIL)是黑色
- 红色节点的子节点必黑
- 对于每个节点，从它出发到每一个叶子节点路经上的黑色节点数量相同(忽略红色节点,黑色节点height平衡)
插入操作
- 1.插入节点是根节点，将根节点变黑
- 2.父节点是黑
- 3.父节点是红，叔节点是红，将父，叔节点置黑，祖父节点置红，再判断祖父节点变红是否打破性质4
- 4.父节点是红，叔节点是黑,父节点是祖父节点的左子节点，插入节点是父节点的左子节点，祖父节点右旋，P置黑，G置红
- 5.父节点是红，叔节点是黑,父节点是祖父节点的左子节点，插入节点是父节点的右子节点，父节点左旋，然后转化成情形4
- 6.父节点是红，叔节点是黑,父节点是祖父节点的右子节点，与情形4，5类似