java - java中批量插入二叉树

Question

我正在实现对二叉树进行多次插入的功能。首先对我得到的元素 vector 进行排序，然后在循环中调用单个元素的普通树插入函数，这是正确的吗？或者有更有效的策略？谢谢!

@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;
    }
}   

Answer 1

You have to balance the tree after insertion .

这是我的实现:

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