1

二分木に複数挿入する機能を実装しています。最初に取得した要素のベクトルを並べ替えてから、単一の要素に対してループの通常のツリー挿入関数を呼び出すのは正しいでしょうか？または、より効率的な戦略がありますか？ありがとう！

@Override
public void insert(Vector<V> vec) {
    insert(root,vec);
}

private void insert(Node<V> node, Vector<V> vec){
    Collections.sort(vec);
    for(int i = 0; i < vec.size(); i++){
        insert(root, vec.get(i));
    }       
}

@Override
public void insert(V obj) {
    root = insert(root, obj);
}

private Node<V> insert(Node<V> node,V data){
    if(node == null){
        return node = new Node<V>(data,null,null);          
    }
    else{
        if(data.compareTo(node.data) < 0){
            node.left = insert(node.left,data);         
        }
        else{
            node.right = insert(node.right,data);                            
        }
        return node;
    }
}
4

2 に答える 2

0

挿入後、ツリーのバランスを取る必要があります。

これが私の実装です：

public class Tree< T extends Comparable< T >>
{
   public static< T extends Comparable< T >> int getDepth( Tree< T > node )
   {
      return
         ( node == null )
            ? 0
            : ( 1 + Math.max( getDepth( node._left  ),
                              getDepth( node._right )));
   }// int getDepth()



   public Tree( T t )
   {
      _data  = t;
      _left  = null;
      _right = null;
      _count = 1;
   }// Tree( T t )



   public Tree< T > add( Tree< T > child )
   {
      Tree< T > root = this;
      int cmp = _data.compareTo( child._data );
      if( cmp > 0 )
      {
         if( _left == null )
         {
            _left = child;
         }
         else
         {
            _left = _left.add( child );
         }// if
         _count += child._count;
         if( _left._count > (( _right == null ) ? 0 : _right._count ) + 1 )
         {
            root = _left;
            _count -= root._count;
            _left = null;
            if( root._right == null )
            {
                root._right = this;
            }
            else
            {
               root._right = root._right.add( this );
            }// if
            root.updateCount();
         }// if
      }
      else if( cmp < 0 )
      {
         if( _right == null )
         {
            _right = child;
         }
         else
         {
            _right = _right.add( child );
         }// if
         _count += child._count;
         if( _right._count > (( _left == null ) ? 0 : _left._count ) + 1 )
         {
            root = _right;
            _count -= root._count;
            _right = null;
            if( root._left == null )
            {
               root._left  = this;
            }
            else
            {
               root._left = root._left.add( this );
            }// if
            root.updateCount();
         }// if
      }// if
      return root;
   }// Tree< T > add( Tree< T > child )



   public int getCount()
   {
      return _count;
   }// int getCount()



   @Override
   public String toString()
   {
      return _data.toString();
   }// String toString()



   private void updateCount()
   {
      _count =
         1 +
         (( _left  == null ) ? 0 : _left._count  ) +
         (( _right == null ) ? 0 : _right._count );
   }// void updateCount()



   public final T         _data;
   public /* */ Tree< T > _left;
   public /* */ Tree< T > _right;
   public /* */ int       _count;

}// class Tree
于 2012-11-06T13:35:38.233 に答える
0

検討

  • ツリーへのリストの挿入: ソートすると、左または右のノードのみが埋められたリストが作成されます。
  • 挿入すると、バイナリ AVL ツリーのように、ツリーのバランスが取り直される可能性があります。欠点は、枝の穴です。K(F(A, -), P(-, T(R -))): 要素 6、深さ 4。最適な深さは 3 です。

リストを最小の深さのバイナリ ツリーに変換する場合: リストを並べ替え、インデックスに基づいてリスト上でツリーを作成します。

擬似コードでのツリー構築:

convertListToTree(list)
    list.sort();
    return subtreeOf(list, 0, list.size())

subtreeOf(list, from, to) {
    if (to - from <= 0)
        return null;
    int mid = (from + to) / 2;
    return new Node(list.get(mid),
                    subTreeOf(list, from, mid),
                    subTreeOf(list, mid + 1, to));
}
于 2018-02-02T11:32:13.097 に答える