小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Computer & DL
  4. Data Structure
  5. 正文

数据结构【浙江大学】(第4节)整理

2018年4月24日 1119点热度 0人点赞 0条评论

第四节:二叉搜索树

4.1 二叉搜索树

二叉搜索树(BST),也称二叉排序树和二叉查找树。一棵这个树,可以为空。如果不为空,满足以下性质:

(1)非空左子树的所有键值小于其根结点的键值。

(2)非空右子树的所有键值大于其根结点的键值。

(3)左、右子树都是二叉搜索树。

1.二叉搜索树操作的函数:

Position Find(ElementType X, BinTree BST):从二叉搜索树BST中查找元素X,并返回其结点地址;

Position FindMin(ElementType X, BinTree BST):从二叉搜索树BST中查找最小元素X,并返回其结点地址;

Position FindMax(ElementType X, BinTree BST):从二叉搜索树BST中查找最大元素X,并返回其结点地址;

BinTree Insert(ElementType X, BinTree BST)

BinTree Delete(ElementType X, BinTree BST)

2.二叉搜索树的查找操作:Find

查找从根结点开始,如果树为空,返回NULL。

若树非空,则根结点关键字与X进行比较,并进行以下处理:

(1)若X小于根结点键值,则在左子树中继续搜索;

(2)若X大于根节点键值,则在右子树中搜索;

(3)若两者相等,搜索完成,返回指向此结点的指针。

代码如下:

Position Find(ElementType X, BinTree BST)
{
       if(!BST)
              return NULL;
       if(X>BST->Data)
              return Find(X,BST->Right);
       else if(X<BST->Data)
              return Find(X, Bst->Left);
       else
              return BST;
}

由于非递归函数的执行效率高,可将尾递归函数修改为迭代函数:

Position Find(ElementType X, BinTree BST)
{
       while(BST){
              if(X>BST->Data)
                     BST= BST->Right;
              else if(X<BST->Data)
                     BST= BST->Left;
       else
              return BST;
       }
       return NULL;
}

3.查找最大和最小元素

最大元素一定在树的最右分支的端结点上;最小元素在最左分支的端结点上。

/*查找最小元素的递归函数*/
Position FindMin(BinTree BST)
{
       if(!BST) return NULL;
       else if(!BST->Left)
              return BST;
       else
              return FindMin(BST->Left);
}
/*查找最大元素的迭代函数*/
Position FindMax(BinTree BST)
{
       if(BST)
              while(BST->Right)
                     BST = BST->Right;
       return BST;
}

4.二叉搜索树的插入

分析:关键是要找到元素应该插入的位置,可以采用与Find类型的方法。

BinTree Insert(ElementType X, BinTree BST)
{
       if(!BST){
              BST = malloc(sizeof(struct TreeNode));
              BST->Data =X;
              BST->Left = BST->Right =NULL;
       }
       else if(X<BST->Data)
              BST->Left = Insert(X, BST->Left);
       else if(X>BST->Data)
              BST->Right = Inser(X,BST->Right);
       return BST;
}

4.二叉搜索树的删除

我们需要考虑三种情况:

(1)要删除的是叶结点:直接删除,并再修改其父结点指针为NULL。

(2)要删除的结点只有一个孩子结点:要将其父结点的指针指向要删除结点的孩子结点。

(3)要删除的结点有左、右两棵子树:用另一结点代替被删除的结点:右子树的最小元素或者左子树的最大元素。如图2所示。

 1524539102126072.jpg

图1

代码如下所示:

BinTree Delete( ElementType X, BinTree BST )
{   Position Tmp;
    if( !BST ) printf("要删除的元素未找到");
    else if( X < BST->Data )
            BST->Left = Delete( X, BST->Left); /* 左子树递归删除 */
    else if( X > BST->Data )
            BST->Right = Delete( X, BST->Right); /* 右子树递归删除 */
    else /*找到要删除的结点 */
         if( BST->Left && BST->Right ) { /*被删除结点有左右两个子结点 */
             Tmp = FindMin( BST->Right );
                           /*在右子树中找最小的元素填充删除结点*/
             BST->Data = Tmp->Data;
             BST->Right = Delete( BST->Data, BST->Right);
                                    /*在删除结点的右子树中删除最小元素*/
         } else { /*被删除结点有一个或无子结点*/
             Tmp = BST;
             if( !BST->Left ) /* 有右孩子或无子结点*/
                  BST = BST->Right;
             else if( !BST->Right ) /*有左孩子或无子结点*/
                  BST = BST->Left;
             free( Tmp );
         }
    return BST;
}

4.2 平衡二叉树

1.平衡二叉树基本介绍

查找二叉搜索树(BST)的时间复杂度(最坏情况下)用查找过程中的比较次数来衡量,它取决于树的深度。

对于二叉树中任一结点T,其“平衡因子(Balance Factor,简称BF)”定义为BF(T)=hL-hR。(其中hL和hR分别为T的左、右子树的高度。)

“平衡二叉树(Balanced Binary Tree)”又称为“AVL树” 。 AVL树或者是一棵空树,或者是具有下列性质的非空二叉搜索树:任一结点左、右子树高度差的绝对值不超过1。”即|BF(T) |≤ 1。

平衡二叉树的高度能达到logn吗?

设nh高度为h的平衡二叉树的最少结点树。结点数最少时:

nh=n(h-1)+n(h-2)+1

具体见图2.

1524539126857172.jpg 

图2

1.平衡二叉树的调整

(1)右单旋

如图3所示,当只将Mar加上May的时候,其平衡因子为-1,但是当增加了一个Nov的时候,其平衡引子变成了-2,不符合平衡二叉树的要求,因此很显然我们会想到将其调整到图3右侧的结构,这样其三个结点的平衡因子都是0了。

1524539140516138.jpg 

图3

首个不平衡的“发现者”是Mar(未必是根结点),它是调整起点位置。而“麻烦结点”Nov 在发现者右子树的右边,因而叫RR插入,需要RR旋转(右单旋);一般情况(设A是首个发现者)的调整方式如下:

 1524539153680093.jpg

图4

(2)左单旋

 1524539165635453.jpg

图5

(3)左-右双旋

 1524539179564828.jpg

图6

(4)右-左双旋

1524539192123126.jpg 

图7

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 数据结构
最后更新:2018年4月24日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
已修:C++语言程序设计(基础篇)【清华大学】[2015-08-31] 航空节开幕式观后自己的感悟 C++面向对象程序设计课程笔记(第五周) 《新少林寺》观后感 Leetcode题目解析(191122):101&102&104 个人日记-091223
标签聚合
鸟哥的linux私房菜 算法 生活 高中 Python leetcode linux 学习 Java python学习
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号