algorithm - 二分探索木に対する反復子の実装

Question

私は最近、さまざまな二分探索木の実装 (AVL、splay、treap) をコーディングしており、これらの構造をトラバースするイテレータを記述する特に「良い」方法があるかどうかに興味があります。私が現在使用している解決策は、BST 内の各ノードに、ツリー内の次の要素と前の要素へのポインタを格納させることです。これにより、反復が標準のリンク リスト反復に減少します。しかし、私はこの答えに本当に満足していません。これは、各ノードのスペース使用量を 2 つのポインター (次と前) だけ増やします。

スタックを使用してフロンティア ノードを追跡し、後で探索することにより、O(h) 補助ストレージ スペース (h はツリーの高さ) を使用する二分探索ツリー イテレータを構築する方法を知っていますが、私は'メモリ使用量のために、これをコーディングすることに抵抗しました。一定のスペースのみを使用するイテレータを作成する方法があることを期待していました。

私の質問はこれです-次のプロパティを持つ二分探索木に対して反復子を設計する方法はありますか?

1. 要素は昇順でアクセスされます (つまり、順不同の走査)
2. next()hasNext()クエリは O(1) 時間で実行されます。
3. メモリ使用量は O(1)

簡単にするために、反復中にツリー構造の形状が変化しない (つまり、挿入、削除、または回転がない) と仮定しても問題ありませんが、これを実際に処理できるソリューションがあれば非常にクールです。

Answer 1

可能な限り最も単純なイテレータは、最後に表示されたキーを格納し、次の反復で、そのキーの最小の上限をツリーで検索します。反復はO（log n）です。これには、非常に単純であるという利点があります。キーが小さい場合、イテレータも小さくなります。もちろん、ツリーを反復処理する方法が比較的遅いという欠点があります。また、一意でないシーケンスでは機能しません。

一部のツリーは、スキャンが非常に高速であることが特定の用途にとって重要であるため、すでに使用している実装を正確に使用します。各ノードのキーの数が多い場合、兄弟ポインターを格納することによるペナルティはそれほど面倒ではありません。ほとんどのBツリーはこの方法を使用します。

多くの検索ツリーの実装では、他の操作を簡素化するために、各ノードに親ポインターを保持しています。それがある場合は、最後に表示されたノードへの単純なポインターをイテレーターの状態として使用できます。各反復で、最後に表示されたノードの親で次の子を探します。兄弟がもういない場合は、もう1つレベルを上げます。

これらの手法のいずれも適切でない場合は、イテレータに格納されているノードのスタックを使用できます。これは、通常どおり検索ツリーを反復処理するときに関数呼び出しスタックと同じ機能を果たしますが、兄弟をループして子を繰り返す代わりに、子をスタックにプッシュして、連続する各兄弟を返します。

Answer 2

TokenMacGuy が述べたように、イテレータに格納されたスタックを使用できます。これをJavaで簡単にテストした実装を次に示します。

/**
 * An iterator that iterates through a tree using in-order tree traversal
 * allowing a sorted sequence.
 *
 */
public class Iterator {

    private Stack<Node> stack = new Stack<>();
    private Node current;

    private Iterator(Node argRoot) {
        current = argRoot;
    }

    public Node next() {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        current = stack.pop();
        Node node = current;
        current = current.right;

        return node;
    }

    public boolean hasNext() {
        return (!stack.isEmpty() || current != null);
    }

    public static Iterator iterator(Node root) {
        return new Iterator(root);
    }
}

他のバリエーションは、構築時にツリーをトラバースし、トラバーサルをリストに保存することです。後でリスト反復子を使用できます。

Answer 3

わかりました、これが古いことは知っていますが、しばらく前にマイクロソフトとのインタビューでこれを尋ねられたので、少し作業することにしました. 私はこれをテストしましたが、非常にうまく機能します。

template <typename E>
class BSTIterator
{  
  BSTNode<E> * m_curNode;
  std::stack<BSTNode<E>*> m_recurseIter;

public:
    BSTIterator( BSTNode<E> * binTree )
    {       
        BSTNode<E>* root = binTree;

        while(root != NULL)
        {
            m_recurseIter.push(root);
            root = root->GetLeft();
        }

        if(m_recurseIter.size() > 0)
        {
            m_curNode = m_recurseIter.top();
            m_recurseIter.pop();
        }
        else
            m_curNode = NULL;
    }

    BSTNode<E> & operator*() { return *m_curNode; }

    bool operator==(const BSTIterator<E>& other)
    {
        return m_curNode == other.m_curNode;
    }

    bool operator!=(const BSTIterator<E>& other)
    {
        return !(*this == other);
    }

    BSTIterator<E> & operator++() 
    { 
        if(m_curNode->GetRight())
        {
            m_recurseIter.push(m_curNode->GetRight());

            if(m_curNode->GetRight()->GetLeft())
                m_recurseIter.push(m_curNode->GetRight()->GetLeft());
        }

        if( m_recurseIter.size() == 0)
        {
            m_curNode = NULL;
            return *this;
        }       

        m_curNode = m_recurseIter.top();
        m_recurseIter.pop();

        return *this;       
    }

    BSTIterator<E> operator++ ( int )
    {
        BSTIterator<E> cpy = *this;     

        if(m_curNode->GetRight())
        {
            m_recurseIter.push(m_curNode->GetRight());

            if(m_curNode->GetRight()->GetLeft())
                m_recurseIter.push(m_curNode->GetRight()->GetLeft());
        }

        if( m_recurseIter.size() == 0)
        {
            m_curNode = NULL;
            return *this;
        }       

        m_curNode = m_recurseIter.top();
        m_recurseIter.pop();

        return cpy;
    }

};

Answer 4

ウィキペディアからのツリートラバーサル：

すべてのサンプル実装では、ツリーの高さに比例するコール スタック スペースが必要になります。バランスの取れていないツリーでは、これはかなりの量になる可能性があります。

各ノードで親ポインターを維持するか、ツリーをスレッド化することで、スタック要件を取り除くことができます。スレッドを使用する場合、これによりインオーダー トラバーサルが大幅に改善されますが、プリオーダーおよびポストオーダー トラバーサルに必要な親ノードの取得は、単純なスタック ベースのアルゴリズムよりも遅くなります。

この記事には、O(1) 状態の反復のための疑似コードがいくつかあります。これは、反復子に簡単に適用できます。

Answer 5

O(1) スペースを使用します。つまり、O(h) スタックは使用しません。

始める：

1. 次()を持っていますか? current.val <= endNode.val は、ツリーが完全にトラバースされているかどうかを確認します。

2. 左端から最小値を見つける: 次の最小値を見つけるために常に左端を探すことができます。

3. 一番左の min がチェックされたら (名前を付けますcurrent)。次の分は 2 つのケースになります: current.right != null の場合、次の分として current.right の左端の子を探し続けることができます。または、親を遡る必要があります。二分探索木を使用して、現在の親ノードを見つけます。

注: 親のバイナリ検索を行うときは、parent.left = current を満たしていることを確認してください。

理由:parent.right == current の場合、その親は以前に訪問されている必要があります。二分探索木では、parent.val < parent.right.val であることがわかっています。無限ループにつながるため、この特殊なケースをスキップする必要があります。

public class BSTIterator {
    public TreeNode root;
    public TreeNode current;
    public TreeNode endNode;
    //@param root: The root of binary tree.
    public BSTIterator(TreeNode root) {
        if (root == null) {
            return;
        }
        this.root = root;
        this.current = root;
        this.endNode = root;

        while (endNode != null && endNode.right != null) {
            endNode = endNode.right;
        }
        while (current != null && current.left != null) {
            current = current.left;
        }
    }

    //@return: True if there has next node, or false
    public boolean hasNext() {
        return current != null && current.val <= endNode.val;
    }

    //@return: return next node
    public TreeNode next() {
        TreeNode rst = current;
        //current node has right child
        if (current.right != null) {
            current = current.right;
            while (current.left != null) {
                current = current.left;
            }
        } else {//Current node does not have right child.
            current = findParent();
        }
        return rst;
    }

    //Find current's parent, where parent.left == current.
    public TreeNode findParent(){
        TreeNode node = root;
        TreeNode parent = null;
        int val = current.val;
        if (val == endNode.val) {
            return null;
        }
        while (node != null) {
            if (val < node.val) {
                parent = node;
                node = node.left;
            } else if (val > node.val) {
                node = node.right;
            } else {//node.val == current.val
                break;
            }
        }
        return parent;
    }
}

Answer 6

定義上、next() と hasNext() を O(1) 時間で実行することはできません。BST の特定のノードを見ているとき、他のノードの高さと構造がわからないため、正しい次のノードに「ジャンプ」することはできません。

ただし、スペースの複雑さは O(1) に減らすことができます (BST 自体のメモリを除く)。Cで行う方法は次のとおりです。

struct node{
    int value;
    struct node *left, *right, *parent;
    int visited;
};

struct node* iter_next(struct node* node){
    struct node* rightResult = NULL;

    if(node==NULL)
        return NULL;

    while(node->left && !(node->left->visited))
        node = node->left;

    if(!(node->visited))
        return node;

    //move right
    rightResult = iter_next(node->right);

    if(rightResult)
        return rightResult;

    while(node && node->visited)
        node = node->parent;

    return node;
}

秘訣は、親リンクと各ノードの訪問済みフラグの両方を持つことです。私の意見では、これは追加のスペース使用量ではなく、単にノード構造の一部であると言えます。そして明らかに、 iter_next() は、ツリー構造の状態を変更せずに (もちろん) 呼び出さなければなりませんが、「訪問済み」フラグの値は変更されません。

iter_next() を呼び出して、このツリーのたびに値を出力するテスター関数を次に示します。

                  27
               /      \
              20      62
             /  \    /  \
            15  25  40  71
             \  /
             16 21

int main(){

    //right root subtree
    struct node node40 = {40, NULL, NULL, NULL, 0};
    struct node node71 = {71, NULL, NULL, NULL, 0};
    struct node node62 = {62, &node40, &node71, NULL, 0};

    //left root subtree
    struct node node16 = {16, NULL, NULL, NULL, 0};
    struct node node21 = {21, NULL, NULL, NULL, 0};
    struct node node15 = {15, NULL, &node16, NULL, 0};
    struct node node25 = {25, &node21, NULL, NULL, 0};
    struct node node20 = {20, &node15, &node25, NULL, 0};

    //root
    struct node node27 = {27, &node20, &node62, NULL, 0};

    //set parents
    node16.parent = &node15;
    node21.parent = &node25;
    node15.parent = &node20;
    node25.parent = &node20;
    node20.parent = &node27;
    node40.parent = &node62;
    node71.parent = &node62;
    node62.parent = &node27;

    struct node *iter_node = &node27;

    while((iter_node = iter_next(iter_node)) != NULL){
        printf("%d ", iter_node->value);
        iter_node->visited = 1;
    }
    printf("\n");
    return 1;
}

ソートされた順序で値を出力します：

15 16 20 21 25 27 40 62 71 

Answer 7

If you use stack, you only achieve "Extra memory usage O(h), h is the height of the tree". However, if you want to use only O(1) extra memory, you need to record the Here are the analysis: - If current node has right child: find min of right sub tree - It current node has no right child, you need to look for it from the root, and keep updating it's lowest ancestor, which is its lowest next node

public class Solution {
           //@param root: The root of binary tree.

           TreeNode current;
           TreeNode root;
           TreeNode rightMost;
           public Solution(TreeNode root) {

               if(root==null) return;
                this.root = root;
                current = findMin(root);
                rightMost = findMax(root);
           }

           //@return: True if there has next node, or false
           public boolean hasNext() {

           if(current!=null && rightMost!=null && current.val<=rightMost.val)    return true; 
        else return false;
           }
           //O(1) memory.
           public TreeNode next() {
                //1. if current has right child: find min of right sub tree
                TreeNode tep = current;
                current = updateNext();
                return tep;
            }
            public TreeNode updateNext(){
                if(!hasNext()) return null;
                 if(current.right!=null) return findMin(current.right);
                //2. current has no right child
                //if cur < root , go left; otherwise, go right

                    int curVal = current.val;
                    TreeNode post = null;
                    TreeNode tepRoot = root;
                    while(tepRoot!=null){
                      if(curVal<tepRoot.val){
                          post = tepRoot;
                          tepRoot = tepRoot.left;
                      }else if(curVal>tepRoot.val){
                          tepRoot = tepRoot.right;
                      }else {
                          current = post;
                          break;
                      }
                    }
                    return post;

            }

           public TreeNode findMin(TreeNode node){
               while(node.left!=null){
                   node = node.left;
               }
               return node;
           }

            public TreeNode findMax(TreeNode node){
               while(node.right!=null){
                   node = node.right;
               }
               return node;
           }
       }