my23tree.java

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

/*
 * Created on 2005-5-14
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
package treeNode;

/**
 * @author ade
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
import java.io.Serializable;
/**
 * <p>Title: class My23Tree</p>
 * <p>Description: 实现一个3阶B-树(2-3树).</p>
 * <p>Copyright: Copyright (c) 2004</p>
 * @author WLD
 * @version 1.0
 */

public class My23Tree implements Serializable
{
  private My23TreeNode root;   // 根结点

  // public methods
  // 默认构造方法. 构造一个空的B-树
  public My23Tree() {
    root = null;
  }

  // 插入关键字。若成功则返回true，存在相同关键字则返回false
  public boolean insertKey( AbstractKey key, Object record )
  {
    if( root == null )  // 如果树为空，建立新结点
    {
      root = new My23TreeNode(key, record, null);
    }
    else  // 树非空
    {
      SearchResult result = search( key ); // 先进行查找以确定插入位置
      if( result.isFound() )               // 存在相同结点，插入失败
        return false;
      else   // 不存在相同结点，且确定插入位置
      {
        My23TreeNode p = result.getNode();  // 插入位置
        My23TreeNode q = null;              // 分裂时新建立的结点
        int index = result.getIndex();
        while( p.insertKeyAt(key, record, index) == false ) // 需进行结点分裂
        {
          if( q != null )
          {
            p.children[index + 1] = q;      // 更新children引用
          }
          q = new My23TreeNode(p.keys[3], p.records[3], p.parent); // 建立新结点
          q.children[0] = p.children[2];    // 更新children引用
          q.children[1] = p.children[3];
          if( q.children[0] != null ) q.children[0].parent = q; // 更新parent的children指针
          if( q.children[1] != null ) q.children[1].parent = q;
          key = p.keys[2];
          record = p.records[2];
          p.keyNum = 1;          // 修改原结点
          p.keys[2] = p.keys[3] = null;
          p.records[2] = p.records[3] = null;
          p.children[2] = p.children[3] = null;
          if( p.parent == null ) // 若p为根结点，则建立新的根结点
          {
            p.parent = new My23TreeNode( key, record, null );
            p.parent.children[0] = p;
            p.parent.children[1] = q;
            root = p.parent;
            q.parent = p.parent;
            q = null;
            break;
          }
          for( index = 0; p.parent.children[index] != p && index < 2; index++ );
          p = p.parent;          // 更新p和index用于继续向parent插入关键字
        }
        if( q != null )
        {
          p.children[index + 1] = q;  // 如有必要，更新children引用
        }
      }
    }
    return true;
  }

  // 删除关键字
  public Object deleteKey( AbstractKey key )
  {
    SearchResult result = search( key ); // 先进行查找以确定插入位置
    if( !result.isFound() )   // 未找到关键字，删除失败
      return null;
    else    // 找到了关键字
    {
      My23TreeNode p = result.getNode();
      int index = result.getIndex();
      deleteKey( p, index );   // 调用私有方法删除结点p上的第index个关键字
      return result.getRecord();
    }
  }

  // 查找关键字。找到则返回指向记录的引用，否则返回null
  public Object searchByKey( AbstractKey key )
  {
    return search(key).getRecord();
  }

  // 以字符串形式输出树的信息
  public String toString()
  {
    return root == null? "" : toString(root, "", false);
  }

  // private methods
  // 私有方法deleteKey删除给定结点p上的第index个关键字
  private void deleteKey( My23TreeNode p, int index )
  {
    if( p.children[0] == null )  // p为最下层结点
    {
      if( p.keyNum > 1 ) // 关键字大于1或为根结点，直接删除即可
      {
        p.deleteKeyAt(index);
        p.keys[p.keyNum+1] = null;
        p.records[p.keyNum+1] = null;
        p.children[p.keyNum+1] = null;
      }
      else               // 否则就麻烦些
      {
        if( p == root )  // 整棵树就一个根结点且就包含一个关键字，删除后即为空树一棵
        {
          root = null;
          return;
        }
        int indexInParent = 0;
        if( p.parent.children[1] == p ) indexInParent = 1;
        else if( p.parent.children[2] == p ) indexInParent = 2;  // 确定p在其parent中的位置
        // 右边的兄弟有足够的关键字，就借一个给parent，并把parent中的拿来给自己
        if( indexInParent < p.parent.keyNum && p.parent.children[indexInParent+1].keyNum > 1 )
        {
          p.keys[index] = p.parent.keys[indexInParent + 1];
          p.records[index] = p.parent.records[indexInParent + 1];

          p.parent.keys[indexInParent + 1] =
              p.parent.children[indexInParent + 1].keys[1];
          p.parent.records[indexInParent + 1] =
              p.parent.children[indexInParent + 1].records[1];

          p.parent.children[indexInParent + 1].keys[1] =
              p.parent.children[indexInParent + 1].keys[2];
          p.parent.children[indexInParent + 1].records[1] =
              p.parent.children[indexInParent + 1].records[2];

          p.parent.children[indexInParent + 1].keys[2] = null;
          p.parent.children[indexInParent + 1].records[2] = null;
          p.parent.children[indexInParent + 1].keyNum = 1;
          return;
        }
        // 左边的兄弟有足够的关键字
        if( indexInParent > 0 && p.parent.children[indexInParent-1].keyNum > 1 )
        {
          p.keys[index] = p.parent.keys[indexInParent];
          p.records[index] = p.parent.records[indexInParent];

          p.parent.keys[indexInParent] =
              p.parent.children[indexInParent - 1].keys[2];
          p.parent.records[indexInParent] =
              p.parent.children[indexInParent - 1].records[2];

          p.parent.children[indexInParent - 1].keys[2] = null;
          p.parent.children[indexInParent - 1].records[2] = null;
          p.parent.children[indexInParent - 1].keyNum = 1;
          return;
        }
        // 所有相邻兄弟的关键字数目均为1...
        if (indexInParent < p.parent.keyNum) { // 右面有兄弟，向右合并
          p.parent.children[indexInParent] = null;
          p.parent.children[indexInParent + 1].insertKeyAt(
              p.parent.keys[indexInParent + 1],
              p.parent.records[indexInParent + 1], 0);
          p.parent.deleteKeyAt(indexInParent + 1);
          p = p.parent.children[indexInParent + 1];
        }
        else { // 右面没兄弟左面一定有（B-Tree性质，且p不为根结点），向左合并
          p.parent.children[indexInParent] = null;
          p.parent.children[indexInParent - 1].insertKeyAt(
              p.parent.keys[indexInParent],
              p.parent.records[indexInParent], 1);
          p.parent.keys[indexInParent] = null;
          p.parent.records[indexInParent] = null;
          p.parent.keyNum--;
          p = p.parent.children[indexInParent - 1];
        }
        if (p.parent.keyNum > 0)     // parent中还有足够结点
          return;               // 删除完成。无需向上合并
        else { // parent已没有足够关键字，需要向上重复合并
          p.parent.keys[1] = p.keys[1];
          p.parent.keys[2] = p.keys[2];
          p.parent.records[1] = p.records[1];
          p.parent.records[2] = p.records[2];

          p.parent.children[0] = p.parent.children[1] =
              p.parent.children[2] = null;
          p.parent.keyNum = 2;
          p = p.parent;
          merge(p);
        }
      }
    } // if( p.children[0] == null )  // p为最下层结点
    else  // p非最下层结点
    {
      My23TreeNode q = p.children[index];
      while( q.children[0] != null )
        q = q.children[0];           // 找到对应子树中包含最小关键字的结点
      p.keys[index] = q.keys[1];     // 用对应子树中的最小关键字代替
      p.records[index] = q.records[1];
      deleteKey( q, 1 );             // 删除多余的最小关键字
    }
  }

  // 用于删除结点时“合并”的方法。将srcNode和其parent中的对应关键字一起合并到相邻兄弟结点
  // 此方法中并未删除任何关键字，只是对在deleteKey方法中删除掉关键字的树进行整理合并
  private void merge( My23TreeNode node )
  {
    if( node == root ) return;

    int indexInParent = 0;
    if (node.parent.children[1] == node) indexInParent = 1;
    else if (node.parent.children[2] == node) indexInParent = 2; // 确定node在其parent中的位置

    while( true )
    {
      if (indexInParent < node.parent.keyNum) { // node右面有兄弟，向右合并