************************************代码来自http://www.cnblogs.com/skywang12345/p/3624343.html#a2讲的特别清晰透彻
/* * 对红黑树的节点(x)进行左旋转 * * 左旋示意图(对节点x进行左旋): * px px * / / * x y * / --(左旋)-. / # * lx y x ry * / / * ly ry lx ly * * */ private void leftRotate(RBTNode<T> x) {.///总体看是从两端往中间的过程,先下后上再中间 // 设置x的右孩子为y RBTNode<T> y = x.right; // 将 “y的左孩子” 设为 “x的右孩子”; // 如果y的左孩子非空,将 “x” 设为 “y的左孩子的父亲” x.right = y.left; if (y.left != null)-----------------------//作为孩子是个双向选择的过程,既要你把我当孩子,我也要把你当父亲。如果我为空,当孩子依然成立,但你就做不了父亲了 y.left.parent = x; // 将 “x的父亲” 设为 “y的父亲” y.parent = x.parent; //已经确定是父亲了,那么做父亲的哪个孩子呢,如果没有父亲了为空,自己就是根节点了 if (x.parent == null) { this.mRoot = y; // 如果 “x的父亲” 是空节点,则将y设为根节点 } else { if (x.parent.left == x) x.parent.left = y; // 如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子” else x.parent.right = y; // 如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子” } // 将 “x” 设为 “y的左孩子” y.left = x; // 将 “x的父节点” 设为 “y” x.parent = y; }
/* * 将结点插入到红黑树中 * * 参数说明: * node 插入的结点 // 对应《算法导论》中的node */ private void insert(RBTNode<T> node) { int cmp; RBTNode<T> y = null; RBTNode<T> x = this.mRoot; // 1. 将红黑树当作一颗二叉查找树,将节点添加到二叉查找树中。 while (x != null) { y = x; cmp = node.key.compareTo(x.key); if (cmp < 0) x = x.left; else x = x.right; }////////////--------------找到 应该做插入节点的父节点 为y node.parent = y; if (y!=null) { cmp = node.key.compareTo(y.key); if (cmp < 0) y.left = node; else y.right = node; } else {//-------------如果y为空的话,就表示,根x=null即根为空,这是个空树【插入操作肯定得涉及到空树的呀】 this.mRoot = node; }//当完成这一步的时候已经让Node插入进去了,如果值比y大就右节点,否则左节点 // 2. 设置节点的颜色为红色 node.color = RED; // 3. 将它重新修正为一颗二叉查找树 insertFixUp(node); } /* * 新建结点(key),并将其插入到红黑树中 * * 参数说明: * key 插入结点的键值 */ public void insert(T key) { RBTNode<T> node=new RBTNode<T>(key,BLACK,null,null,null); // 如果新建结点失败,则返回。 if (node != null) insert(node); }
-------------割没懂,大概分成俩方向,每个再三小方向
/* * 红黑树插入修正函数 * * 在向红黑树中插入节点之后(失去平衡),再调用该函数; * 目的是将它重新塑造成一颗红黑树。 * * 参数说明: * node 插入的结点 // 对应《算法导论》中的z */ private void insertFixUp(RBTNode<T> node) { RBTNode<T> parent, gparent;//grandparent祖父 // 若“父节点存在,并且父节点的颜色是红色”//如果父亲是黑色,不用改变节点顺序什么的就可以满足成为红黑树的五大特性了 while (((parent = parentOf(node))!=null) && isRed(parent)) { gparent = parentOf(parent); //若“父节点”是“祖父节点的左孩子” if (parent == gparent.left) { // Case 1条件:叔叔节点是红色 RBTNode<T> uncle = gparent.right; if ((uncle!=null) && isRed(uncle)) { setBlack(uncle); setBlack(parent); setRed(gparent); node = gparent; continue;//此时,虽然祖父颜色未知,但是不管 是什么都可以满足的,红色--改变后子都是黑色了满足,黑色---并要求黑色的结点子节点的颜色 } // Case 2条件:叔叔是黑色,且当前节点是右孩子 if (parent.right == node) { RBTNode<T> tmp; leftRotate(parent); tmp = parent; parent = node; node = tmp; } // Case 3条件:叔叔是黑色,且当前节点是左孩子。 setBlack(parent); setRed(gparent); rightRotate(gparent); } else { //若“z的父节点”是“z的祖父节点的右孩子” // Case 1条件:叔叔节点是红色 RBTNode<T> uncle = gparent.left; if ((uncle!=null) && isRed(uncle)) { setBlack(uncle); setBlack(parent); setRed(gparent); node = gparent; continue; } // Case 2条件:叔叔是黑色,且当前节点是左孩子 if (parent.left == node) { RBTNode<T> tmp; rightRotate(parent); tmp = parent; parent = node; node = tmp; } // Case 3条件:叔叔是黑色,且当前节点是右孩子。 setBlack(parent); setRed(gparent); leftRotate(gparent); } } // 将根节点设为黑色 setBlack(this.mRoot); }
删除操作也是······简直了回见