二叉搜索树
二叉搜索树的基本概念
二叉搜索树( Binary Search Tree )也称二叉排序树,是一种各节点值之间存在一定次序关系的二叉树。
二叉搜索树的特点
一般情况下,二叉搜索树中所有节点值是不重复的。
对于二叉搜索树中的每个节点:
(1)如果其左子树不为空,那么其左边的节点值都比当前节点值小;
(2)如果其右子树不为空,那么其右边的节点值都比当前的节点值要大。
二叉搜索树的中序遍历结果,就是所有节点值升序排序的结果。
二叉搜索树的查找
二叉搜索树查找的基本步骤
根据二叉搜索树的特点,其实二叉搜索树中的查找和二分查找非常相似。从树的根节点出发,当前节点值 val 如果等于目标值 target,那么就直接返回;如果 val 小于目标值 target,那么就要往左边去寻找;如果 val 大于目标值 target,那么就要往右边去寻找。假如最后节点为 NULL,都没有找到等于目标值的节点,那么说明此时的二叉搜索树中不存在这个等与目标值 target 的节点。
我们将使用递归函数来实现这一过程,假设函数名为 SearchBST,则大致步骤为:
(1)节点为空,没有等于目标值的节点 if(!root) return NULL ;
(2)当前节点值小于目标值 if(root->val < target) return SearchBST(root->left) ;
(3)当前节点值大于目标值 if(root->val > target) return SearchBST(root->right) ;
(4)找到该节点 return root 。
二叉搜索树查找图解
(1)
(2)
(3)
(4)
二叉搜索树查找代码
//递归 查找二叉排序树指定元素target
BinaryTree Search_BST(BinaryTree root, Elemtype target){
if(!root) //最后没有找到root为NULL
return NULL;
if(target > root->val) //root值小于target 往其右子树查找
return Search_BST(root->rightchild, target);
if(target < root->val) //root值大于target 往其左子树查找
return Search_BST(root->leftchild, target);
return root; //找到直接返回该节点
}
二叉搜索树的插入
二叉搜索树插入的基本步骤
二叉搜索树插入的元素,首先一定是当前二叉搜索树中不存在的元素,如果要插入的元素 val 已经存在于二叉搜索树中,那么就没有插入的必要了。
二叉搜索树插入新元素,同时还需要使整棵树保持二叉搜索树的性质。所以在插入过程中,我们依旧需要用类似于二分查找的形式来实现插入的操作。从树的根节点出发,如果当前节点为空,说明可以插入到这个位置;如果插入元素 val 与当前节点值相等,说明已经存在,直接 return;如果插入元素 val 小于当前节点值,那么递归往左寻找合适的插入位置;如果插入元素 val 大于当前节点值,那么递归往右寻找合适的插入位置。
我们还是用递归函数来实现这个插入的过程,也是创建二叉搜索树的过程。
假定函数名为 InsertBST ,则大致步骤为:
(1)当前节点位置为空,可以插入,创建一个新节点 root = new Node(val) ;
(2)当前节点值与插入元素值相等,直接 return;
(3)插入元素 val 小于当前节点值,则进行 InsertBST(root->left, val) ;
(4)插入元素 val 大于当前节点值,则进行 InsertBST(root->right, val) 。
二叉搜索树插入图解
(1)
(2)
二叉搜索树插入代码
//二叉排序树元素的插入
void Insert_BST(BinaryTree &root, Elemtype val){
if(!root){ //若为当前root为空
BinaryTree node = (BinaryTree)malloc(sizeof(BiNode));
node->val = val;
node->leftchild = node->rightchild = NULL;
root = node;
return;
}
if(root->val == val)
return; //当前值已经存在 则不插入
/* 递归写法 */
if(root->val > val)
Insert_BST(root->leftchild, val);
else
Insert_BST(root->rightchild, val);
}
二叉搜索树的删除
第一类删除的情况
删除节点为叶子结点
基本步骤
由于删除节点为叶子结点,直接置 NULL 即可,删除完之后不会对整棵树满足二叉搜索树性质产生任何影响。
图解
第二类删除的情况
这一类删除的节点的特点为其只有一个子树,另一个子树为空。这种情况往往也是比较方便处理的。
(1)删除节点只有右子树
当删除节点只有右子树时,为了维持二叉搜索树的特点,只需要将删除节点的右子树继承给其父节点就可以,并且做到了将该节点删除。
基本步骤
假定 root 为当前要删除的节点,直接 root = root->right。
图解
(2)删除节点只有左子树
当删除节点只有左子树时,为了维持二叉搜索树的特点,和上一种情况也类似,将左子树继承给其父节点。
基本步骤
假定 root 为当前要删除的节点,直接 root = root->left。
图解
第三类删除的情况
这一类删除的节点同时含有左子树和右子树,此时的处理是比较麻烦的,但是整理好思路就不难。
本质上,我们要找到当前删除的节点的右子树中的节点值最小的节点,也就是右边第一个大于当前删除节点的节点。我们用 s 来指向这个节点,后期我们将其作为代替当前删除的节点。
但是,s 情况的不同也会导致一些处理上的区别。
(1)右子树根节点为右边的最小节点
s 指向的是右子树中的最小的节点,如果右子树的左子树为空,也就是说右子树的根节点即右子树中最小的节点。那么此时 s 就指向这个右子树根节点,然后只需要将删除节点 root 的左子树继承给 s 的 left ,最后将 s 代替删除节点 root 就可以了。这样就可以保持二叉搜索树的性质。
基本步骤
(1)此时 s 就指向 root->right ;
(2)将 root->left 继承给 s->left ;
(3)s 代替删除节点, root = s。
图解
(2)最后一种情况
基本步骤
s 指向的是右子树中的最小的节点,假如右子树的左子树不为空,那么我们首先要先一直向左搜索,直到右子树的最左边,即找到最左边的节点。而且这个最左边的节点一定是没有左子树的,但是可能存在右子树。为了能够顺利的让 s 代替删除节点 root,根据 s 一定是其父节点的左子树的特点,我们需要先将 s 的右子树继承给其父节点 parent,然后此时的 s 就形成一个单独的节点。最后将删除节点 root->left 赋给 s 的左子树,将 root->right 赋给 s 的右子树,将 root = s 完成代替操作。
为了将 s 的右子树继承给其父节点 parent,在右子树中一直往左寻找最左边的节点时,我们需要定义 parent 来记录其父节点。
(1)在删除节点 root 的右子树中一直往左搜索,找到最左边的节点 s ;
(2)将 s 的右子树继承给 parent, parent->left = s->right ;
(3)将 root 的左右子树继承给 s, s->left = root->left, s->right = root->right ;
(4)最后 root = s 。
图解
二叉搜索树删除代码
//二叉排序树元素的删除
void Delete_BST(BinaryTree &root, Elemtype val){
BinaryTree t = root, parent = NULL, s = NULL;
if(!t){ //要删除节点不存在
puts("要删除的节点不存在");
return;
}
//当前的root为要删除的节点
if(t->val == val){
if(!t->leftchild && !t->rightchild){ //要删除的节点是一个叶子结点 直接置NULL
root = NULL;
}
else if(!t->leftchild && t->rightchild){ //要删除的节点只有右子树,将其右子树的根节点代替删除节点
root = t->rightchild;
}
else if(t->leftchild && !t->rightchild){ //要删除的节点只有左子树,将其左子树的根节点代替删除节点
root = t->leftchild;
}
/* **个人认为最难的地方 采用迭代法** */
else{ //要删除的节点既有左子树,又有右子树
s = t->rightchild; //记录删除节点的右子树根节点
//找到右子树中最小的节点
if(!s->leftchild){ //如果此时的s没有左儿子,直接把删除节点的左子树变为此时s(删除节点右儿子)的左子树
s->leftchild = t->leftchild;
}else{
while(s->leftchild){ //找到删除节点的右子树中最左边的节点s 即第一个大于删除节点值的节点(后期将其代替删除节点的位置)
parent = s; //记录代替位置节点的父节点
s = s->leftchild;
}
parent->leftchild = s->rightchild;//若代替位置节点有右子树,把其右子树继承给父节点(重构删除节点的右子树)
s->leftchild = t->leftchild; //删除节点的左子树变为代替节点的左子树
s->rightchild = t->rightchild; //删除节点的右子树变为代替节点的右子树
}
root = s; //最后将当前s代替要删除的节点
}
free(t);
}
else if(val > t->val){
Delete_BST(t->rightchild, val); //向其右子树寻找要删除的节点
}
else if(val < t->val){
Delete_BST(t->leftchild, val); //向其左子树寻找要删除的节点
}
}
二叉搜索树的平均查找度
基本概念
ASL(Average Search Length),即平均查找长度,在查找运算中,由于所费时间在关键字的比较上,所以把平均需要和待查找值比较的关键字次数称为平均查找长度。
查找成功情况下的AVL
计算公式
其中 i 表示当前层级,numi 表示第 i 层的节点个数,nodesum 表示整颗二叉搜索树的节点个数。
图解
计算二叉树节点个数代码
//计算二叉树节点的个数
int Nodenum_of_BST(BinaryTree root){
if(!root)
return 0;
return Nodenum_of_BST(root->leftchild) + Nodenum_of_BST(root->rightchild) + 1;
}
查找失败情况下的AVL
计算公式
其中 i 表示当前层级,supplei 表示第 i 层的要补全的节点个数,supplesum 表示整颗二叉搜索树的要补全的总节点个数。
图解
利用层次遍历求补全节点
double sum1 = 0, sum2 = 0;
//全局变量 sum1 = ∑(各层节点数 × 对应层级), sum2 = ∑(各层补全节点 × (对应层级-1))
int n0 = 0, n1 = 0;
//全局变量 分别用于计算每一层叶子节点 和 度数为1的节点
int supplesum = 0;
//全局变量 计算补全的节点总数
//层次遍历 并利用队列计算二叉树每一层的节点个数
void Show_Level_Order(BinaryTree root){
if(!root)
return;
BinaryTree t = NULL;
int level = 1;
std::queue<BinaryTree> q;
q.push(root);
while(!q.empty()){
n0 = n1 = 0;
int n = q.size();
for(int i = 0; i < n; i++){
t = q.front();
q.pop();
printf("%d ", t->val);
if(t->leftchild) q.push(t->leftchild);
if(t->rightchild) q.push(t->rightchild);
if(!t->leftchild && !t->rightchild)
n0 ++ ; //度数为0的节点
if(!t->leftchild && t->rightchild || t->leftchild && !t->rightchild)
n1 ++ ; //度数为1的节点
}
printf("\n");
sum1 += n * level; //每一层节点个数*层级
sum2 += (n0 * 2 + n1) * level; //每一层下方需补全节点*层级
supplesum += (n0 * 2 + n1); //补全的节点个数
level++;
}
}