第七章查找单元小结（1）基本概念二叉树 B树

旧城等待， 2022-01-06 14:47 212阅读 0赞

小细节：

1.若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找结果可给出一个“空”记录或“空”指针

2.动态查找表：表结构是在查找过程中产生的，即在创建表的过程中，对于给定值，若表中存在其关键字等于给定值的记录，则返回查找成功；

否则插入关键字等于给定值的记录

顺序查找：1.适用于线性表的顺序存储结构，又适用于链式存储结构；

2.时间复杂度O（n）,空间复杂度O（1）

3.优点：算法简单，对表结构没有要求，且对记录是否按关键字有序均可应用

4.缺点：平均查找长度较大，查找效率较低，n很大的时候不适合用

折半查找：1.线性表必须采用顺序存储结构，而且表中的元素按关键字有序排列；

2.时间复杂度O（log2 n）

3.在查找成功与否的情况下：和给定值进行比较的关键字个数最多也不超过向下取整的(log2 n )+1

4.优点：比较次数少，查找效率高；

5.缺点：对表的要求高，一定要是顺序存储，且关键字必须有序；费时：1.查找前排序；2.对有序表进行插入和删除的时候，平均比较和移动表中一半的元素

6.折半查找不适用于数据元素经常变动的线性表

分块查找：1.优点：.在表中插入和删除元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除。由于块内无序，故插入和删除比较容易，无序进行大量移动

2.缺点：要增加一个索引表的存储空间并对索引表进行排序运算

3.适用于动态变化的线性表

！！！！！这是一条分界线：为了保护表的有序性，线性表的查找更适用于静态查找表，若要对动态查找表进行高效率的查找，可采用几种特殊的二叉树作为查找表的组织形式，在此统称“树表”

树表的查找

1.二叉排序树：又称二叉查找树；！！！！中序遍历一课二叉排序树时可以得到一个节点值递增的有序序列

2.考点：①二叉树的查找，

②插入（在查找的基础上）:当树中不存在关键字等于key的结点时才进行插入。新插入的结点一定是新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子。

时间复杂度O（log2 n）

③创建

假设有n个结点，需要n此插入操作，而插入一个结点的算法时间复杂度是O（log2 n）,所以创建二叉排序树算法的时间复杂度为O（nlog2 n）

④删除

基本过程还是在查找，时间复杂度O（log2 n）

删除结点为\*p（指向结点的指针为p)，其双亲结点为\*f,PL和PR分别表示其左子树和右子树

1）\*p结点的左右结点均为空：f->lchild=NULL

2) \*p结点只有左子树PL或者右子树PR,此时直接令PL 或PR直接成为其双亲结点\*f的左子树即可

f->lchild=p->lchild；（或f->lchild=p->rchild）

3）\*p结点左右子树均不为空：

总结：①缺右子树用左孩子填补；②缺左子树用右孩子填补；③在左子树上找中序最后一个结点填补

转载于:https://www.cnblogs.com/snowlxy/p/10958972.html

发表评论取消回复

表情：

评论列表（有 0 条评论，212人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉查找树，平衡二叉树，B树，B+树区别

二叉查找树对于树的每个节点，其左子树上每个节点都比它小，其右子树上每个节点的值都比它大 -------------------- 平衡二叉树（AVL树）对于树的每个

川长思鸟来/ 2023年01月06日 01:16/ 0 赞/ 167 阅读

相关二叉查找树、平衡二叉树、红黑树、B-/B+树性能对比

前言：BST、AVL、RBT、B-tree都是动态结构，查找时间基本都在O(longN)数量级上。下面做出详细对比。 1. 二叉查找树 (Binary Search Tre

ゞ浴缸里的玫瑰/ 2022年08月09日 05:25/ 0 赞/ 266 阅读

相关二叉查找树、红黑树、B树、B+树、AVL树

不求甚解，但求掌握基础的了解。二叉查找树：原文：[http://blog.csdn.net/touch\_2011/article/details/68319

╰半夏微凉°/ 2022年08月06日 07:13/ 0 赞/ 206 阅读

相关二叉查找树、平衡二叉树、红黑树、B-/B+树性能对比

1. 二叉查找树 (Binary Search Tree) BST 的操作代价分析： (1) 查找代价：任何一个数据的查找过程都需要从根结点出发，沿某一个路径朝叶

布满荆棘的人生/ 2022年06月11日 03:59/ 0 赞/ 254 阅读

相关【二叉树】二叉树学习小结1

一、主干功能部分代码分享 1.存储定义 struct Tree{ char data;/数据域/ struct Tree left;/指针

冷不防/ 2022年06月01日 06:24/ 0 赞/ 201 阅读

相关二叉树、平衡二叉树、B- tree、B+ tree 基本概念

1 二叉树二叉树binary tree是指每个节点最多含有两个子树的树结构。特点： 1.所有节点最多拥有两个子节点，即度不大于2

雨点打透心脏的1/2处/ 2022年05月20日 06:59/ 0 赞/ 279 阅读

相关第七章查找单元小结（1）基本概念二叉树 B树

小细节： 1.若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找结果可给出一个“空”记录或“空”指针 2.动态查找表：表结构是在查找过程中产生的，即在创建表的过程

旧城等待，/ 2022年01月06日 14:47/ 0 赞/ 213 阅读

相关【数据结构】（二叉排序树）查找二叉排序树第k小的结点

> 算法思想：我是想到了查找第k个结点的办法也就是[二叉树查找先序序列第k个结点][k]将其改造为查找中序序列第k个结点即可 int i=0; int

爱被打了一巴掌/ 2021年10月29日 21:52/ 0 赞/ 294 阅读

相关二叉树、二叉搜索树、平衡二叉树、红黑树、B树、B+树概念的简单区分

文章目录 1、二叉树（Binary Tree） 2、二叉搜索树（Binary Search Tree） 3、平衡二叉树（AVL T

一时失言乱红尘/ 2021年10月19日 09:38/ 0 赞/ 406 阅读

相关 AVL树、B树、B+树（1-基本概念）

AVL树（平衡二叉树）定义：（1）左子树与右子树的高度差只能是-1，0，1。（2）树中的每个左子树和右子树都是AVL树 B树（多路平衡查找树）： B

喜欢ヅ旅行/ 2021年09月26日 14:42/ 0 赞/ 305 阅读