書上的文字描述是這樣的：在沿著左鏈接向下的過程中，保證以下情況之一成立：1、如果當前節點的左子節點不是2-節點，完成；2、如果當前節點的左子節點時2-節點，而他的親兄弟節點不是2-節點，將左子節點的兄弟節點中的一個鍵移動到左子節點中；3、如果當前節點的左子節點和它的親兄弟節點都是2-節點，將左子節點，父親節點中的最小鍵和左子節點最近的兄弟節點合并一個4-節點。這樣的話刪除后仍可以保持紅黑樹的狀態。上面這段話我是看懂了，但是放到代碼里就不知道哪里有對應上面這段話中的操作，代碼如下：代碼我貼了紅黑樹的全部API,只要看刪除最小鍵那就好了。package?unit3_3;
public?class?RedBlackBST<Key?extends?Comparable<Key>,?Value>?{
????private?Node?root;
????private?static?final?boolean?RED?=?true;
????private?static?final?boolean?BLACK?=?false;
????private?class?Node?{
????????Key?key;
????????Value?val;
????????Node?left,?right;
????????int?N;
????????boolean?color;
????????Node(Key?key,?Value?val,?int?N,?boolean?color)?{
????????????this.key?=?key;
????????????this.val?=?val;
????????????this.N?=?N;
????????????this.color?=?color;
????????}
????}
????private?boolean?isRed(Node?x)?{
????????if?(x?==?null)
????????????return?false;
????????return?x.color?=?RED;
????}
????//?節點左旋
????private?Node?rotateLeft(Node?h)?{
????????Node?x?=?h.right;
????????h.right?=?x.left;
????????x.left?=?h;
????????x.color?=?h.color;
????????h.color?=?RED;
????????x.N?=?h.N;
????????h.N?=?1?+?size(h.left)?+?size(h.right);
????????return?x;
????}
????//?節點右旋
????private?Node?rotateRight(Node?h)?{
????????Node?x?=?h.left;
????????h.left?=?x.right;
????????x.right?=?h;
????????x.color?=?h.color;
????????x.N?=?h.N;
????????h.N?=?1?+?size(h.left)?+?size(h.right);
????????return?x;
????}
????//?改變顏色
????void?flipColors(Node?h)?{
????????h.color?=?!h.color;
????????h.left.color?=?!h.left.color;
????????h.right.color?=?!h.right.color;
????}
????public?int?size()?{
????????return?size(root);
????}
????private?int?size(Node?x)?{
????????if?(x?==?null)?{
????????????return?0;
????????}?else
????????????return?x.N;
????}
????public?void?put(Key?key,?Value?val)?{
????????root?=?put(root,?key,?val);
????????root.color?=?BLACK;
????}
????public?Node?put(Node?h,?Key?key,?Value?val)?{
????????if?(h?==?null)
????????????return?new?Node(key,?val,?1,?RED);
????????int?cmp?=?key.compareTo(h.key);
????????if?(cmp?<?0)
????????????h.left?=?put(h.left,?key,?val);
????????else?if?(cmp?>?0)
????????????h.right?=?put(h.right,?key,?val);
????????else
????????????h.val?=?val;
????????if?(isRed(h.right)?&&?!isRed(h.left))
????????????h?=?rotateLeft(h);
????????if?(isRed(h.left)?&&?isRed(h.left.left))
????????????h?=?rotateRight(h);
????????if?(isRed(h.left)?&&?isRed(h.right))
????????????flipColors(h);
????????h.N?=?size(h.left)?+?size(h.right)?+?1;
????????return?h;
????}
????public?boolean?isEmpty()?{
????????return?size()?==?0;
????}
????private?Node?balance(Node?h)?{
????????if?(isRed(h.right))
????????????h?=?rotateLeft(h);
????????if?(isRed(h.right)?&&?!isRed(h.left))
????????????h?=?rotateLeft(h);
????????if?(isRed(h.left)?&&?isRed(h.left.left))
????????????h?=?rotateRight(h);
????????if?(isRed(h.left)?&&?isRed(h.right))
????????????flipColors(h);
????????h.N?=?size(h.left)?+?size(h.right)?+?1;
????????return?h;
????}
????public?Value?get(Key?key)?{
????????return?get(root,?key);
????}
????private?Value?get(Node?x,?Key?key)?{
????????if?(x?==?null)
????????????return?null;
????????int?cmp?=?key.compareTo(x.key);
????????if?(cmp?<?0)
????????????return?get(x.left,?key);
????????else?if?(cmp?>?0)
????????????return?get(x.right,?key);
????????else
????????????return?x.val;
????}
????//?求最小值
????public?Key?min()?{
????????return?min(root).key;
????}
????private?Node?min(Node?x)?{
????????if?(x.left?==?null)
????????????return?x;
????????return?min(x.left);
????}
????//?刪除最小鍵
????private?Node?removeRedLeft(Node?h)?{
????????flipColors(h);
????????if?(isRed(h.right.left))?{
????????????h.right?=?rotateRight(h.right);
????????????h?=?rotateLeft(h);
????????}
????????return?h;
????}
????public?void?deleteMin()?{
????????if?(!isRed(root.left)?&&?!isRed(root.right))
????????????root.color?=?RED;
????????root?=?deleteMin(root);
????????if?(!isEmpty())
????????????root.color?=?BLACK;
????}
????private?Node?deleteMin(Node?h)?{
????????if?(h.left?==?null)
????????????return?null;
????????if?(!isRed(h.left)?&&?!isRed(h.left.left))
????????????h?=?removeRedLeft(h.left);
????????h.left?=?deleteMin(h.left);
????????return?balance(h);
????}
????//?刪除最大鍵
????private?Node?moveRedRight(Node?h)?{
????????flipColors(h);
????????if?(!isRed(h.left.left))
????????????h?=?rotateRight(h);
????????return?h;
????}
????public?void?deleteMax()?{
????????if?(!isRed(root.left)?&&?!isRed(root.right))
????????????root.color?=?RED;
????????root?=?deleteMax(root);
????????if?(!isEmpty())
????????????root.color?=?BLACK;
????}
????private?Node?deleteMax(Node?h)?{
????????if?(isRed(h.left))
????????????h?=?rotateRight(h);
????????if?(h.right?==?null)
????????????return?null;
????????if?(!isRed(h.right)?&&?!isRed(h.right.left))
????????????h?=?moveRedRight(h);
????????h.right?=?deleteMax(h.right);
????????return?balance(h);
????}
????//?刪除任意鍵
????public?void?delete(Key?key)?{
????????if?(!isRed(root.left)?&&?!isRed(root.right))
????????????root.color?=?RED;
????????root?=?delete(root,?key);
????????if?(!isEmpty())
????????????root.color?=?BLACK;
????}
????private?Node?delete(Node?h,?Key?key)?{
????????if?(key.compareTo(h.key)?<?0)?{
????????????if?(!isRed(h.left)?&&?!isRed(h.left.left))
????????????????h?=?removeRedLeft(h);
????????????h.left?=?delete(h.left,?key);
????????}?else?{
????????????if?(isRed(h.left))
????????????????h?=?rotateRight(h);
????????????if?(key.compareTo(h.key)?==?0?&&?(h.right?==?null))
????????????????return?null;
????????????if?(!isRed(h.right)?&&?!isRed(h.right.left))
????????????????h?=?moveRedRight(h);
????????????if?(key.compareTo(h.key)?==?0)?{
????????????????h.val?=?get(h.right,?min(h.right).key);
????????????????h.key?=?min(h.right).key;
????????????????h.right?=?deleteMin(h.right);
????????????}?else
????????????????h.right?=?delete(h.right,?key);
????????}
????????return?balance(h);
????}
}
1 回答
已采納
-
Liu__就是removeRedLeft那個方法，不懂具體有什么用 -
Liu__最好有個刪除的例子，謝謝
-
sunbohan00剛剛登上慕課網，不管是什么方式，你能理解了那是最好的了。加油
點擊展開后面1條
添加回答
舉報
0/150
提交
取消