0

私の質問は、この関数ペアを単一の非再帰呼び出しに変換するにはどうすればよいですか? 私が理解しているように、再帰呼び出しは同じ結果をもたらす反復アルゴリズムに変わる可能性があります。

public void insert(Key key, Value value){
       root = insert(root, key, value);
       root.color = BLACK;
}
private Node insert(Node h, Key key, Value value) {

       /*1*/ if (h == null)      return new Node(key, value);

       /*2*/ if (isRed(h.left) && isRed(h.right)) colorFlip(h);

       /*3*/ int cmp = key.compareTo(h.key);
       /*4*/ if (cmp == 0) h.val = value;
       /*5*/ else if (cmp < 0) h.left = insert(h.left, key, value); 
       /*6*/ else              h.right = insert(h.right, key, value);

       /*7*/ if (isRed(h.right) && !isRed(h.left))     h = rotateLeft(h);
       /*8*/ if (isRed(h.left)  && isRed(h.left.left)) h = rotateRight(h);
             return h; 
  }

2 行目で、ノードがスタックにプッシュされたときにノードを評価していることがわかります。また、ノードが 5 行目と 6 行目でユーザー定義スタックにプッシュされていることにも気付きました。7 行目と 8 行目がどこで発生するか、ノードをポップオフして左または右に正しくリンクする方法を考え始めると、混乱が始まります。正しいポインター。

4

1 に答える 1

0

私の直観は、そうすることで、このような厄介な混乱が生じる「はず」であるということです...

public void insert(Key key, Value value) {

Stack<Node> nodeStack = new Stack<>();
Stack<Key> keyStack = new Stack<>();
Stack<Value> valStack = new Stack<>();

nodeStack.push(root);
keyStack.push(key);
valStack.push(value);

boolean done = false;

while(!done) {
   //here you cut-past the 3-parameter insert method...
   //BUT...
   //replace all uses have h, key, and value with stack.peek() calls
   //push new items to each stack everytime you call insert(Node n, Key k, Value v) (and do a continue)
   //pop items from each stack each time you leave insert
   //set done to true when the recurssion should end

         //you also MAY need some a Node var to hold the last returned value
}

 root.color = BLACK;
}

話の教訓は...ソフトウェアスタックを独自のいくつかのスタックに置き換える必要があるということです。上記の概要は完璧ではないかもしれませんが、その出発点です。

好奇心から、あなたは何を尋ねますか?

于 2013-03-27T21:53:55.003 に答える