Insert完善
根据规则4,新增节点必须为红;根据规则3,新增节点之父节点必须为黑.
示例:
(1)插入16(红色)/55(红色),则既不用旋转,也不用重新染色
(2)插入82(红色),则违反了红黑规则,需要进行动态的调整;
红黑树所需的处理
1.单旋转
新插入的X与其父P都是红色的,而且X还是G的外部孙子;
2.双旋转
新插入的X与其父P都是红色的,而且X还是G的内部孙子;
3.还需要处理有两个红色孩子的节点,将右儿子变成黑色的,我们只允许左儿子是红色的;方法:旋转+重新染色
insert完整实现代码:
/**注意带有 ++ 注释的为新添加的代码**/template <typename Comparable>void RedBlackTree<Comparable>::insert(const Comparable &x){current = parent = grand = great = header;nullNode->element = x;while (current->element != x){//让祖父成为曾祖父, 父亲成为祖父, 自己成为父亲//每个人都长了一辈great = grand;grand = parent;parent = current;current = (x < current->element) ? current->left: current->right;// ++//+ 处理1. 如果current节点有两个红孩子if ((current->left->color == RED) && (current->right->color == RED))handleReorient( x );}//如果树中包含相同的元素if (current != nullNode)throw DuplicateItemException();current = new Node(x, nullNode, nullNode);if (x < parent->element)parent->left = current;elseparent->right = current;// ++//+ 处理2. 如果新插入的节点破坏了红黑规则, 则还需做一次处理handleReorient( x );}/**自动平衡函数:[1]重新染色[2]自动旋转*/template <typename Comparable>void RedBlackTree<Comparable>::handleReorient(const Comparable & item){// 将current节点染成红色current->color = RED;// 将current的left和right节点染成黑色current->left->color = current->right->color = BLACK;// 如果current节点的父节点也是红的 -> 单旋转 or 双旋转if( parent->color == RED ){//则将其祖父(爷爷)的颜色染成红色grand->color = RED;//然后判断新插入的节点是否是内部孙子?//如果是, 则增加一次旋转->构成双旋转//if注释: 如果该节点小于爷爷, 小于爸爸, 这两种情况不同时满足//则说明其是爷爷的内孙子if( (item < grand->element) != (item < parent->element) ){// 则依grand(祖父)节点进行旋转parent = rotate( item, grand ); // Start double rotate}// 则依great(曾祖父)节点进行旋转current = rotate( item, great );//令当前节点为黑色current->color = BLACK;}//根节点必须是黑色的header->right->color = BLACK; // Make root black}// 自动判断并进行旋转函数template <typename Comparable>typename RedBlackTree<Comparable>::Node *RedBlackTree<Comparable>::rotate(const Comparable &item,Node *theParent ){//位于theParent的左子树if( item < theParent->element ){//如果为真, 则说明theParent->left有左孩子,//否则, 有右孩子item < theParent->left->element ?//如果theParent左边有一棵子树, 则以theParent->left//为轴, 向右转rotateWithLeftChild( theParent->left ) : // LL//如果theParent右边有一棵子树, 则以theParent->left//为轴, 向左转rotateWithRightChild( theParent->left ) ; // LRreturn theParent->left;//返回左子树}else //位于右子树{//如果为真, 则说明theParent->right有左孩子,往右转//否则, 有右孩子, 往左转item < theParent->right->element ?rotateWithLeftChild( theParent->right ) : // RLrotateWithRightChild( theParent->right ); // RRreturn theParent->right; //返回右子树}}
测试代码:
int main(){//用NEG_INF来代表负无穷大const int NEG_INF = -999999;RedBlackTree<int> tree(NEG_INF);tree.insert(50);cout << tree.header->right->element << " " << tree.header->right->nodeColor() << endl;cout << endl;tree.insert(40);cout << tree.header->right->left->element << " " << tree.header->right->left->nodeColor() << endl << endl;//此时需要进行旋转和重新染色tree.insert(30);cout << tree.header->right->element << " " << tree.header->right->nodeColor() << endl ;cout << tree.header->right->left->element << " " << tree.header->right->left->nodeColor() << endl;cout << tree.header->right->right->element << " " << tree.header->right->right->nodeColor() << endl;return 0;}//由于需要用到nodeColor成员函数, 因此我们将RedBlackNode类改造如下:template <typename Comparable>class RedBlackNode{friend class RedBlackTree<Comparable>;public:RedBlackNode(const Comparable &theElement = Comparable(),RedBlackNode *theLeft = NULL,RedBlackNode *theRight = NULL,int theColor = RedBlackTree<Comparable>::BLACK): element(theElement), left(theLeft), right(theRight), color(theColor) {}public://返回当前节点的颜色, 以作测试std::string nodeColor() const{return (color == RedBlackTree<Comparable>::BLACK) ? "black" : "red";}public:Comparable element;RedBlackNode *left;RedBlackNode *right;int color;};红黑树其他操作template <typename Comparable>class RedBlackTree{…bool isEmpty() const;void makeEmpty();Gref<Comparable> find(const Comparable & x) const;Gref<Comparable> findMin() const;Gref<Comparable> findMax() const;//递归删除所有节点void reclainMemory(Node *t) const;…};不要因为世态变迁而埋怨,不要因为命运多舛而怨恨.
