AVL树(查找、插入、删除)——C语言

AVL树平衡二叉查找树(Self-balancingbinarysearchtree)又被称为AVL树(AVL树是根据它的发明者G.M.Adelson-Velskii和E.M.Landis命名的),是在二叉查找树的基础上一个优化版本AVL树的特点:1.本身首先是一棵二叉查找树2.带有平衡条件:每个结点的左右子树的高度之差的绝对值不超过1,也就是说,AVL树,本质上是带了平衡功能的二叉查找树如果读者...

AVL树(查找、插入、删除)——C语言

AVL树

平衡二叉查找树(Self-balancing binary search tree)又被称为AVL树(AVL树是根据它的发明者G. M.Adelson-Velskii和E.M.Landis命名的),是在二叉查找树的基础上一个优化版本

AVL树的特点:

1.本身首先是一棵二叉查找树
2.带有平衡条件:每个结点的左右子树的高度之差的绝对值不超过1,也就是说,AVL树,本质上是带了平衡功能的二叉查找树
如果读者关于二叉查找树还不了解可以看一下这篇随笔:二叉查找树(查找、插入、删除)

AVL树的作用

AVL树解决了二叉查找树可能出现的极端情况,对于一般的二叉搜索树(Binary Search Tree),其期望高度(即为一棵平衡树时)为log2n,其各操作的时间复杂度(O(log2n))同时也由此而决定,但是在某些极端情况下

(如在插入的序列是有序的时),二叉搜索树将退化成近似链或链,此时,其操作的时间复杂度将退化成线性的,即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况,但是在进行了多次的操作之后,例如在在删除时,

我们总是选择将待删除节点的后继代替它本身,这样就会造成总是右边的节点数目减少,以至于树向左偏沉。这同时也会造成树的平衡性受到破坏,使得它的操作时间复杂度增加

例如下面这种情况:

AVL树的特性让二叉搜索树的节点实现平衡(balance):节点相对均匀分布,而不是偏向某一侧

AVL树节点的定义:

1 typedef struct AVLTreeNode2 {3  int data;4  int height; //节点的高度5  struct BSTreeNode *left;//左子树6  struct BSTreeNode *right;//右子树7 8 }AVLTree;

与一般的二叉查找树的节点相比多了一个参数,节点的高度(网上有些博客是把平衡因子加在了节点的定义里面,笔者不太建议这样做)

预备知识

为了读者能更好了理解AVL树的操作,在继续往下看之前需要搞清楚几个概念

高度深度平衡因子

(1)深度——从上往下数

节点的层次(节点的深度):从根开始定义,根为第1层,根的子节点为第2层,以此类推;(这里说根节点为第1层,其他博客可能把根节点定义成第0层,两种记法都没有错,都可以用来描述树的性质,只需要标注(>0)或者(>=0)做一个区分和解释即可),本篇随笔记根节点为第1层(也可以说成根节点的深度为1)
树的深度:树中节点的最大层次

(树的深度 = 叶子节点的深度)

(2)高度——从下往上数

关于高度,有的文章中将"空二叉树的高度定义为-1",本篇随笔采用维基百科上的定义:空二叉树的高度为0,因为高度是从下往上数,所以叶子节点的高度为1

(树的高度 = 根节点的高度)

(3)平衡因子

某结点的左子树与右子树的高度或深度(高度深度都可以,本篇随笔使用深度来计算平衡因子)差即为该结点的平衡因子(BF,Balance Factor),平衡二叉树(AVL树)上所有结点的平衡因子只可能是 -1,0 或 1
从上面的节点的定义可以看出,节点中存储的是节点的高度,而不是平衡因子
下图中就标注了所有节点的平衡因子

(平衡因子计算时左子树 - 右子树 和 右子树 - 左子树 都可以,因为判断树是否平衡的条件是:每个结点的左右子树的高度之差的绝对值不超过1,只不过判断失衡以后还要判断是哪一种失衡,这就需要根据情况来选择是左-右还是右-左了)

-----------------------------------------------------------------------------------------------------

1、查找节点

AVL树中查找与在 二叉查找树 中查找完全一样,因为AVL树总是保持平衡的,树的结构不会由于查询而改变,这里就不再赘述了

实现代码:

 1 /* 查找特定值 */ 2 void SearchData(int targ, BSTree *nod) 3 { 4  if (nod != NULL) 5  { 6if (nod->data == targ) 7   { 8 printf("查找值存在,值为%d\n", nod->data); 9   }10else if (nod->data > targ)11   {12 SearchData(targ, nod->left); //递归查找左子树13   }14else if (nod->data < targ)15   {16 SearchData(targ, nod->right); //递归查找右子树17   }18  }19  else if (nod == NULL)20  {21printf("查找值不存在\n");22  }23 }
View Code

2、插入节点(递归实现)

先梳理一下步骤

先来实现搜索最低失衡节点,搜索最低失衡节点是从新插入的节点(也就是叶子节点)往上搜索(也可以说成从新增结点开始向根部回溯),搜索到的第一个平衡因子>1(|左子树高度-右子树高度|>1)的节点,作为最低失衡节点,因为是从新插入的节点往上搜索,二叉树的搜索是单向的(结构体成员中只有左右子树),单独使用一个函数来实现逆向搜索实现起来并不方便,这里就把搜索最低失衡节点的操作放到递归实现的插入操作中

这里没有像上一篇随笔:二叉查找树(查找、插入、删除)——C语言那样先手动输入的一个二叉平衡树(因为这里要考虑节点的高度,输入不太方便),干脆就从空二叉树开始插入

实现代码:

/* 获取节点高度,空树的高度为0 */int GetNodeHeight(AVLTree *nod){ if (nod != NULL) //若不为空子树 {  if (nod->left == NULL && nod->right == NULL) //若为叶子节点  {return 1;   }  else if (GetNodeHeight(nod->right) > GetNodeHeight(nod->left)) //若右子树高度较高  {return (nod->right)->height1;  }  else //若左子树高度较高 
源文地址:https://www.guoxiongfei.cn/cntech/24324.html