0

これが尋ねられた場合は申し訳ありませんが、検索中に見つけることができませんでした..すべての検索結果は、特定のノードを検索しているかのようにバイナリツリーをトラバースすることに関するものでした-したがって、ダウンしてしまいます.左または右など。

しかし、トラバースしてツリーのサイズを更新する場合はどうでしょうか。下部に新しいノードを追加したとします。その後、各ノードのサイズを更新して、新しいツリー サイズを反映する必要があります。

これが元のツリーで、Z を追加するとします。

    D              D
   / \            / \
  A   S   -->    A   S
     /              / \
    N              N   Z
(size = 4)      (size = 5)

したがって、サイズを更新するには、私が間違っていると考えていない限り、その上のノードを更新する前に、まず下のノードを更新する必要があります。右？(D を更新するには、まず S と A を更新する必要があります)

では、ルートからボトムまでトラバースし、ボトムアップで更新するにはどうすればよいでしょうか?

4

1 に答える 1

0

各サブツリーのサイズを保存するためのユースケースが何であるかはまだわかりませんが、再帰に頼らずに各挿入中に更新を維持するのは簡単です。簡単にするために、次の定義から始めるとします。

public static class BSTNode
{
    public BSTNode leftTree = null;
    public BSTNode rightTree = null;
    public int subtreeSize = 1;
    public int value;

    public BSTNode(int valToAdd){
        value = valToAdd;
    }
}

public static class BST
{
    public BSTNode root;

    //public void insert(int valToAdd)
}

の実装ではinsert、ルートから開始し、ツリーをトラバースして、新しい値を追加する適切な場所を見つけます。進むにつれて、各サブツリーのサイズを更新できます。簡単な実装は次のようになります。

public void insert(int valToAdd)
{
    if(root == null){
        root = new BSTNode(valToAdd);
        return;
    }

    BSTNode parent = root;
    BSTNode current = root;
    while(current != null){
        parent = current;
        ++current.subtreeSize;
        if(valToAdd <= current.value){
            current = current.leftTree;
        }
        else{
            current = current.rightTree;                
        }
    }

    if(valToAdd <= parent.value){
        parent.leftTree = new BSTNode(valToAdd);
    }
    else{
        parent.rightTree = new BSTNode(valToAdd);
    }
}

サブツリーの高さを追跡するなど、下から更新したい場合があります (リバランスで使用される可能性があります)。定義BSTNodeが次のようになっているとします。

public static class BSTNode
{
    public BSTNode leftTree = null;
    public BSTNode rightTree = null;
    public int height = 0;
    public int value;

    public BSTNode(int valToAdd){
        value = valToAdd;
    }
}

ではinsert、Stack(または LIFO セマンティクスを提供できるもの) を使用して、新しく挿入されたノードの祖先を格納します。前の簡単な例を変更します。

public void insert(int valToAdd)
{
    if(root == null){
        root = new BSTNode(valToAdd);
        return;
    }

    java.util.Stack<BSTNode> stack = new java.util.Stack<BSTNode>();

    BSTNode parent = root;
    BSTNode current = root;
    while(current != null){
        parent = current;
        stack.push(current);
        if(valToAdd <= current.value){
            current = current.leftTree;
        }
        else{
            current = current.rightTree;                
        }
    }

    if(valToAdd <= parent.value){
        parent.leftTree = new BSTNode(valToAdd);
    }
    else{
        parent.rightTree = new BSTNode(valToAdd);
    }

    int height = 1;
    while(!stack.isEmpty()){
        current = stack.pop();
        current.height = Math.max(height, current.height);
        ++height;
    }
}
于 2014-04-09T19:37:59.353 に答える