在红黑树中删除节点,需要考虑到删除后会不会破坏红黑树平衡,如果违反平衡性质就需要通过旋转和重新分配颜色。
删除红黑树节点有这7种情况
1、当删除的是子节点且该子节点是红色的,直接删除即可,因为它不会破坏红黑树的特性。
2、当删除的是红黑树的根,可以直接删除。
3、当删除的子节点是黑色,且其右子节点为红时,将右子节点变成黑替换到被删除元素的位置。
4、当被删除节点为黑色,且兄弟节点为黑色,兄弟节点两个子节点也为黑,父节点为红,此时,交换兄弟节点与父节点的颜色。
5、当被删除节点为黑、并且为父节点的左子节点,且兄弟节点颜色为黑,兄弟节点的右子节点为红色,这个时候需要交换兄弟节点与父节点的颜色,并把父节点涂黑、兄弟的右子节点涂黑,并以父节点为中心左转。
6、当被删除节点为黑、并且为父节点的左子节点,且兄弟颜色为黑,兄弟的左子节点为红色,这个时候需要先把兄弟与兄弟的左子节点颜色互换,进行右转。
7、被删除节点为黑且兄弟节点为黑,兄弟节点的子节点为黑,父节点为黑,这个时候需要将兄弟节点变为红,再把父节点看做那个被删除的元素。