插入过程简单,讲解教程也多。
删除思路:非叶节点找替代结点,然后在相应子树中递归删除。叶结点直接删除。
删除完后判断是否要调整。在插入函数中有个find的辅助函数,定位关键值插入的结点和下标,但在删除函数中不能直接定位到删除的目标结点,必须逐层遍历。否则中间的层可能受影响但是略过了导致没有调整,要保证每层都进行判断。
一些特殊情况的处理:
调整函数中判断有没有左右兄弟,是否能借。
根结点删除至无,要指向新结点。怎么判断是不是根结点?只有根结点的关键值数量才会数量减为0,因为非根结点至少为M/2-1或M/2,会通过调整函数自动维护。M/2向上取整,不是整除。
非叶节点删除思路有两种。一种是直接在小于/大于关键值的子树选前驱/后继结点,然后在相应子树中(不可直接跳)递归删除。一种是根据前/后子树关键值的数量选择向哪个子树借,这种会面临一种特殊情况:要删除只有一个关键值的根结点,而左右子树中有M/2-1个关键值。这样两边都不能借,只能合并,然后还要改根结点指针,在新的根结点中删除。
最后就是一些细节,移动操作的for循环有没有等号,keynum要不要减一,数组下标是不是从0开始,等等,结合图走一遍就行。不熟多看几遍就记住了,回想起来才不会迷茫。
#include<queue>
template<class K, int M = 3>
struct BTreeNode {//M阶b树
K _key[M];//从0开始,M-1用于溢出时暂时存放
BTreeNode<K, M>* _sub[M + 1];//子树指针,从0开始,M+1暂时存放
BTreeNode<K, M>* _parent;
size_t _keynum;//关键字个数
BTreeNode() :_keynum(0), _parent(nullptr) {
memset(_sub, 0, sizeof(BTreeNode<K, M>*) * (M + 1));
}
};
template<class K, int M = 3>//M阶b树
class BTree {
typedef BTreeNode<K, M> BTNode;
BTNode* _root;
public:
BTree() :_root(nullptr) {}
~BTree() { destoryTree(_root); _root = nullptr; }
void levelorder() {
if (!_root) { cout << "levelorder,null" << endl; return; }
queue<BTNode*>q;
q.push(_root);
int a = 1, b;
BTNode* node;
while (!q.empty())
{
b = 0;
for (int j = 0; j < a; j++) {
node = q.front();
cout << " ( ";
for (int i = 0; i < node->_keynum; i++) {
cout << node->_key[i] << ",";
}
cout << ") ";
for (int i = 0; i <= node->_keynum; i++) {
if (node->_sub[i]) {
q.push(node->_sub[i]);
b++;
}
}
q.pop();
}
cout << endl;
a = b;
}
}
pair<BTNode*, int>find(const K& key) {
BTNode* parent = nullptr, * node = _root;
while (node) {
int i = 0;
while (i<node->_keynum && key>node->_key[i]) {
i++;//i最大等于_keynum,刚好是最右边的子树
}
if (i < node->_keynum && key == node->_key[i]) {
return make_pair(node, i);//返回关键值所在结点和下标
}//找到关键值
parent = node;
node = node->_sub[i];//到key[i]右边的子树找
}
return make_pair(parent, -1);//没找到
}
bool insert(K key) {
if (_root == nullptr) {
_root = new BTNode;
_root->_key[0] = key;
_root->_keynum++;
return true;
}//空树
pair<BTNode*, int> result = find(key);
if (result.second != -1)return false;//关键值已存在
K k = key;
BTNode* node = result.first;
BTNode* sub = nullptr;//新关键值插入的结点必为叶结点,子树为空
while (1) {
_insert(node, k, sub);//先插入再判断
if (node->_keynum < M)return true;//关键值没满
//结点分裂,将大于“中间值”[M/2]的关键值及子树分裂到新结点中
BTNode* temp = new BTNode;
for (int i = M / 2 + 1, j = 0; i < M; i++, j++) {//移动关键值
temp->_key[j] = node->_key[i];
node->_keynum--;
temp->_keynum++;
}
for (int i = M / 2 + 1, j = 0; i <= M; i++, j++) {//移动子树
if (node->_sub[i]) {
temp->_sub[j] = node->_sub[i];//大于关键值的子树移到新结点
//if (node->_sub[i])node->_sub[i]->_parent = temp;//更新双亲结点
//node->_sub[i]->_parent = temp;//更新双亲结点
temp->_sub[j]->_parent = temp;//更新双亲结点
node->_sub[i] = nullptr;//清空
}
}
k = node->_key[M / 2];//中间上移的关键值,插入到双亲结点,M/2
node->_keynum--;
if (node->_parent == nullptr) {//分裂到根结点了,新建根结点
_root = new BTNode;
_root->_key[0] = k;
_root->_keynum = 1;
_root->_sub[0] = node;
_root->_sub[1] = temp;//两个子树
temp->_parent = _root;
node->_parent = _root;
return true;
}
node = node->_parent;//分裂出来的关键值和新结点插入到父结点中
sub = temp;
}
}
bool remove(K key) {
return remove(_root, key);
}
private:
void shownode(BTNode* node) {//输出结点的关键值
if (!node) {
cout << "shownode, null" << endl;
return;
}
for (int i = 0; i < node->_keynum; i++)cout << node->_key[i] << ",";
cout << endl;
}
bool remove(BTNode* node, K key) {
if (!node)return false;
bool result = false;
pair<bool, int> ret = get_keyindex(node, key);
int index = ret.second;//关键值是否在此结点中
if (ret.first) {
result = true;
if (is_leaf(node)) {//已经是叶结点,直接删除
for (int i = index; i < node->_keynum - 1; i++) {
node->_key[i] = node->_key[i + 1];
}
node->_keynum--;
if (_root->_keynum == 0) {//只剩根结点也为叶结点,且无关键值
cout << "_root->_keynum == 0 " << endl;
delete _root;
_root = nullptr;
}
return true;
}
else {//不是叶结点,用子树中最小的关键值代替,和BST类似
BTNode* pre = node->_sub[index];//小于关键值的子树
BTNode* next = node->_sub[index + 1];//大于关键值的子树
if (pre->_keynum >= (M + 1) / 2) {//用前驱代替
//cout << "get pre" << endl;
for (; pre->_sub[pre->_keynum] != nullptr; pre = pre->_sub[pre->_keynum]);
node->_key[index] = pre->_key[pre->_keynum - 1];
remove(node->_sub[index], pre->_key[pre->_keynum - 1]);//在子树中递归的删除代替的关键值
}
else if (next->_keynum >= (M + 1) / 2) {//后继代替
for (; next->_sub[0] != nullptr; next = next->_sub[0]);
node->_key[index] = next->_key[0];
remove(node->_sub[index + 1], next->_key[0]);//在右子树中递归的删除代替的关键值//不能直接的跳到next删除
}
else {
merge(node, index);//子树next和pre合并再删除
remove(pre, key);
node = pre;//更新结点,方便检查是否需要调整
}
}
}
else result = remove(node->_sub[index], key);//在相应子树中找
if (node->_sub[index] && node->_sub[index]->_keynum < (M + 1) / 2 - 1) //删除完了检查子树是否需要调整
{
adjust(node, index);//子树index需要调整
}
return result;
}
void adjust(BTNode* node, int index) {
BTNode* sub = node->_sub[index];
BTNode* left = index > 0 ? node->_sub[index - 1] : nullptr;
BTNode* right = index < node->_keynum ? node->_sub[index + 1] : nullptr;
//BTNode* right = index < M - 1 && index < node->_keynum ? node->_sub[index + 1] : nullptr;
if (right && right->_keynum >= (M + 1) / 2) {//有右兄弟且可借
sub->_key[sub->_keynum++] = node->_key[index];//父结点借给sub
node->_key[index] = right->_key[0];//right借给父
right->_keynum--;
for (int i = 0; i < right->_keynum; i++) {//right借了一个关键值,往左填补空位
right->_key[i] = right->_key[i + 1];
}
if (right->_sub[0]) {//借的关键值的子树也要移动
sub->_sub[sub->_keynum] = right->_sub[0];
for (int i = 0; i <= right->_keynum; i++) {
right->_sub[i] = right->_sub[i + 1];
}
}
}
else if (left && left->_keynum >= (M + 1) / 2) {//有左兄弟且可借
for (int i = sub->_keynum; i > 0; i--) {//sub空出位置
sub->_key[i] = sub->_key[i - 1];
}
sub->_keynum++;
sub->_key[0] = node->_key[index - 1];//父结点借给sub
if (left->_sub[left->_keynum]) {//借的关键值的子树也要移动
for (int i = sub->_keynum; i > 0; i--) {//sub空出位置
sub->_sub[i] = sub->_sub[i - 1];
}
sub->_sub[0] = left->_sub[left->_keynum];
}
node->_key[index - 1] = left->_key[--left->_keynum];//left借给父
}
else if (left) {//与左兄弟合并
merge(node, index - 1);
}
else {//与右兄弟合并
merge(node, index);
}
}
void merge(BTNode* node, int index) {//合并,保留index,删index+1
if (!node || index < 0)return;
BTNode* sub1 = node->_sub[index], * sub2 = node->_sub[index + 1];
sub1->_key[sub1->_keynum++] = node->_key[index];//差一个满足最少
for (int i = 0; i < sub2->_keynum; i++)//关键值合并//sub2->_keynum//(M + 1) / 2 - 1
sub1->_key[sub1->_keynum + i] = sub2->_key[i];
if (sub2->_sub[0]) {//子树合并
for (int i = 0; i <= sub2->_keynum; i++)
sub1->_sub[sub1->_keynum + i] = sub2->_sub[i];
}
sub1->_keynum += sub2->_keynum;
node->_keynum--;
free(sub2);
if (node->_keynum > 0) {
for (int i = index; i < node->_keynum; i++) {//父结点借出关键值,调整
node->_key[i] = node->_key[i + 1];
node->_sub[i + 1] = node->_sub[i + 2];
}
node->_sub[node->_keynum + 1] = nullptr;
}
if (node->_keynum == 0) {//根才会减到0?其他结点都会合并不会为0,直到合并到根结点
cout << "node->_keynum == 0" << endl;//合并导致上层结点关键值没了
free(_root);
_root = sub1;//改根结点
}
}
pair<bool, int> get_keyindex(BTNode* node, K key) {//单个结点中搜索关键值
int i = 0;
while (i < node->_keynum && key > node->_key[i])i++;
if (i < node->_keynum && key == node->_key[i]) return make_pair(true, i);//找到关键值
else return make_pair(false, i);//没找到
}
bool is_leaf(BTNode* node) {
if (node->_sub[0] == nullptr)return true;
else return false;
}
//将关键值和子树插入到双亲结点中
void _insert(BTNode* node, const K& key, BTNode* sub) {
int i = node->_keynum - 1;//最后一个关键值的下标
while (i >= 0 && node->_key[i] > key) {
node->_key[i + 1] = node->_key[i];
node->_sub[i + 2] = node->_sub[i + 1];//子树大于关键值
i--;
}
node->_key[i + 1] = key;
node->_sub[i + 2] = sub;
if (sub)sub->_parent = node;
node->_keynum++;
}
void destoryTree(BTNode* root) {//连同所有子树一同删除
if (root) {
//cout << "destoryTree=" << root << endl;
for (int i = 0; i <= root->_keynum; i++) {
destoryTree(root->_sub[i]);
root->_sub[i] = nullptr;
}
//root->_parent = nullptr;
//root->_keynum = 0;
delete root;
}
}
};
void test02() {
//sizeof(a) / sizeof(*a)
int a11[] = { 1,3,7,14,8,5,11,17,13,6,12,20,23,26,4,19 };
int a[] = { 36,1,43,45,15,35,6,0,46,31,3,9,16,34,21,44,24,10,30,17,5,40,32,4,29,27,12,2,18,19 };
BTree<int, 5> bt;
for (auto i : a) {
bt.insert(i);
//bt.levelorder();
//cout << "----------" << endl;
}
//bt.levelorder();
//cout << "----------" << endl;
for (auto i : a) {
cout << "delete " << i << endl;
bt.remove(i);
//bt.levelorder();
//cout << "----------" << endl;
}
bt.levelorder();
}
|