Commons Collections學習筆記（三）

這個Map類是基於紅黑樹構建的，每個樹節點有兩個域，一個存放節點的Key,一個存放節點的Value,相當於是兩棵紅黑樹，一棵是關於key的 紅黑樹，一棵是關於Value的紅黑樹。

關於紅黑樹的詳細介紹，參考《C#與數據結構--樹論--紅黑樹（Red Black Tree）》這篇文章。

public final class DoubleOrderedMap extends AbstractMap
{
private Node[] rootNode = new Node[] { null, null };//根節點

public Set entrySetByValue()
{//按Value獲取Entry集合
　　　　 if (setOfEntries[VALUE] == null) {
　　　　　　 setOfEntries[VALUE] = new AbstractSet() {
　　　　　　　　 public Iterator iterator() {
　　　　　　　　　　 return new DoubleOrderedMapIterator(VALUE) {
　　　　　　　　　　　　 protected Object doGetNext() {
　　　　　　　　　　　　　　 return lastReturnedNode;
　　　　　　　　　　　　 }
　　　　　　　　　　 };
　　　　　　　　 }
　　　　　　　　 public boolean contains(Object o) {
　　　　　　　　　　 if (!(o instanceof Map.Entry)) {
　　　　　　　　　　　　 return false;
　　　　　　　　　　 }
　　　　　　　　　　 Map.Entry entry = (Map.Entry) o;
　　　　　　　　　　 Object　　key　 = entry.getKey();
　　　　　　　　　　 Node　　　node　= lookup((Comparable) entry.getValue(),
　　　　　　　　　　　　　　　　　　　　　　 VALUE);
　　　　　　　　　　 return (node != null) && node.getData(KEY).equals(key);
　　　　　　　　 }
　　　　　　　　 public boolean remove(Object o) {
　　　　　　　　　　 if (!(o instanceof Map.Entry)) {
　　　　　　　　　　　　 return false;
　　　　　　　　　　 }
　　　　　　　　　　 Map.Entry entry = (Map.Entry) o;
　　　　　　　　　　 Object　　key　 = entry.getKey();
　　　　　　　　　　 Node　　　node　= lookup((Comparable) entry.getValue(),
　　　　　　　　　　　　　　　　　　　　　　 VALUE);
　　　　　　　　　　 if ((node != null) && node.getData(KEY).equals(key)) {
　　　　　　　　　　　　 doRedBlackDelete(node);
　　　　　　　　　　　　 return true;
　　　　　　　　　　 }
　　　　　　　　　　 return false;
　　　　　　　　 }
　　　　　　　　 public int size() {
　　　　　　　　　　 return DoubleOrderedMap.this.size();
　　　　　　　　 }
　　　　　　　　 public void clear() {
　　　　　　　　　　 DoubleOrderedMap.this.clear();
　　　　　　　　 }
　　　　　　 };
　　　　 }
　　　　 return setOfEntries[VALUE];
}

private Object doRemove(final Comparable o, final int index)
{
　　　　 Node　 node = lookup(o, index);//在紅黑樹中查找節點
　　　　 Object rval = null;
　　　　 if (node != null)
{
　　　　　　 rval = node.getData(oppositeIndex(index));
　　　　　　 doRedBlackDelete(node);//在紅黑樹中刪除指定節點
　　　　 }
　　　　 return rval;
　　 }
private Object doGet(final Comparable o, final int index)
{
　　　　 checkNonNullComparable(o, index);//檢查參數非空
　　　　 Node node = lookup(o, index);//按Key或Value查找指定節點
　　　　 return ((node == null)? null: node.getData(oppositeIndex(index)));
　　 }
private Node lookup(final Comparable data, final int index)
{
　　　　 Node rval = null;
　　　　 Node node = rootNode[index];//根節點
　　　　 while (node != null)
{
　　　　　　 int cmp = compare(data, node.getData(index));//與當前節點比較
　　　　　　 if (cmp == 0)
{//找到了
　　　　　　　　 rval = node;
　　　　　　　　 break;
　　　　　　 } else {//在左子樹或右子樹中尋找
　　　　　　　　 node = (cmp < 0)
　　　　　　　　　　　 ? node.getLeft(index)
　　　　　　　　　　　 : node.getRight(index);
　　　　　　 }
　　　　 }
　　　　 return rval;
　　 }
private static Node leastNode(final Node node, final int index)
{//返回指定節點的最右子節點
　　　　 Node rval = node;
　　　　 if (rval != null) {
　　　　　　 while (rval.getLeft(index) != null) {
　　　　　　　　 rval = rval.getLeft(index);
　　　　　　 }
　　　　 }
　　　　 return rval;
　　 }

private Node nextGreater(final Node node, final int index)
{//返回下一個大於指定節點的節點
　　　　 Node rval = null;
　　　　 if (node == null) {
　　　　　　 rval = null;
　　　　 } else if (node.getRight(index) != null)
{//右子樹不為空，返回右子樹最左子節點
　　　　　　 rval = leastNode(node.getRight(index), index);
　　　　 }
else
{//不斷向上，只要仍然是右子節點
　　　　　　 Node parent = node.getParent(index);
　　　　　　 Node child　= node;
　　　　　　 while ((parent != null) && (child == parent.getRight(index))) {
　　　　　　　　 child　= parent;
　　　　　　　　 parent = parent.getParent(index);
　　　　　　 }
　　　　　　 rval = parent;
　　　　 }
　　　　 return rval;
　　 }

private void rotateLeft(final Node node, final int index)
{//左旋操作
　　　　 Node rightChild = node.getRight(index);
　　　　 node.setRight(rightChild.getLeft(index), index);
　　　　 if (rightChild.getLeft(index) != null) {
　　　　　　 rightChild.getLeft(index).setParent(node, index);
　　　　 }
　　　　 rightChild.setParent(node.getParent(index), index);
　　　　 if (node.getParent(index) == null)
{//設置為根節點
　　　　　　 rootNode[index] = rightChild;
　　　　 } else if (node.getParent(index).getLeft(index) == node) {
　　　　　　 node.getParent(index).setLeft(rightChild, index);
　　　　 } else {
　　　　　　 node.getParent(index).setRight(rightChild, index);
　　　　 }
　　　　 rightChild.setLeft(node, index);
　　　　 node.setParent(rightChild, index);
　　 }

private void rotateRight(final Node node, final int index)
{//右旋操作
　　　　 Node leftChild = node.getLeft(index);
　　　　 node.setLeft(leftChild.getRight(index), index);
　　　　 if (leftChild.getRight(index) != null) {
　　　　　　 leftChild.getRight(index).setParent(node, index);
　　　　 }
　　　　 leftChild.setParent(node.getParent(index), index);
　　　　 if (node.getParent(index) == null)
{//設置為根節點
　　　　　　 rootNode[index] = leftChild;
　　　　 } else if (node.getParent(index).getRight(index) == node) {
　　　　　　 node.getParent(index).setRight(leftChild, index);
　　　　 } else {
　　　　　　 node.getParent(index).setLeft(leftChild, index);
　　　　 }
　　　　 leftChild.setRight(node, index);
　　　　 node.setParent(leftChild, index);
}
private void doRedBlackInsert(final Node insertedNode, final int index)
　 {//進行紅黑樹節點插入後的調整
　　　　 Node currentNode = insertedNode;//新插入節點置為當前節點
　　　　 makeRed(currentNode, index);//標記新節點為紅色
　　　　 while ((currentNode != null) && (currentNode != rootNode[index])&& (isRed(currentNode.getParent (index), index)))
　　　　 {//確保當前節點父節點為紅色才繼續處理
　　　　　　 if (isLeftChild(getParent(currentNode, index), index))
　　　　　　 {//父節點是祖父節點的左孩子
　　　　　　　　 Node y = getRightChild(getGrandParent(currentNode, index),index);//叔節點是祖父節點的右孩子
　　　　　　　　 if (isRed(y, index))
　　　　　　　　 {//紅叔(圖4)
　　　　　　　　　　 makeBlack(getParent(currentNode, index), index);//標記父節點為黑色
　　　　　　　　　　 makeBlack(y, index);//標記叔節點為黑色
　　　　　　　　　　 makeRed(getGrandParent(currentNode, index), index);//標記祖父節點為紅色
　　　　　　　　　　 currentNode = getGrandParent(currentNode, index);//置祖父節點為當前節點
　　　　　　　　 }
　　　　　　　　 else
　　　　　　　　 {//黑叔(對應圖5和圖6)
　　　　　　　　　　 if (isRightChild(currentNode, index))
　　　　　　　　　　 {//當前節點是父節點的右孩子(圖6)
　　　　　　　　　　　　 currentNode = getParent(currentNode, index);//置父節點為當前節點
　　　　　　　　　　　　 rotateLeft(currentNode, index);//左旋
　　　　　　　　　　 }
　　　　　　　　　　 makeBlack(getParent(currentNode, index), index);//當前節點的父節點置為黑色
　　　　　　　　　　 makeRed(getGrandParent(currentNode, index), index);//祖父節點置為紅色
　　　　　　　　　　 if (getGrandParent(currentNode, index) != null)
　　　　　　　　　　 {//對祖父節點進行右旋
　　　　　　　　　　　　 rotateRight(getGrandParent(currentNode, index),index);
　　　　　　　　　　 }
　　　　　　　　 }
　　　　　　 } else
　　　　　　 {//父節點是祖父節點的右孩子
　　　　　　　　 Node y = getLeftChild(getGrandParent(currentNode, index),index);//叔節點是祖父節點的左孩子
　　　　　　　　 if (isRed(y, index))
　　　　　　　　 {//紅叔(圖4)
　　　　　　　　　　 makeBlack(getParent(currentNode, index), index);//標記父節點為黑色
　　　　　　　　　　 makeBlack(y, index);//標記叔節點為黑色
　　　　　　　　　　 makeRed(getGrandParent(currentNode, index), index);//標記祖父節點為紅色
　　　　　　　　　　 currentNode = getGrandParent(currentNode, index);//置祖父節點為當前節點
　　　　　　　　 }
　　　　　　　　 else
　　　　　　　　 {//黑叔(對應圖7和圖8)
　　　　　　　　　　 if (isLeftChild(currentNode, index))
　　　　　　　　　　 {//當前節點是父節點的左孩子(圖8)
　　　　　　　　　　　　 currentNode = getParent(currentNode, index);//置父節點為當前節點
　　　　　　　　　　　　 rotateRight(currentNode, index);//右旋
　　　　　　　　　　 }
　　　　　　　　　　 makeBlack(getParent(currentNode, index), index);//當前節點的父節點置為黑色
　　　　　　　　　　 makeRed(getGrandParent(currentNode, index), index);//祖父節點置為紅色
　　　　　　　　　　 if (getGrandParent(currentNode, index) != null)
　　　　　　　　　　 {//對祖父節點進行左旋
　　　　　　　　　　　　 rotateLeft(getGrandParent(currentNode, index), index);
　　　　　　　　　　 }
　　　　　　　　 }
　　　　　　 }
　　　　 }
　　　　 makeBlack(rootNode[index], index);//標記根節點為黑色
　　 }

private void doRedBlackDelete(final Node deletedNode)
{//在紅黑樹中刪除指定節點
　　　　 for (int index = FIRST_INDEX; index < NUMBER_OF_INDICES; index++) {
　　　　　　 // if deleted node has both left and children, swap with
　　　　　　 // the next greater node
　　　　　　 if ((deletedNode.getLeft(index) != null)
　　　　　　　　　　 && (deletedNode.getRight(index) != null)) {
　　　　　　　　 swapPosition(nextGreater(deletedNode, index), deletedNode,
　　　　　　　　　　　　　　 index);
　　　　　　 }
　　　　　　 Node replacement = ((deletedNode.getLeft(index) != null)
　　　　　　　　　　　　　　　　 ? deletedNode.getLeft(index)
　　　　　　　　　　　　　　　　 : deletedNode.getRight(index));
　　　　　　 if (replacement != null) {
　　　　　　　　 replacement.setParent(deletedNode.getParent(index), index);

　　　　　　　　 if (deletedNode.getParent(index) == null) {
　　　　　　　　　　 rootNode[index] = replacement;
　　　　　　　　 } else if (deletedNode
　　　　　　　　　　　　　 == deletedNode.getParent(index).getLeft(index)) {
　　　　　　　　　　 deletedNode.getParent(index).setLeft(replacement, index);
　　　　　　　　 } else {
　　　　　　　　　　 deletedNode.getParent(index).setRight(replacement, index);
　　　　　　　　 }
　　　　　　　　 deletedNode.setLeft(null, index);
　　　　　　　　 deletedNode.setRight(null, index);
　　　　　　　　 deletedNode.setParent(null, index);
　　　　　　　　 if (isBlack(deletedNode, index)) {
　　　　　　　　　　 doRedBlackDeleteFixup(replacement, index);
　　　　　　　　 }
　　　　　　 } else {
　　　　　　　　 // replacement is null
　　　　　　　　 if (deletedNode.getParent(index) == null) {
　　　　　　　　　　 // empty tree
　　　　　　　　　　 rootNode[index] = null;
　　　　　　　　 } else {
　　　　　　　　　　 // deleted node had no children
　　　　　　　　　　 if (isBlack(deletedNode, index)) {
　　　　　　　　　　　　 doRedBlackDeleteFixup(deletedNode, index);
　　　　　　　　　　 }
　　　　　　　　　　 if (deletedNode.getParent(index) != null) {
　　　　　　　　　　　　 if (deletedNode
　　　　　　　　　　　　　　　　 == deletedNode.getParent(index)
　　　　　　　　　　　　　　　　　　 .getLeft(index)) {
　　　　　　　　　　　　　　 deletedNode.getParent(index).setLeft(null, index);
　　　　　　　　　　　　 } else {
　　　　　　　　　　　　　　 deletedNode.getParent(index).setRight(null,
　　　　　　　　　　　　　　　　　　　　　　　　　 index);
　　　　　　　　　　　　 }
　　　　　　　　　　　　 deletedNode.setParent(null, index);
　　　　　　　　　　 }
　　　　　　　　 }
　　　　　　 }
　　　　 }
　　　　 shrink();
　　 }

　　 private void doRedBlackDeleteFixup(final Node replacementNode,
　　　　　　　　　　　　　　　　　　　 final int index){

//重新局部平衡紅黑樹

　　　　Node currentNode = replacementNode;
　　　　 while ((currentNode != rootNode[index])
　　　　　　　　 && (isBlack(currentNode, index))) {
　　　　　　 if (isLeftChild(currentNode, index)) {
　　　　　　　　 Node siblingNode =
　　　　　　　　　　 getRightChild(getParent(currentNode, index), index);
　　　　　　　　 if (isRed(siblingNode, index)) {
　　　　　　　　　　 makeBlack(siblingNode, index);
　　　　　　　　　　 makeRed(getParent(currentNode, index), index);
　　　　　　　　　　 rotateLeft(getParent(currentNode, index), index);
　　　　　　　　　　 siblingNode = getRightChild(getParent(currentNode, index), index);
　　　　　　　　 }
　　　　　　　　 if (isBlack(getLeftChild(siblingNode, index), index)
　　　　　　　　　　　　 && isBlack(getRightChild(siblingNode, index),
　　　　　　　　　　　　　　　　　 index)) {
　　　　　　　　　　 makeRed(siblingNode, index);
　　　　　　　　　　 currentNode = getParent(currentNode, index);
　　　　　　　　 } else {
　　　　　　　　　　 if (isBlack(getRightChild(siblingNode, index), index)) {
　　　　　　　　　　　　 makeBlack(getLeftChild(siblingNode, index), index);
　　　　　　　　　　　　 makeRed(siblingNode, index);
　　　　　　　　　　　　 rotateRight(siblingNode, index);
　　　　　　　　　　　　 siblingNode =
　　　　　　　　　　　　　　 getRightChild(getParent(currentNode, index), index);
　　　　　　　　　　 }
　　　　　　　　　　 copyColor(getParent(currentNode, index), siblingNode,
　　　　　　　　　　　　　　　 index);
　　　　　　　　　　 makeBlack(getParent(currentNode, index), index);
　　　　　　　　　　 makeBlack(getRightChild(siblingNode, index), index);
　　　　　　　　　　 rotateLeft(getParent(currentNode, index), index);
　　　　　　　　　　 currentNode = rootNode[index];
　　　　　　　　 }
　　　　　　 } else {
　　　　　　　　 Node siblingNode = getLeftChild(getParent(currentNode, index), index);
　　　　　　　　 if (isRed(siblingNode, index)) {
　　　　　　　　　　 makeBlack(siblingNode, index);
　　　　　　　　　　 makeRed(getParent(currentNode, index), index);
　　　　　　　　　　 rotateRight(getParent(currentNode, index), index);
　　　　　　　　　　 siblingNode = getLeftChild(getParent(currentNode, index), index);
　　　　　　　　 }
　　　　　　　　 if (isBlack(getRightChild(siblingNode, index), index)
　　　　　　　　　　　　 && isBlack(getLeftChild(siblingNode, index), index)) {
　　　　　　　　　　 makeRed(siblingNode, index);
　　　　　　　　　　 currentNode = getParent(currentNode, index);
　　　　　　　　 } else {
　　　　　　　　　　 if (isBlack(getLeftChild(siblingNode, index), index)) {
　　　　　　　　　　　　 makeBlack(getRightChild(siblingNode, index), index);
　　　　　　　　　　　　 makeRed(siblingNode, index);
　　　　　　　　　　　　 rotateLeft(siblingNode, index);
　　　　　　　　　　　　 siblingNode =
　　　　　　　　　　　　　　 getLeftChild(getParent(currentNode, index), index);
　　　　　　　　　　 }
　　　　　　　　　　 copyColor(getParent(currentNode, index), siblingNode,
　　　　　　　　　　　　　　　 index);
　　　　　　　　　　 makeBlack(getParent(currentNode, index), index);
　　　　　　　　　　 makeBlack(getLeftChild(siblingNode, index), index);
　　　　　　　　　　 rotateRight(getParent(currentNode, index), index);
　　　　　　　　　　 currentNode = rootNode[index];
　　　　　　　　 }
　　　　　　 }
　　　　 }
　　　　 makeBlack(currentNode, index);
　　 }
private void swapPosition(final Node x, final Node y, final int index)
{//交換樹中兩個節點
　　　　 // Save initial values.
　　　　 Node　　xFormerParent　　 = x.getParent(index);
　　　　 Node　　xFormerLeftChild　= x.getLeft(index);
　　　　 Node　　xFormerRightChild = x.getRight(index);
　　　　 Node　　yFormerParent　　 = y.getParent(index);
　　　　 Node　　yFormerLeftChild　= y.getLeft(index);
　　　　 Node　　yFormerRightChild = y.getRight(index);
　　　　 boolean xWasLeftChild　　 =
　　　　　　 (x.getParent(index) != null)
　　　　　　 && (x == x.getParent(index).getLeft(index));
　　　　 boolean yWasLeftChild　　 =
　　　　　　 (y.getParent(index) != null)
　　　　　　 && (y == y.getParent(index).getLeft(index));
　　　　 // Swap, handling special cases of one being the other's parent.
　　　　 if (x == yFormerParent) {　　// x was y's parent
　　　　　　 x.setParent(y, index);
　　　　　　 if (yWasLeftChild) {
　　　　　　　　 y.setLeft(x, index);
　　　　　　　　 y.setRight(xFormerRightChild, index);
　　　　　　 } else {
　　　　　　　　 y.setRight(x, index);
　　　　　　　　 y.setLeft(xFormerLeftChild, index);
　　　　　　 }
　　　　 } else {
　　　　　　 x.setParent(yFormerParent, index);
　　　　　　 if (yFormerParent != null) {
　　　　　　　　 if (yWasLeftChild) {
　　　　　　　　　　 yFormerParent.setLeft(x, index);
　　　　　　　　 } else {
　　　　　　　　　　 yFormerParent.setRight(x, index);
　　　　　　　　 }
　　　　　　 }
　　　　　　 y.setLeft(xFormerLeftChild, index);
　　　　　　 y.setRight(xFormerRightChild, index);
　　　　 }
　　　　 if (y == xFormerParent) {　　// y was x's parent
　　　　　　 y.setParent(x, index);
　　　　　　 if (xWasLeftChild) {
　　　　　　　　 x.setLeft(y, index);
　　　　　　　　 x.setRight(yFormerRightChild, index);
　　　　　　 } else {
　　　　　　　　 x.setRight(y, index);
　　　　　　　　 x.setLeft(yFormerLeftChild, index);
　　　　　　 }
　　　　 } else {
　　　　　　 y.setParent(xFormerParent, index);
　　　　　　 if (xFormerParent != null) {
　　　　　　　　 if (xWasLeftChild) {
　　　　　　　　　　 xFormerParent.setLeft(y, index);
　　　　　　　　 } else {
　　　　　　　　　　 xFormerParent.setRight(y, index);
　　　　　　　　 }
　　　　　　 }
　　　　　　 x.setLeft(yFormerLeftChild, index);
　　　　　　 x.setRight(yFormerRightChild, index);
　　　　 }
　　　　 // Fix children's parent pointers
　　　　 if (x.getLeft(index) != null) {
　　　　　　 x.getLeft(index).setParent(x, index);
　　　　 }
　　　　 if (x.getRight(index) != null) {
　　　　　　 x.getRight(index).setParent(x, index);
　　　　 }
　　　　 if (y.getLeft(index) != null) {
　　　　　　 y.getLeft(index).setParent(y, index);
　　　　 }
　　　　 if (y.getRight(index) != null) {
　　　　　　 y.getRight(index).setParent(y, index);
　　　　 }
　　　　 x.swapColors(y, index);
　　　　 // Check if root changed
　　　　 if (rootNode[index] == x) {
　　　　　　 rootNode[index] = y;
　　　　 } else if (rootNode[index] == y) {
　　　　　　 rootNode[index] = x;
　　　　 }
　　 }
　　 public Object put(final Object key, final Object value)
　　　　　　 throws ClassCastException, NullPointerException,
　　　　　　　　　 IllegalArgumentException {
　　　　 checkKeyAndValue(key, value);
　　　　 Node node = rootNode[KEY];
　　　　 if (node == null) {//空樹
　　　　　　 Node root = new Node((Comparable) key, (Comparable) value);
　　　　　　 rootNode[KEY]　 = root;
　　　　　　 rootNode[VALUE] = root;
　　　　　　 grow();
　　　　 } else {
　　　　　　 while (true) {
　　　　　　　　 int cmp = compare((Comparable) key, node.getData(KEY));
　　　　　　　　 if (cmp == 0) {
　　　　　　　　　　 throw new IllegalArgumentException(
　　　　　　　　　　　　 "Cannot store a duplicate key (\"" + key
　　　　　　　　　　　　 + "\") in this Map");
　　　　　　　　 } else if (cmp < 0) {
　　　　　　　　　　 if (node.getLeft(KEY) != null) {
　　　　　　　　　　　　 node = node.getLeft(KEY);
　　　　　　　　　　 } else {
　　　　　　　　　　　　 Node newNode = new Node((Comparable) key,
　　　　　　　　　　　　　　　　　　　　　　　　 (Comparable) value);
　　　　　　　　　　　　 insertValue(newNode);
　　　　　　　　　　　　 node.setLeft(newNode, KEY);
　　　　　　　　　　　　 newNode.setParent(node, KEY);
　　　　　　　　　　　　 doRedBlackInsert(newNode, KEY);
　　　　　　　　　　　　 grow();
　　　　　　　　　　　　 break;
　　　　　　　　　　 }
　　　　　　　　 } else {　　// cmp > 0
　　　　　　　　　　 if (node.getRight(KEY) != null) {
　　　　　　　　　　　　 node = node.getRight(KEY);
　　　　　　　　　　 } else {
　　　　　　　　　　　　 Node newNode = new Node((Comparable) key,
　　　　　　　　　　　　　　　　　　　　　　　　 (Comparable) value);
　　　　　　　　　　　　 insertValue(newNode);
　　　　　　　　　　　　 node.setRight(newNode, KEY);
　　　　　　　　　　　　 newNode.setParent(node, KEY);
　　　　　　　　　　　　 doRedBlackInsert(newNode, KEY);
　　　　　　　　　　　　 grow();
　　　　　　　　　　　　 break;
　　　　　　　　　　 }
　　　　　　　　 }
　　　　　　 }
　　　　 }
　　　　 return null;
　　 }
private abstract class DoubleOrderedMapIterator implements Iterator
{
　　　　 private int　　expectedModifications;
　　　　 protected Node lastReturnedNode;//上次訪問的節點
　　　　 private Node　 nextNode;//下一個節點(最左子節點)
　　　　 private int　　iteratorType;
　　　　 DoubleOrderedMapIterator(final int type)
{
　　　　　　 iteratorType　　　　　= type;
　　　　　　 expectedModifications = DoubleOrderedMap.this.modifications;
　　　　　　 lastReturnedNode　　　= null;
　　　　　　 nextNode　　　　　　　= leastNode(rootNode[iteratorType],
　　　　　　　　　　　　　　　　　　　　　　　 iteratorType);
　　　　 }
　　　　 protected abstract Object doGetNext();
　　　　 public final boolean hasNext() {
　　　　　　 return nextNode != null;
　　　　 }
　　　　 public final Object next()
　　　　　　　　 throws NoSuchElementException,
　　　　　　　　　　　 ConcurrentModificationException {
　　　　　　 if (nextNode == null) {
　　　　　　　　 throw new NoSuchElementException();
　　　　　　 }
　　　　　　 if (modifications != expectedModifications) {
　　　　　　　　 throw new ConcurrentModificationException();
　　　　　　 }
　　　　　　 lastReturnedNode = nextNode;
　　　　　　 nextNode　　　　 = nextGreater(nextNode, iteratorType);
　　　　　　 return doGetNext();
　　　　 }
　　　　 public final void remove()
　　　　　　　　 throws IllegalStateException,
　　　　　　　　　　　 ConcurrentModificationException {
　　　　　　 if (lastReturnedNode == null) {
　　　　　　　　 throw new IllegalStateException();
　　　　　　 }
　　　　　　 if (modifications != expectedModifications) {
　　　　　　　　 throw new ConcurrentModificationException();
　　　　　　 }
　　　　　　 doRedBlackDelete(lastReturnedNode);
　　　　　　 expectedModifications++;
　　　　　　 lastReturnedNode = null;
　　　　 }
　　 }

//內部節點類

private static final class Node implements Map.Entry, KeyValue
{
　　　　 private Comparable[] data;//數據域（key和value）
　　　　 private Node[]　　　 leftNode;//左子節點
　　　　 private Node[]　　　 rightNode;//右子節點
　　　　 private Node[]　　　 parentNode;//父節點
　　　　 private boolean[]　　blackColor;//顏色(紅或黑)
　　 }
}