B树的实现与源代码二（删除源代码）
2024-10-18 20:30:44
int BTreeMaximum( BNode *x )
{
if ( x->leaf )
{
return x->key[x->size - 1];
}
else
{
return BTreeMaximum( x->child[x->size] );
}
} int BTreeMinimum( BNode *x )
{
if ( x->leaf )
{
return x->key[0];
}
else
{
return BTreeMinimum( x->child[0] );
}
} void BTreeDelete( BNode *&x, int k )
{
int i = 0;
while ( i < x->size && k > x->key[i] )
{
i++;
}
// case 1
if ( i < x->size && k == x->key[i] && x->leaf )
{
for ( int j = i; j < x->size - 1; ++j )
{
x->key[j] = x->key[j + 1];
}
x->size--;
}
// case 2
else if ( i < x->size && k == x->key[i] && !x->leaf )
{
BNode *y = x->child[i];
BNode *z = x->child[i + 1];
// 2a
if ( y->size >= t )
{
int k_ = BTreeMaximum( y );
x->key[i] = k_;
BTreeDelete( y, k_ );
}
// 2b
else if ( z->size >= t )
{
int k_ = BTreeMinimum( z );
x->key[i] = k_;
BTreeDelete( z, k_ );
}
// 2c
else
{
// update the node y
y->key[t - 1] = k;
for ( int j = t; j < 2 * t - 1; ++j )
{
y->key[j] = z->key[j - t];
y->child[j] = z->child[j - t];
}
y->child[2 * t - 1] = z->child[t - 1];
y->size = y->size + z->size + 1; // update the node x
for ( int j = i; j < x->size - 1; ++j )
{
x->key[j] = x->key[j + 1];
x->child[j + 1] = x->child[j + 2];
}
x->size--; // delete z
delete z;
BTreeDelete( y, k );
} // end else 2c
} // end if case 2
// case 3
else if ( i <= x->size )
{
if ( x->child[i]->size == t - 1 )
{
if ( i > 0 && x->child[i - 1]->size >= t )
{
// update x->child[i]
for ( int j = t - 2; j >= 0; --j )
{
x->child[i]->key[j + 1] = x->child[i]->key[j];
if ( !x->child[i]->leaf )
{
x->child[i]->child[j + 2] = x->child[i]->child[j + 1];
}
}
x->child[i]->child[1] = x->child[i]->child[0];
x->child[i]->key[0] = x->key[i - 1];
x->child[i]->child[0] = x->child[i - 1]->child[x->child[i - 1]->size];
x->child[i]->size++;
// update x
x->key[i - 1] = x->child[i - 1]->key[x->child[i - 1]->size - 1];
// update x->child[i - 1]
x->child[i - 1]->size--;
BTreeDelete( x->child[i], k );
}
else if ( i < x->size && x->child[i + 1]->size >= t )
{
// update x->child[i]
x->child[i]->key[t - 1] = x->key[i];
x->child[i]->child[t] = x->child[i - 1]->child[0];
x->child[i]->size++;
//update x
x->key[i] = x->child[i - 1]->key[0];
//update x->child[i - 1]
for ( int j = 0; j < x->child[i - 1]->size - 1; ++j )
{
x->child[i - 1]->key[j] = x->child[i - 1]->key[j + 1];
x->child[i - 1]->child[j] = x->child[i - 1]->child[j + 1];
}
x->child[i - 1]->child[x->child[i - 1]->size - 1] = x->child[i - 1]->child[x->child[i - 1]->size];
x->child[i - 1]->size--;
BTreeDelete( x->child[i], k );
}
// case 3b
// merge with the left node x->child[i - 1]
else if ( i > 0 )
{
// update x->child[i - 1]
x->child[i - 1]->key[t - 1] = x->key[i - 1];
for ( int j = t; j < 2 * t - 1; ++j )
{
x->child[i - 1]->key[j] = x->child[i]->key[j - t];
x->child[i - 1]->child[j] = x->child[i]->child[j - t];
}
x->child[i - 1]->child[2 * t - 1] = x->child[i]->child[t - 1];
x->child[i - 1]->size = 2 * t - 1;
// delete x->child[i]
delete x->child[i];
// update x
for ( int j = i; j < x->size; ++j )
{
x->key[i - 1] = x->key[i];
x->child[i] = x->child[i + 1];
}
x->size--;
if ( x->size == 0 )
{
x = x->child[0];
BTreeDelete( x, k );
}
else
{
BTreeDelete( x->child[i - 1], k );
}
}
// merge with the right node x->child[i + 1]
else if ( i < x->size )
{
// update x->child[i]
x->child[i]->key[t - 1] = x->key[i];
for ( int j = t; j < 2 * t - 1; ++j )
{
x->child[i]->key[j] = x->child[i + 1]->key[j - t];
x->child[i]->child[j] = x->child[i + 1]->child[j - t];
}
x->child[i]->child[2 * t - 1] = x->child[i + 1]->child[t - 1];
x->child[i]->size = 2 * t - 1;
// delete x->child[i + 1]
delete x->child[i + 1];
// update x
for ( int j = i; j < x->size - 1; ++j )
{
x->key[j] = x->key[j + 1];
x->child[j + 1] = x->child[j + 2];
}
x->size--;
if ( x->size == 0 )
{
x = x->child[0];
BTreeDelete( x, k );
}
else
{
BTreeDelete( x->child[i - 1], k );
}
}
} // end if case 3
else
{
BTreeDelete( x->child[i], k );
}
//
} }
最新文章
- CentOS7：安装Puppet
- 电赛总结（二）——AD芯片总结之高速AD9224
- Ubuntu中Eclipse安装与配置
- hdu4714Tree2cycle
- DDD的好文章
- 如何扩展大规模Web网站的性能？
- linux shell pushd popd dirs命令
- ssh配置事务
- BZOJ1668: [Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富
- 通过SVG与CSS3实现向上图标
- 51ak带你看MYSQL5.7源码2：编译现有的代码
- 基于hashchange导航管理
- 【NOI赛前训练】——专项测试1·网络流
- luoguP4705 玩游戏
- Python成绩雷达图
- Math中的floor,round和ceil方法总结
- CSS3实战开发: 折角效果实战开发
- Smart Disk -- proposed by Liyuan Liu
- Answer the questions（回答自己的问题）
- 递归查询SQL语句