vlambda博客
学习文章列表

红黑树如何插入和删除的?


面试1000问第12问

Q:
红黑树如何插入和删除的?

插入:
  (
1)如果父节点为黑色,直接插入不处理 

(2)如果父节点为红色,叔叔节点为红色,则父节点和叔叔节点变为黑色,祖先节点变为红色,将节点操作转换为祖先节点 

(3)如果当前节点为父亲节点的右节点,则以父亲结点为中心左旋操作 

(4)如果当前节点为父亲节点的左节点,则父亲节点变为黑色,祖先节点变为红色,以祖先节点为中心右旋操作

删除:

(1)先按照排序二叉树的方法,删除当前节点,如果需要转移即转移到下一个节点 

(2)当前节点,必定为这样的情况:没有左子树。

(3)删除为红色节点,不需要处理,直接按照删除二叉树节点一样

(4)如果兄弟节点为黑色,兄弟节点的两个子节点为黑色,则将兄弟节点变为红色,将着色转移到父亲节点    (5)如果兄弟节点为红色,将兄弟节点设为黑色,父亲结点设为红色节点,对父亲结点进行左旋操作 

(6)如果兄弟节点为黑色,左孩子为红色,右孩子为黑色,对兄弟节点进行右旋操作 

(7)如果兄弟节点为黑色,右孩子为红色,则将父亲节点的颜色赋值给兄弟节点,将父亲节点设置为黑色,将兄弟节点的右孩子设为黑色,对父亲节点进行左旋