Javaで完全なバイナリツリーにノードを挿入する方法は？

Question

私たちは皆知っているように、完全なバイナリツリーに挿入するときは、すべてのリーフのすべての子を左から右に塗りつぶす必要があります。私は完全なバイナリツリーにノードを挿入する次のメソッドを持っています。

//fields 
private T item; 
private int size; 
private CBTree<T> left, right; 

//add method 
public void add(T item) 
{ 
    if(left == null) 
    { 
     left = new CBTree<T>(item); 
     size += left.size; 
    } 
    else if(right == null) 
    { 
     right = new CBTree<T>(item); 
     size += right.size; 
    } 
    else if(!((left.left != null) && (left.right != null)) && 
      ((right.left == null) || (right.right == null))) 
    { 
     left.add(item); 
    } 
    else 
    { 
     right.add(item); 
    } 
} 

この実装に問題が11ノードの後に​​、それは次の行は、このツリーのルートを再割り当てされているので、私はこれが起こっていることを理解し8の代わりに、6の左の子に12ノードを追加することです根の左の子になる。

left.add(item); 

は、だから、元の値に戻すルートを変更する方法はあり2.にルートを変更していますか？私はスタックとキューを使用せずにこれを達成しようとしています。

Answer 1

Dukelingの答えのおかげで、メソッドを実装する正しい方法は、サブツリーがいっぱいだったかどうかを数学的に判断することでした。コードは次のとおりです。

//fields 
private T item; 
private int size; 
private CBTree<T> left, right; 

//add method 
public void add(T item) 
{ 
    if(left == null) 
    { 
     left = new CBTree<T>(item); 
    } 
    else if(right == null) 
    { 
     right = new CBTree<T>(item); 
    } 
    else if(leftFull()) 
    { 
     right.add(item); 
    } 
    else 
    { 
     left.add(item); 
    } 
    size++; 
} 

//Checks if the left subtree is full 
public boolean leftFull() 
{ 
    int used, leafs = 1; 
    while(leafs <= size + 1) 
    { 
     leafs *= 2; 
    } 

    leafs /= 2; 
    used = (size + 1) % leafs; 
    if(used >= (leafs/2)) 
    { 
     return true; 
    } 
    else 
    { 
     return false; 
    } 
} 

Answer 2

ツリーの高さが4に達すると直ちにルートが子どもの子供たちが変わることはないので、子どもの子どもを調べるだけでは不十分です私たちはまだ左または右のいずれかに行くことができます。

2アプローチが頭に浮かぶ：

1. は、各ノードでcomplete変数を持っています。

   子を持たないノードが完成しました。

   等しいサイズの2つの完全な子を持つノードが完成しました。

   ツリーを更新（挿入または削除）するたびに、影響を受けるノードごとにこの変数も更新します。

2. サイズに基づいてサブツリーが完成しているかどうかを数学的に判断します。

   サイズが2^n - 1のツリーが完成しました（一部はn）。

   注：これは、ツリーを完成させずに要素を自由に削除することができない場合にのみ機能します。アプローチのいずれかの場合

挿入を行う場合、これらの条件のいずれかに該当する場合、我々は（left.add(item)）左に行く：

• 左のサブツリーが
• 左と右のサブツリーを完了していません同じサイズです（両方とも、この挿入により高さが増していることを意味します）

実装の詳細はあなたに任せます。

---

注：left.add(item);とright.add(item);を行うときにもサイズを更新する必要があります。 add関数にsize++を貼り付けるだけです。なぜなら、1要素を追加して何があってもサイズが1増加するからです。