my23tree.java

来自「j2se程序」· Java 代码 · 共 469 行 · 第 1/2 页

        node.parent.children[indexInParent + 1].insertKeyAt(
            node.parent.keys[indexInParent + 1],
            node.parent.records[indexInParent + 1], 0);
        node.parent.children[indexInParent + 1].children[0] = node;
        node.parent.deleteKeyAt(indexInParent + 1);
        node.parent = node.parent.children[indexInParent];
        node = node.parent;//.children[indexInParent]; // 指向合并后的结点
      }
      else { // 否则向左合并（右面没有左面必有）
        node.parent.children[indexInParent - 1].insertKeyAt(
            node.parent.keys[indexInParent],
            node.parent.records[indexInParent],
            node.parent.children[indexInParent - 1].keyNum);
        node.parent.children[indexInParent - 1].children[node.parent.children[indexInParent - 1].keyNum] =
            node;
        node.parent.keys[indexInParent] = null;
        node.parent.records[indexInParent] = null;
        node.parent.children[indexInParent] = null;
        node.parent.keyNum--;
        indexInParent--;
        node.parent = node.parent.children[indexInParent];
        node = node.parent;//.children[indexInParent]; // 指向合并后的结点
      }
      if (node.keyNum == 3)  // 还需要分裂
      {
        My23TreeNode ap = new My23TreeNode( node.keys[3], node.records[3], node.parent );
        ap.children[0] = node.children[2];
        ap.children[1] = node.children[3];
        ap.children[0].parent = ap.children[1].parent = ap;
        node.children[2] = node.children[3] = null;
        node.parent.insertKeyAt( node.keys[2], node.records[2], indexInParent );
        node.keys[2] = node.keys[3] = null;
        node.records[2] = node.records[3] = null;
        node.keyNum = 1;
        node.parent.children[indexInParent] = node;
        node.parent.children[indexInParent+1] = ap;
      }
      if( node.parent.keyNum > 0 )
        break;  // 合并终于结束
      else
      {
        if( node.parent == root )
        {
          root = node;
          root.parent = null;
          break;
        }
        else
        {
          indexInParent = 0;
          if (node.parent.parent.children[1] == node.parent)
            indexInParent = 1;
          else if (node.parent.parent.children[2] == node.parent)
            indexInParent = 2; // 确定node的空parent在其grandparent中的位置
          node.parent.parent.children[indexInParent] = node;
          node.parent = node.parent.parent;  // 忽略掉空的parent，继续往上合并
        }
      }
    } // while
  }

  // 以字符形式输出某一结点。showFailNode为false时不显示最下层空结点
  private String toString( My23TreeNode node, String space, boolean showFailNode )
  {
    StringBuffer str = new StringBuffer("");
    if( node == null && !showFailNode )
      return "";
    str.append(space);
    if (node == null)
      str.append("◎ F\n");
    else {
      str.append("● " + node.toString() + "\n");
      if( space.length() > 0 )
      {
        space = space.substring(0, space.length() - 1) +
            (space.substring(space.length()-1).equals("├")?  "│":"　");
      }
      for (int i = 0; i < node.keyNum + 1; i++) {
        str.append(toString(node.children[i],
                            space + (i == node.keyNum? "└":"├"), showFailNode));
      }
    }
    return str.toString();
  }

  // 在树中查找关键字key并返回SearchResult型的结果
  private SearchResult search( AbstractKey key )
  {
    My23TreeNode p = root, q = null;
    boolean found = false;
    int i = 0;
    while( p != null && !found )
    {
      i = p.search(key);
      if( i > 0 && p.keys[i].compare(key) == 0 ) found = true;
      else
      {
        q = p;
        p = p.children[i];
      }
    }
    if( found ) return new SearchResult(p, i, true);
    else return new SearchResult(q, i, false);
  }

  //************************************************************************
  // B-Tree查找结果类
  //************************************************************************
  private class SearchResult implements Serializable
  {
    My23TreeNode node;
    int i;
    boolean found;

    public SearchResult( My23TreeNode pt, int index, boolean tag )
    {
      node = pt;
      i = index;
      found = tag;
    }

    public My23TreeNode getNode() { return node; }
    public int getIndex() { return i; }
    public boolean isFound() { return found; }
    public Object getRecord() { return found? node.records[i] : null; }
  }

  //************************************************************************
  // 私有内类, B-树的结点类
  //************************************************************************
  private class My23TreeNode implements Serializable
  {
    // properties
    int keyNum;             // 关键字个数
    My23TreeNode parent;        // 父结点（引用）
    My23TreeNode[] children;    // 子结点向量（引用）
    AbstractKey[] keys;     // 关键字向量
    Object[] records;       // 记录向量（引用）


    // method
    // 默认构造方法，创建含一个关键字的结点
    public My23TreeNode( AbstractKey key, Object record, My23TreeNode parentNode )
    {
      keyNum = (key == null)? 0 : 1;
      parent = parentNode;
      children = new My23TreeNode[4];
      keys = new AbstractKey[4];
      records = new Object[4];
      for( int i = 0; i <= 3; i++ )
      {
        children[i] = null;
        keys[i] = null;
        records[i] = null;
      }
      keys[1] = key;
      records[1] = record;
    }

    // 以字符串返回结点信息（关键字列表）
    public String toString()
    {
      return toString(false, false);
    }

    // 可以选择是否现实parent和children信息
    private String toString( boolean showParent, boolean showChildren )
    {
      StringBuffer str = new StringBuffer();
      if( showParent )
      {
        str.append("[");
        str.append(parent);
        str.append("] ");
      }
      for( int i = 1; i <= keyNum; i++ )
      {
        str.append(keys[i]);
        if( i != keyNum ) str.append(", ");
      }
      if( showChildren )
      {
        for (int i = 0; i <= 3; i++) {
          str.append(" [");
          str.append(children[i]);
          str.append("]");
        }
      }

      return str.toString();
    }

    // 返回关键字key在结点中的位置
    private int search( AbstractKey key )
    {
      int i;
      for( i = 1; i <= keyNum; i++ )
      {
        if( keys[i].compare(key) > 0 )
          break;
      }
      return i - 1;
    }

    // 将关键字插入到结点的指定位置
    private boolean insertKeyAt( AbstractKey key, Object record, int index )
    {
      for(int i = keyNum; i > index; i--) {
        keys[i + 1] = keys[i];
        records[i+1] = records[i];
        children[i + 1] = children[i];
      }
      keys[index + 1] = key;
      records[index+1] = record;
      children[index + 1] = children[index];
      keyNum++;
      return keyNum < 3;
    }

    // 删除结点中指定位置的关键字
    private void deleteKeyAt( int index )
    {
      if( keyNum == 0 ) return;
      for( int i = index; i <= keyNum; i++ )
      {
        keys[i] = keys[i+1];
        records[i] = records[i+1];
        children[i-1] = children[i];
      }
      keyNum--;
    }
  }
}