首页 > 代码库 > 【算法导论】二叉搜索树的插入和删除
【算法导论】二叉搜索树的插入和删除
上一篇说了有关二叉树遍历的三种方式,文本将继续探讨如何实现二叉搜索树的插入和删除节点。
在继续之前,我们先来了解两个概念:前驱和后继。
一、后继和前驱
后继:如果所有的关键字互不相同,则一个节点x的后继是大于x.key的最小关键字的节点。
前驱:如果所有的关键字互不相同,则一个节点x的前驱是小于x.key的最大关键字的节点。
如果联系二叉搜索树的性质:
节点的key值总是大于它的左节点(如果存在)的key值并且小于它的右节点(如果存在)的key值。那么我们容易推知:如果一个节点有右子树,它后继即是它的右子树的最“左”端的节点,也即右子树的最左节点,否则它的后继位于它的某个父或祖父点,这个父或祖父节点有最后一次的左分支指向当前节点所在的子树;而一个节点如果有左子树,它的前驱即是它的左子树的最“右”端的节点,也即左子树的最大节点,否则它的前驱位于它的某个父或者祖父节点,这个父或者祖父节点有最后一次的右分支指向当前节点所在的子树。
了解了上面的内容,就不难给出前驱和后继的代码:
后继:
/* * 求x节点的后继,后继的key值为大于x.key的最小值 */ node* successor(node* x) { if (x->right != NULL) { //右子树中的最小值,没有左节点 return minimum(x->right); } node* y = x->parent; while (y != NULL && x == y->right) { x = y; y = y->parent; } return y; }
/* * 求x节点的前驱,前驱的key值为小于x.key的最大值 */ node* predessor(node* x) { if (x->left != NULL) { //左子树中的最大值,没有右节点 return maximum(x->left); } node* y = x->parent; while (y != NULL && x == y->left) { x = y; y = y->parent; } return y; }
二、节点的插入
插入的操作相对比较简单,我们只需要注意满足二叉树节点之间的关系,以及注意树是否为空的判断即可,代码如下:
递归的方式插入:
/* * 递归方式插入,r:当前递归遍历到的节点,pre:r的父节点,x要插入的节点 */ void tree_insert(node* pre, node* r, node*x) { if (r == NULL) { if (pre == NULL) { this->root = x; } else if (pre->key > x->key) { pre->left = x; } else { pre->right = x; } x->parent = pre; } else { if (r->key > x->key) { tree_insert(r, r->left, x); } else { tree_insert(r, r->right, x); } } } void tree_insert(node* x) { tree_insert(NULL, root, x); }
非递归方式插入:
/* * 插入一个关键值为key的节点 */ void tree_insert(int key) { node* n = new node(key); node* back = NULL; if (root == NULL) { root = n; } else { node* current = root; while (current != NULL) { back = current; if (current->key > key) { current = current->left; //左边放小的key值 } else { current = current->right; //右边放大的key值 } } if (back == NULL) { //表明树是空树 this->root = n; } else if (back->key > key) { back->left = n; } else { back->right = n; } n->parent = back; } }
三、节点的删除
二叉搜索树删除节点的操作比较复杂,主要考虑以下几种情况:
①要删除的节点没有孩子,那么直接删除即可
②要删除的节点只有一个孩子,那么将孩子放到节点位置,再删除节点即可
③要删除的节点有两个孩子,那么可以寻找节点的后继。
由于有两颗子树,所以它的后继一定在右子树中,且是右子树中最小的那个节点,所以没有左子节点。这里又要分量小细分情况:如果这个后继节点就是要删除节点的右子节点,那么使用右子节点替换原节点,再删除原节点即可;如果这个后继节点并不是要删除节点右子节点,而是在右子树的下层之中,那么要先用后继的右子树替换后继,然后再用后继节点替换要删除的节点。
上面提到的“替换”操作,实际上是一种节点的“移植”,我们将这个操作抽取出来,以方便使用:
/* * 移植操作: * 用以b为根的子树去替换以a为根的子树,这里只管替换,不管a的处理,也不管b的值是否合适, * 也不管b节点左右子树的处理 */ void transplant(node* a, node* b) { if (b == NULL) { return; } if (a->parent == NULL) { root = b; } if (a->parent->left == a) { //a是其父节点的左节点 a->parent->left = b; } else { a->parent->right = b; } if (b != NULL) { b->parent = a->parent; } }
节点的删除操作:
void tree_delete(node* n) { if (n == NULL) { return; } if (n->left == NULL) { //如果左子节点为空,那么最多只会有一个右节点,直接执行移植操作即可 transplant(n, n->right); } else if (n->right == NULL) { //如果左子节点不为空,而右子节点为空,则只有一个左子节点,也可以直接执行移植操作 transplant(n, n->left); } else { //左右两个子节点都不为空的情况 node* succ = minimum(n->right); //求右子树中的最小值 if (succ == n->right) { //如果suc是n的直系右节点 transplant(succ, succ->right); transplant(n, succ); succ->left = n->left;//因为是直系右节点,所以只需要处理左子树即可 succ->left->parent = succ; } else { //如果suc不是n的直系右节点 transplant(succ, succ->right); //将后继的右子树替换后继 transplant(n, succ); //将后继替换要删除的节点 succ->parent = n->parent; succ->right = n->right;//处理右子树 succ->left = n->left; succ->left->parent = succ;//处理左子树 succ->right->parent = succ; } } delete n; }
至此就完成了删除的操作。
【算法导论】二叉搜索树的插入和删除