树形查找思维脑图思维导图

生杀予夺

2023-12-06

浏览量: 4

树形查找

数据分析

信息查找

数据的树形查找相关内容知识讲解

树图思维导图提供《树形查找思维脑图》在线思维导图免费制作，点击“编辑”按钮，可对《树形查找思维脑图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：88bd7670c86e45ff68bbf594fca5b214

思维导图大纲

二叉排序树（BST）

定义

左＜根＜右

进行中序遍历可以得到一个递增的有序序列

查找

从根开始，目标更小向左找，目标更大向右找

插入

找到应插入的位置（一定是叶结点），修改其父节点指针

构造

就是不断地查找应该插入的位置后进行插入

不要混淆给定序列构造二叉树，和判断查找序列问题

删除操作

叶子，直接删

只有左 or 右子树，用其左 or 右子树顶替之

被删结点既有左子树又有右子树

可用其后继顶替，再删除后继

后继：右子树中最左下结点

可用其前驱顶替，再删前驱

前驱：左子树中最右下结点

查找效率分析

取决于树高，最好O(logn)，最差O(n)

平均查找长度ASL

计算方法同折半查找判定树

二叉排序树与堆的区别

用途

二叉排序树用于查找，作小型目录；堆用于排序：组织优先级队列

逻辑结构

二叉排序树左＜根＜右，大根堆根＞左、右

物理结构

二叉排序树用二叉链表实现，堆用顺序存储实现

平衡二叉树AVL

定义

树上任意节点左右子树高度差不超过1

结点平衡因子 = 左子树高度 - 右子树高度

也是个二叉排序树

插入操作

和二叉排序树一样，插入后可能要调整不平衡

调整不平衡

首先找到最小不平衡子树，满足其是插入后向上找第一个不平衡的子树，记根为A，

LL：A左孩子的左子树插入导致A不平衡

A的左孩子右旋

RR：A右孩子的右子树插入导致A不平衡

A的右孩子左旋

LR：A左孩子的右子树插入导致A不平衡

A的左孩子的右孩子先左旋后右旋

RL：A右孩子的左子树插入导致A不平衡

A的右孩子的左孩子先右旋后左旋

删除操作

删除结点，同二叉排序树

一路向上找到最小不平衡子树，找不到结束

找最小不平衡子树下“个头”最高的儿子、孙子

以爷爷为起始，根据孙子的位置判断

儿子右旋

儿子左旋

孙子先左旋后右旋

孙子先右旋后左旋

如果不平衡向上传导，继续第二步

查找效率分析

二叉树最大深度O(logn)

平均查找长度、查找、插入、删除时间复杂度均为O(logn)

高度为h的平衡二叉树最少有多少个结点，满足此条件时，所有非叶节点平衡因子=1

高度为h的AVL树中，离根最近的叶结点所在层数

递推公式L(h) = L(h-2)+1,L(1)=1,L(2)=2

即所在层数L(h) = [h/2] + 1，取整函数

补充

任意一棵二叉排序树BST，删除一个结点，再重新插入回去

若是叶结点，必和之前相同

若是非叶节点，必和之前不同

任意一棵平衡二叉树AVL，删除一个结点，再重新插入回去

若是叶结点，可能和之前不同

若是非叶节点，可能和之前不同

例如，删除再重新插入，结果和之前相同的情况

AVL旋转举例

插入时的旋转

LL、RR型

RR型

LR、RL型

LR、RL型不需要两次旋转，可以一步到位：找到让孙子当爷爷，其左右子树分配给它爹和它爷，然后它左右孩子连上它爹和它爷

删除时的旋转

找“个头”最高的儿子、孙子

如何找“个头”最高的儿子和孙子

孙子在LL、RR，儿子右 or 左旋

孙子在LL、RR，儿子右 or 左旋（续上）

孙子在RL，孙子先右旋后左旋

最终结果

孙子在LR，孙子先左旋后右旋

最终结果

不平衡向上传导

思维导图：城市设计领域的实地调查方法

Kar.Logic

2.14

树图思维导图提供《思维导图：城市设计领域的实地调查方法》在线思维导图免费制作，点击“编辑”按钮，可对《思维导图：城市设计领域的实地调查方法》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：6d8530c4b68e0584800437e9b7e5cfd8

分子名称思维脑图思维导图

U763671284

3.4

树图思维导图提供《分子名称思维脑图》在线思维导图免费制作，点击“编辑”按钮，可对《分子名称思维脑图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：c71cf199b7a5b69a378a465ae11afbcc

思维导图模板

IT互联网

产品结构

正文

相似思维导图模版

《Python程序设计》课程综合育人框架模式思维导图

思维导图模版推荐

首页

我的文件

我的团队

个人中心