精华内容
下载资源
问答
  • 数据结构:静态查找动态查找
    千次阅读 多人点赞
    2019-03-15 15:32:10

    概念

    1、静态查找

    首先无论是静态查找还是动态查找,都要有查找的对象,也就是包含很多同类型数据的“表”,这个“表”可以理解为一个由同类型数据元素组成的一个“集合”,该集合可以用各种容器来存储,例如数组、链表、树等,我们统称这些存储数据的数据结构为——查找表。可见,查找表有时是我们传统意义的表,有时候是很复杂的一种结构。

    静态查找就是我们平时概念中的查找,是“真正的查找”。之所以说静态查找是真正的查找,因为在静态查找过程中仅仅是执行“查找”的操作,即:(1)查看某特定的关键字是否在表中(判断性查找);(2)检索某特定关键字数据元素的各种属性(检索性查找)。这两种操作都只是获取已经存在的一个表中的数据信息,不对表的数据元素和结构进行任何改变,这就是所谓的静态查找。

    2、动态查找

    看到上面静态查找的概念,动态查找就很好理解了,个人总觉得动态查找不像是“查找”,更像是一个对表进行“创建、扩充、修改、删除”的过程。动态查找的过程中对表的操作会多两个动作:(1)首先也有一个“判断性查找”的过程,如果某特定的关键字在表中不存在,则按照一定的规则将其插入表中;(2)如果已经存在,则可以对其执行删除操作。动态查找的过程虽然只是多了“插入”和“删除”的操作,但是在对具体的表执行这两种操作时,往往并不是那么简单。

    哪种查找对应各自查找表,如有序表可以为静态查找表,也可以为动态查找表。依查找方式决定。

    一、静态查找表

    1.顺序查找

    假设每个记录的查找概率相等,顺序查找的平均查找长度:ASL=\sum_{i=1}^{n}P_{i}C^{i} = \frac{1}{n}\sum_{i=1}^{n}(n-i+1)=\frac{n+1}{2}

    假设查找成功与不成功的可能性相同,对每个记录查找概率也相等,则P_{i} = 1/(2n),此时平均查找长度为ASL=\frac{3}{4}(n+1)

    2.有序表查找

    折半查找:这个查找过程类似二叉树,具有n个节点的判定树深度为\left \lfloor log_{2}n \right \rfloor + 1,平均查找长度为ASL=\frac{1}{n}\sum _{j =1}^{h}j*2_{j-1} = \frac{n+1}{n}log_{2}(n+1)-1

    3.索引顺序表的查找(分块查找)

    对子表建立一个索引表,包括两项内容:关键字项(值为该子表内最大关键字)和指针项(指向该子表的第一个记录在表中的位置)。索引表按关键字有序,表或者有序,或者分块有序。

    由于索引项按关键字有序,则确定块的查找可以用顺序表查找,也可以用折半查找,块中记录是任意排列的,在块中只能是顺序查找。

    分块查找由这两种查找算法简单合成。分块查找的平均查找长度为

                                 ASL_{bs} = L_{b} + L_{w}

    其中:L_{b}为查找索引表确定所在块的平均查找长度,L_{w}为在块中查找元素的平均查找长度。

    一般情况下,为进行分块查找,可以将长度为n的表均匀的分成b块,每块含有s个记录;假定表中每个记录的查找概率相等。用顺序查找确定所在块,分块查找的平均查找长度为

                                ASL = \frac{b+1}{2}+\frac{s+1}{2}

    分块查找是折半查找和顺序查找的一种改进方法,折半查找虽然具有很好的性能,但其前提条件时线性表顺序存储而且按照关键码排序,这一前提条件在结点树很大且表元素动态变化时是难以满足的。而顺序查找可以解决表元素动态变化的要求,但查找效率很低。如果既要保持对线性表的查找具有较快的速度,又要能够满足表元素动态变化的要求,则可采用分块查找的方法。

    分块查找的速度虽然不如折半查找算法,但比顺序查找算法快得多,同时又不需要对全部节点进行排序。当节点很多且块数很大时,对索引表可以采用折半查找,这样能够进一步提高查找的速度。

    分块查找由于只要求索引表是有序的,对块内节点没有排序要求,因此特别适合于节点动态变化的情况。当增加或减少节以及节点的关键码改变时,只需将该节点调整到所在的块即可。在空间复杂性上,分块查找的主要代价是增加了一个辅助数组。

    平均查找长度:

    以一个牛客网上的题目为例:设顺序线性表的长度为30,分成5块,每块6个元素,如果采用分块查找并且索引表和块内均采用顺序查找,则其平均查找长度为(     )。

    分块查找会分两部分进行,第一步先进行索引表查找判断其在那个字表中,第二步然后进行在字表中的查找
    索引表有5个元素 所以平均查找长度为:(1+5)/2=3
    字表中有6个元素,所以平均查找长度为:(1+6)/2=3.5
    所以总的平均查找长度为3+3.5=6.5

    二、动态查找表

    2.1二叉排序树与AVL树

    2.1.1二叉排序树

    含有n个节点的二叉排序树的平均查找长度和树的形态有关,最好和log_{2}n成正比,当先后插入的关键字有序,构成的二叉排序树蜕变为单支树,树的深度为n,最坏情况,平均查找长度为\frac{n+1}{2}

    2.1.2平衡二叉树(AVL树)

    它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左右子树的深度之差绝对值不超过1。结点平衡因子定义为左子树深度减右子树深度(-1,0,1)。平均查找时间复杂度O(logn)

    2.2B-树和B+树

    一棵m阶B-树,或为空树,或满足下列特性的m叉树:(是一种平衡的多路查找树)

    1. 树中每个节点至多有m棵子树;
    2. 若根节点不是叶子结点,则至少有两棵子树;
    3. 除根之外的所有非终端结点至少有\left \lceil m/2 \right \rceil
    4. 所有非终端结点中包含下列信息数据(n,A_{0},K_{1},...,K_{n},A_{n}),其中K_{i}(i=1...n)为关键字,A_{i}(i = 0...n)为指向子树根结点的指针,且指针A_{i-1}所指子树中所有结点的关键字均小于K_{i}
    5. 所有的叶子结点都出现在同一层次上,且不带信息。

    m阶B+树和m阶B-树的差异在于:

    1. 有n棵子树的结点中含有n个关键字。
    2. 所有叶子结点中包含了全部关键字信息,及指向这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
    3. 所有非终端结点可以看成是索引部分,结点中仅含有其子树(根结点)中最大(或最小) 关键字。

    参考文献:

    数据结构(C语言版),严蔚敏 

    https://blog.csdn.net/pamchen/article/details/8476134

    更多相关内容
  • 利用二叉排序树完成动态查找表的建立、指定关键字的查找、插入与删除指定关键字结点。 算法输入:指定一组数据。 算法输出:显示二叉排序树的中序遍历结果、查找成功与否的信息、插入和删除后的中序遍历结果(排序...
  • 数据结构_动态查找

    2014-07-31 13:10:38
    数据结构 抽象数据类型 动态查找表 C语言
  • 数据结构动态查找

    2013-01-03 19:45:52
    数据结构ADT动态查找动态查找表的特点和抽象数据类型ADT DynamicSearchTable 存储结构定义、 算法设计
  •  ②动态查找 二叉排序树的基本操作 任务: 编写算法实现对依次输入的关键字序列建立二叉排序树 并能实现二叉排序树的查找 插入和删除运算  ③散列法查找  在Hash查找方法中 散列函数构造方法多种多样 同时对于...
  • 主要介绍了C语言实现树的动态查找实例代码的相关资料,需要的朋友可以参考下
  • 查找算法集(顺序查找、二分查找、插值查找、动态查找).docx
  • 【数据结构——树表的查找(动态查找表)】

    千次阅读 多人点赞 2020-11-28 20:43:36
    【数据结构——树表的查找(动态查找表)】 目录【数据结构——树表的查找(动态查找表)】动态查找表(基于树的查找法)(一)二叉排序树1、定义2、查找算法3、插入算法4、创建算法5、删除算法(二)平衡二叉树1、...

    【数据结构——树表的查找(动态查找表)】

    动态查找表(基于树的查找法)

    当表插入、删除操作频繁时,为维护表的有序性,需要移动表中很多记录。
    改用动态查找表——几种特殊的树
    表结构在查找过程中动态生成。
    对于给定值:
    若表中存在,则返回成功;
    否则,插入关键字等于key的记录

    (一)二叉排序树

    1、定义

    二叉排序树又称二叉查找树
    定义:
    二叉排序树或者是一棵空树;或者是具有如下特性的二叉树:

    在这里插入图片描述实例——判断二叉排序树
    在这里插入图片描述
    二叉排序树的存储结构:二叉链表表示

    //二叉排序树的存储结构
    typedef struct
    {
    	KeyType key;					//关键字项
    	InfoType otherinfo;				//其他数据项
    }ElemType;							//每个结点的数据域的类型
    
    typedef struct BSTNode
    { //结点结构
    	ElemType data;					//数据域
    	struct BSTNode* lchild, * rchild;	//左右孩子的指针
    }BSTNode,*BSTree;
    

    2、查找算法

    算法思想
    在这里插入图片描述
    算法描述

    typedef struct BSTNode
    { //结点结构
    	ElemType data;					//数据域
    	struct BSTNode* lchild, * rchild;	//左右孩子的指针
    }BSTNode,*BSTree;
    
    BSTree SearchBST(BSTree T, KeyType key)
    {
    	//在指针T所指的二叉排序树中递归地查找某关键字等于key的数据元素
    	//若查找成功,则返回指向该数据元素结点的指针,否则返回空指针
    	if (!T || key == T->data.key)
    		return T;					//查找结束
    	else if (key < T->data.key)
    		return SearchBST(T->lchild,key);//在左子树中继续查找
    	else
    		return SearchBST(T->rchild,key);//在右子树中继续查找
    } 
    

    二叉排序树的查找分析
    (1)在二叉排序树上查找其他关键字等于给定值的结点的过程,恰是走了一条从根结点到该结点的路径的过程。
    比较的关键字次数=次结点所在的层次数
    最多比较次数=树的深度
    (2)但 二叉排序树平均查找长度和树的形态有关

    在这里插入图片描述
    在这里插入图片描述

    3、插入算法

    在这里插入图片描述

    typedef struct BSTNode
    { //结点结构
    	ElemType data;					//数据域
    	struct BSTNode* lchild, * rchild;	//左右孩子的指针
    }BSTNode, * BSTree;
    
    //二叉排序树的插入
    void InsertBST(BSTree& T, ElemType e)
    {//当二叉排序树T中不存在关键字等于e.key的数据元素时,则插入该元素
    	if (!T)							//T为空树
    	{ //找到插入位置,递归结束
    		BSTree S;
    		S = new BSTNode;			//生成新结点*S
    		S->data = e;				//新结点数据域置为e
    		S->lchild = S->rchild = NULL;//新结点*S作为叶子结点
    		T = S;						//把新结点*S链接到已找到的插入位置
    	}
    	else if (e.key < T->data.key)
    		InsertBST(T->lchild, e);	//将*S插入左子树
    	else if (e.key > T->data.key)
    		InsertBST(T->rchild, e);	//将*S插入右子树
    }
    

    4、创建算法

    在这里插入图片描述

    typedef struct BSTNode
    { //结点结构
    	ElemType data;					//数据域
    	struct BSTNode* lchild, * rchild;	//左右孩子的指针
    }BSTNode, * BSTree;
    
    //创建
    void CreatBST(BSTree& T)
    { //依次读入一个关键字为key的结点,将此结点插入到二叉排序树T中
    	T = NULL;						//将二叉排序树T初始化为空树
    	cin >> e;
    	while (e.key != ENDFLAG)
    	{ //ENDFLAG为自定义常量,作为输入结束标志
    		InsertBST(T, e);			//将此结点插入到二叉排序树T中
    		cin >> e;
    	}
    }
    

    5、删除算法

    在这里插入图片描述
    (1)被删除结点*p为叶子结点
    在这里插入图片描述
    (2)被删除结点*p只有左子树或者只有右子树

    在这里插入图片描述
    实例
    在这里插入图片描述
    (3)被删除结点*p既有左子树又有右子树

    在这里插入图片描述
    实例
    在这里插入图片描述

    在这里插入图片描述

    算法描述:

    //在这里插入代码片
    

    (二)平衡二叉树

    1、平衡二叉树的定义

    平衡二叉树又称AVL树
    一棵AVL树或者是空树,或者是具有下列性质的二叉排序树:
    (1)它的左子树和右子树都是AVL树,且左子树和右子树的深度之差的绝对值不超过1
    (2)左子树和右子树也是AVL树

    在这里插入图片描述
    ···每个结点附加一个数字,给出该结点的平衡因子BF:该结点的左子树深度和右子树深度之差。
    ···AVL树任一结点平衡因子只能取-1,0,1

    在这里插入图片描述

    2、如何构造平衡二叉树

    如果在一棵AVL树中插入一个新结点,就有可能造成失衡,此时必须重新调整树的结构,使之恢复平衡

    调整方法:找到离插入点最近且平衡因子绝对值超过1的祖先结点,以该结点为根的子树称为最小不平衡子树,可将重新平衡的范围局限于这棵子树。

    平衡调整的四种类型
    在这里插入图片描述
    LL型调整:
    在这里插入图片描述
    在这里插入图片描述
    RR型调整:
    在这里插入图片描述在这里插入图片描述
    LR型调整:

    在这里插入图片描述在这里插入图片描述在这里插入图片描述
    RL型调整:
    在这里插入图片描述在这里插入图片描述在这里插入图片描述

    3、AVL的插入

    在这里插入图片描述实例:
    在这里插入图片描述在这里插入图片描述在这里插入图片描述

    (三)B-树

    1、B-树的概念

    在这里插入图片描述

    2、B-树的结点特点

    在这里插入图片描述
    在这里插入图片描述

    3、B-树的特点

    在这里插入图片描述
    在这里插入图片描述

    4、B-树的搜索算法

    在这里插入图片描述

    展开全文
  • 我将主要讲解介绍 查找的相关知识,如查找算法等,希望你们会喜欢。

    前言

    • 查找是 数据结构中的重要操作
    • 今天,我将主要讲解介绍 查找的相关知识,如查找算法等,希望你们会喜欢。

    目录

    示意图


    1. 简介

    • 本节将介绍关于 查找 的相关基础概念
    • 具体请看下图:

    示意图


    2. 查找 需求场景

    • 对于不同的查找需求场景,会采用不同的查找类型,最终采用的查找方式(查找算法)也有所不同

    • 具体如下

    示意图

    • 下面,将根据不同的查找需求类型,讲解对应的查找算法

    3. 静态查找

    • 定义:仅作 查找操作
    • 面向的数据结构:静态查找表
    • 算法:顺序查找、有序查找、线性索引查找
    • 具体介绍如下

    3.1 顺序查找

    • 具体介绍如下

    示意图

    3.2 有序查找

    1. 主要算法有:二分查找、插值 & 斐波那契
    2. 本文 主要介绍 = 二分查找(也称:折半查找)
    • 定义

    示意图

    • 具体实现
    public class BinarySearch {
    
        /**
         * 二分查找方法
         *  @param srcArray:有序数组
         * @param des:需要查找的元素
         */
        public static int binarySearch(int[] srcArray, int des){
    
            int low = 0; // 比较区间第1位
            int high = srcArray.length-1; // 比较区间最后1位
            int middle ; // 区间的中间位置
            
            
            while(low <= high) {
    
                // 1. 通过折半,求出区间的中间位置
                middle = low +  (high - low)>>1;
                 // 此处需特别注意以下:
               // a. mid = (low + high) / 2:当low、high都是比较大的数时,可能造成上溢除
               // b. 采用右移的位运算代替除2,提高效率
    
                // 2. 比较给定值和中间值
                    // 2.1 若给定值 = 中间记录,则查找成功,返回该位置
                if(des == srcArray[middle]) {
                    return middle;
    
                    // 2.2 若给定值 < 中间记录,则 在中间记录的左半区 继续查找
                    // 即 将比较区间的最后1位 设置为 原中间位置的前1位
                }else if(des <srcArray[middle]) {
                    high = middle - 1;
    
                    // 2.3 若给定值 > 中间记录,则 在中间记录的右半区 继续查找
                    // 即 将比较区间的首位 设置为原中间位置的后1位
                }else {
                    low = middle + 1;
                }
            }
            // 若比较区间的第1位 ≥ 最后1位,则表示查找失败,返回-1
            return -1;
        }
    
    
        /**
         * 执行 二分查找方法
         */
        public static void main(String[] args) {
    
            // 定义1个有序表数组
            int[] src = new int[]{1, 4, 5, 7, 8, 13,20,28};
            // 输出结果
            System.out.println("需要查找数据的数组下标 = " + binarySearch(src,8));
    
        }
        
    }
    
    • 测试结果
    需要查找数据的数组下标 = 4
    
    • 二分查找的变式

    对于二分查找存在一定的优 & 缺点,所以衍生出2种二分查找的变式方法:插值查找 & 斐波那契查找。具体如下:

    区别主要在于:比较元素(中间元素)的计算

    对比

    3.3 线性索引查找

    • 面向的数据结构:索引表

    关于 索引 的介绍如下

    示意图

    • 本文主要介绍的线性索引查找算法 = 稠密索引、分块索引、倒排索引。具体介绍如下:

    示意图


    4. 动态查找

    • 定义:作 查找、插入 & 删除操作
    • 面向的数据结构:动态查找表
    • 算法:二叉排序树、平衡二叉排序树(AVL树)&多路查找树
    • 具体介绍如下

    4.1 二叉排序树

    也称:二叉查找树、二叉搜索树

    • 特点
      示意图

    • 作用 & 应用场景

    示意图

    4.2 平衡二叉排序树(AVL树)

    属于 二叉搜索树的一种特殊类型

    • 特点

    示意图

    • 具体介绍

    示意图

    4.3 多路查找树

    • 具体介绍如下
      示意图

    • 多路查找树的类型介绍 & 对比
      http://blog.csdn.net/wtyvhreal/article/details/46442091

    示意图


    5. 散列查找

    • 定义:通过关键字获取记录
    • 面向的数据结构:散列表
    • 算法:散列技术
    • 具体介绍如下

    5.1 散列技术

    • 简介

    示意图

    5.2 散列函数的设计(构造方法)

    • 简介
      即,该如何构造出 散列函数
      示意图

    • 具体构造方法介绍 & 对比

    示意图

    5.3 散列冲突

    • 简介 & 解决方案

    示意图

    • 解决方案介绍

    示意图


    6. 总结

    • 本文主要讲解了数据结构中的查找相关知识
    • 下面我将继续对 数据结构,有兴趣可以继续关注Carson_Ho的安卓开发笔记

    请帮顶 / 评论点赞!因为你的鼓励是我写作的最大动力!

    展开全文
  • 查找(2)动态查找.pdf

    2021-09-30 16:09:26
    查找(2)动态查找.pdf
  • 动态查找表与索引

    千次阅读 2018-08-09 15:56:56
    动态查找表的特点是,表结构本身是在查找过程中动态生成的,即对于给定值key,若表中存在其关键字等于key的记录,则查找成功返回,否则插入关键字等于key的记录。  以上相当于是动态查找表的定义。在对数据库表...

        动态查找表的特点是,表结构本身是在查找过程中动态生成的,即对于给定值key,若表中存在其关键字等于key的记录,则查找成功返回,否则插入关键字等于key的记录。

        以上相当于是动态查找表的定义。在对数据库表进行插入/删除操作时,索引需要进行维护工作,也就是索引会动态的变化,而动态查找表能满足索引动态变化的要求。

        动态查找表包括二叉排序树、平衡二叉树(AVL树)、B树、B+树以及红黑树。下面对它们分别进行分析。

    二叉排序树

        定义:是一颗空树;或者是具有下列性质的二叉树:

                    1、若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值。

                    2、若它的右子树不为空,则右子树上所有节点的值均大于它的根节点的值。                

                    3、它的左、右子树也分别为二叉排序树。      

                      

                                          上图为一颗二叉排序树

        实现:通常使用二叉链表实现,也可使用三叉链表等方式。

        查找:在进行查找时,首先将给定值与根节点的关键字比较,若相等则查找成功,否则根据给定值和根节点的关键字之间的大小关系,分别在左子树或右子树上继续查找。

        插入:插入是在查找不成功后才进行的操作,所以新插入的结点一定是树的叶子结点,并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子,在判断之后直接插入到树中。

        容易看出,中序遍历二叉排序树能得到关键字的有序序列。此外,进行插入操作时,不必移动其它结点,仅需改动某个结点的指针,这就相当于在一个有序序列中插入一个记录而不需要移动其它记录。由此表明,二叉排序树拥有类似于折半查找的特性,而且使用链表作为存储结构,是动态查找表的一种合适表示。

        删除:删除分为三种情况:(删除p结点)

            1、p是叶子结点:删除叶子结点不破坏整棵树的结构,所以只需要修改p的父节点的指针即可。

            2、p只有左子树或只有右子树:直接令p的子树成为p的父节点的子树即可。

            3、p的左右子树均不为空:这时有两种做法:

                (1)令p的左子树代替p的位置,p的右子树则移动到p的左子树的最右端(即p的左子树的最右的结点)

                (2)找到p的左子树的最右端的结点(或p的右子树的最左端节点),代替p的位置,若该结点有左子树,则其左子树(右子树)代替该结 点原来的位置。具体请看下图:

                                 

                               左侧为删除p结点前,中间为第一种删除方式,右侧为第二种删除方式

        二叉排序树的查找、插入、删除方式都已经了解完了,接下来该考虑的就是性能,或者说适不适合作为数据库索引的数据结构。

        二叉排序树在进行插入操作时不需要移动其它结点,插入效率能得到保证。并且查找采用类似于折半查找的方式,查找效率同样也不低。但是不能忽略了生成二叉排序树时产生的问题。例如:有两颗二叉排序树,分别由(45,24,53,12,37,93)与(12,24,37,45,53,93)生成,生成的两棵树如下图所示:

        从上图可以明显看出,二者的平均查找长度是有差异的,右侧二叉排序树的平均查找长度明显大于左侧。所以其平均查找长度会根据树的形态不同而产生不同程度的差异,是不稳定的,“不平衡”的,是不适合作为数据库索引的数据结构的。下面接着介绍“平衡”的二叉排序树。

    平衡二叉树(AVL树)

        定义:是一颗空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。实际上就是在二叉排序树的基础上加上了,左右子树深度之差的绝对值不超过1的约束条件,来保证是平衡的二叉排序树。

        由于平衡二叉树只是在二叉排序树的基础上增加了约束条件,所以其实现方式与查找方式是与二叉排序树相同的。

         在介绍插入之前得讲一个实现二叉树平衡常用的操作:左旋及右旋,可以参考此处

         插入:平衡二叉树插入过程与二叉排序树的插入过程一致,只是多出了保持平衡这一项。插入一个节点后,树可能变为不平衡的(即左子树和右子树的深度之差的绝对值超过了1),这时就要使用左旋及右旋操作使其恢复平衡。首先要找到最小不平衡子树,然后通过该子树的根节点来判断,分下列几种情况(该根节点为P,其左孩子为Pl,其右孩子为Pr,其左孩子的左右孩子为Pll、Plr,其右孩子的左右孩子为Prl、Prr):

        (1)往该根节点的左孩子的左子树添加节点(LL):以P与Pl为轴,进行右旋操作。

                

        (2)往该根节点的左孩子的右子树添加节点(LR):以Pl与Plr为轴,进行左旋操作。然后重复一次操作(找到最小不平衡子树,判断属于哪种情况)。

                

        (3)往该根节点的右孩子的左子树添加节点(RL):与情况(2)相同,只是方向不同。以Pr与Prl为轴,进行右旋操作。然后重复一次操作(找到最小不平衡子树,判断属于哪种情况)。

        (4)往该根节点的右孩子的右子树添加节点(RR):与情况(1)相同,只是方向不同,以P与Pr为轴,进行左旋操作。

        删除:平衡二叉树与二叉排序树的删除相同,也是多出了保持平衡这一项,保持平衡可以参照平衡二叉树的插入。

        总的来说,平衡二叉树相较二叉排序树来说,其查找的稳定性远大于二叉排序树,代价是花出多余时间来维护二叉树的平衡。就目前来说,平衡二叉树已经适合作为数据库索引的数据结构的。但是随着数据量的增加,在进行插入与删除时会进行大量的平衡度计算,严重影响了性能。为了克服这个问题,下面介绍另一种平衡方式的“平衡”二叉树。

    红黑树(下面图中均没有NIL,请大家自行脑补吧,画图不好画...)

        定义:红黑树也是在二叉排序树的基础上增加了平衡性约束,不过相较平衡二叉树而言,红黑树的约束条件没有平衡二叉树那么严格。

                    1、节点是红色或黑色。

                    2、根节点是黑色。

                    3、每个叶节点(NIL节点,空节点)是黑色(约束:当一个黑色节点只有一个孩子时,该孩子为红色)。

                    4、每个红色节点的两个子节点都是黑色。

                    5、从任一节点到该节点每个叶子的所有路径都包含相同数目的黑色节点。如下图:

                                                   

        插入:首先将红黑树当做二叉排序树进行插入,然后将节点重新着色保持平衡。假设插入节点为P,将插入节点着色为红色,此时要分三种情况:

        1、P为根节点,直接将P着色为黑色。

        2、P的父节点为黑色,此时插入后的树不会违背定义中的约束条件,仍为一颗红黑树,不需要做任何处理。

        3、插入节点的父节点为红色,此时违背了定义4(每个红色节点的两个子节点都是黑色),需要对树进行操作,使之重新成为一颗红黑树。(其核心思想就是将红色节点移到根节点,然后将其变为黑色)

        3、(1)P的父节点为红色,父节点的兄弟节点(叔叔节点)是黑色,P为其祖父节点的左孩子的左孩子时:以其祖父节点为支点进行右旋操作,然后将其父节点变为黑色,其祖父节点变为红色。如下图,插入节点12:

                        

              (2)P的父节点为红色,P的叔叔节点是黑色,P为其祖父节点的左孩子的右孩子时:以其父节点为支点,进行左旋操作,然后继续判断。如下图,插入节点14,操作完后变为了情况(1),按情况(1)继续操作即可:

                        

            (3)P的父节点为红色,P的叔叔节点是黑色,P为其祖父节点的右孩子的右孩子时:此时的处理方式与情况(1)相同,只是由右旋变为左旋。

              (4)P的父节点为红色,P的叔叔节点是黑色,P为其祖父节点的右孩子的左孩子时:此时的处理方式与情况(2)相同,只是由左旋变为右旋。

              (5)P的父节点为红色,P的叔叔节点也为红色时:将P的父节点和叔叔节点都设为黑色,将P的祖父节点设为红色,然后以P的祖父节点为当前节点(插入节点)继续判断。如下图:

        删除:红黑树的删除过程也与二叉排序树的过程相同,删除后再进行维护平衡的工作,详情见上面二叉排序树的删除,情况3时选择第二种删除方法,找到删除节点D右子树的最左节点X的值复制到D,此时删除的情况就转换为了删除X,如下图:

                                        

        至此,只用考虑删除叶子结点的情况了。

        假设要删除节点为D,其左右子树为Dl、Dr,其父节点为P,其兄弟节点为Pr,其兄弟节点的左右子树为Prl、Prr。D为最左节点,所以D的左子树Dl为空。下图是要考虑到的7种情况:

                                            

        1、D为红色:此时Dr必为空(由定义3、5可推断出),删除一个红色叶子结点不影响红黑树的“平衡”,此时直接将D删除即可。

        2、D为黑色,Dr不为空:此时Dr必为红色,使用Dr代替D,并变为黑色即可。

        D为黑色,Dr为空:此时删除D,P的左子树的黑色节点会减少一个,违背了定义5。为了保持“平衡”就需要从P的右子树中拿一个节点到P的左子树,以保证P的左子树的黑色节点个数。下面就对P及P的右子树的节点的颜色情况进行讨论:(下面的情形操作完后,树不一定恢复了平衡,若未恢复平衡,则继续以D为标志,判断当前属于哪种情况)

        3、Pr为红色:那么P、Prl、Prr一定都为黑色,绕P进行左旋操作,并交换P与Pr的颜色。

                   

                    

        4、Prl为红色,P和Prr为任意颜色:此时Pr必为黑色,Prr为红色或空(NIL节点),绕Pr右旋,Pr与Prl交换颜色。

                        

        5、Prr为红色,P和Prl为任意颜色:此时Pr必为黑色,Prl为红色或空(NIL节点),绕P左旋,交换P与Pr的颜色,Prr变为黑色。

                         

        6、P为红色,Prr和Prl为黑色:此时Pr必为黑色,Prl与Prr为空(NIL节点),P与Pr交换颜色。

                        

        7、P、Prr和Prl均为黑色:此时Prl与Prr为空(NIL节点),将Pr变为红色。

                        

        红黑树的查询性能会稍逊于AVL树,因为红色节点的存在不影响红黑树的“平衡”,所以红黑树在查询相同内容的情况下,最多比AVL树多一次比较。但是,在插入与删除上红黑树完胜AVL树,AVL树在每次插入删除的时候会进行大量的平衡度计算,而红黑树为了维持红黑性质所做的红黑变换和旋转的开销,相较于AVL树为了维持平衡的开销要小得多。

        红黑树在插入后为了恢复平衡,最多进行两次旋转操作;在删除后为了恢复平衡,最多进行三次旋转操作。

        红黑树在查找、插入、删除的性能方面已经比较不错了。但是是不是适合作为数据库索引呢?下面来分析一下。

        当树存储在磁盘中时:红黑树在进行查找操作时,在树的每一层都会进行一次IO操作(取到对应的节点数据)。而红黑树是二叉树,当数据量非常大时,树的高度也会非常大。此时进行查找操作需要进行多次IO操作,而IO操作是十分耗时的,会造成查询效率低下。所以为了提升查询效率,需要减少IO操作,也就是需要降低树的高度,此时就引进来了B-Tree。

    B树

        定义假定树的度为D,则一颗B树需要满足以下条件:

                    1、D > 2。

                    2、根节点的儿子数为[2,D]。

                    3、除根节点以外的非叶子节点的儿子数为[D/2,D]。

                    4、每个节点存放的关键字个数:[D/2-1(向上取整),D-1]。(根节点最少为1)

                    5、非叶子节点:关键字个数 + 1 = 指针个数。

                    6、节点关键字:k[1]、k[2]、、、k[n],其中k[i] < k[i+1]。

                    7、非叶子节点指针:p[1]、p[2]、、、p[n],其中p[1]指向关键字小于k[1]的子树,p[2]指向关键字大于k[1]、小于k[2]的子树。

                    8、所有叶子节点位于同一层。

        下图就为一颗度为3的B树:

        查找:B树的查找与二叉排序树、AVL树及红黑树的查找略有不同。B树是多叉树,所以会从左往右遍历该节点中所有的关键字,来确定在该节点的哪一个子树继续进行查找。

        插入:B树插入操作的基本步骤:

                   1、根据要插入关键字的值,找到叶子节点并插入。

                   2、判断当前节点的关键字个数是否大于D-1,若不满足则插入结束,若满足则执行3。

                  3、以节点中间的关键字为中心分裂成左右两部分,将该关键字插入到父节点中,并将该关键字的左子树指向分裂后的左半部分,右子树指向分裂后的右半部分,然后继续执行2。

              下面介绍一个5阶B树的插入过程,依次插入(39,22,97,41,53,13,21,40,30,27,33 ,36,35,34 ,24, 29,26),因为是5阶B树,所以节点中最多有4个关键字。

               (1)插入39,22,97,41。

                                                

               (2) 插入53。

                                               

                          此时,节点中有5个关键字,大于4(D-1),所以以41为中心进行分裂。(若D为偶数,选择中心关键字时,从中间两个关键字任取一个即可)

                                                

               (3)插入13,21,40。

                                        

                         进行分裂。

                                          

               (4) 插入30,27,33 ;36,35,34 ;24,29。中间分裂了两次,与(2)(3)一致,就不详细画图了。

                                                

                          叶子节点的指针图方便我就没画了,大家自行脑补....

               (5)插入26。

                                               

                         此时第二个叶子节点需要进行分裂。

                                                  

                        此时根节点的关键字个数也大于4,需要进行分裂。

                                           

              在网上找资料的时候,有看到一种说法,先判断要插入的叶子节点的关键字个数是否已达到D-1,若达到了则分裂,然后再进行插入操作。从原理上来说,先分裂再插入和先插入再分裂没有什么区别。但是在实现的时候,先分裂再插入会在分裂后额外的查找一次需要插入的叶子节点,会影响B树插入的效率。

              在实现B树时,可以将每个节点的数组容量设置为D,而不是D-1,这样可以容纳D个指针和D个关键字,方便在插入时的操作。

          删除:根据B树的定义4,B树节点中的关键字个数必须大于等于D/2-1(向上取整)(设该数值为S),所以在删除时需要对这个约束条件进行判断。

            1、要删除的关键字处于非叶子节点上:此时可以参考红黑树的删除,找到该关键字右子树的最左关键字(或左子树的最右关键字)替换到该关键字的位置,由此转换为删除叶子节点中的关键字的情况。

             2、要删除的关键字处于叶子节点上:

                 (1)关键字删除后,该节点的关键字个数仍大于等于S:删除结束。

                 (2)关键字删除后,该节点的关键字个数小于S:

                         ①该节点的兄弟节点关键字个数大于S:找兄弟节点“借”一个关键字,具体操作方式为:其父节点的关键字下移到该节点,其兄弟节点的关键字上移到父节点。

                         ②该节点的兄弟节点关键字个数刚好等于S:与其兄弟节点合并,具体操作方式为:其父节点的关键字下移,并将该节点与其兄弟节点合并。

             下面来看具体的例子:以上面插入时的B树为例:

            上图为情况②,若“34”“35”所在节点的兄弟节点有3个或以上的关键字时,则符合情况①,下面来举例说明:

                     

         tips:对于要删除关键字的叶子节点,可能即有左兄弟又有右兄弟,此时选择其中之一进行操作即可。

         总的来说,B树是为了磁盘等存储设备而设计出来的,有效的减少了磁盘IO次数,提升查找效率。但是在范围查询的方面仍有些“吃力”,而在数据库中范围查询是非常频繁的,所以由此引进了B树的变种---B+树。

    B+树

         定义:B+树是B树的变种,其定义与B树基本相同,有以下不同及额外要求。

                  1、有N棵子树的节点中,关键字也为N个(B树为N-1个)(即关键字个数为 [ D/2(向上取整), D ])

                  2、所有叶子节点中包含了全部的关键字信息,及指向这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接

                  3、所有非叶子结点可以看成索引部分,节点中仅含有其子树中的最大(或最小)关键字

                  下图为一颗三阶的B+树:

                                          

         插入:B+树的插入与B树的插入基本相同,不同之处在于:节点在分裂时,B+树中间的关键字不上移,而是将其的复制上移到父节点。

                   例:在上图中插入25

                                         

                          分裂,并将25的复制上移(因为此树是属于节点中仅含有其子树中的最大关键字的情况)

                                        

                          分裂,并将25的复制上移

                                         

                          完毕

         删除:B+树的删除相比B树的删除简单很多,遇到需要合并节点的情况时,只需在合并后将其父节点对应的关键字索引删除即可。

     

           从Mysql(Inoodb)的角度来看,是使用B+树作为索引存储结构的,一般来说索引非常大,尤其是关系性数据库这种数据量大的索引,所以为了减少内存的占用,索引也会被存储在磁盘上。

           而B-树(B类树)的特定就是每层节点数目非常多,层数很少,目的就是为了就少磁盘IO次数,当查询数据的时候,最好的情况就是很快找到目标索引,然后读取数据,使用B+树就能很好的完成这个目的,但是B-树的每个节点都有data域,这就会增大了节点大小,说白了增加了磁盘IO次数,而B+树除了叶子节点其它节点并不存储数据,节点小,磁盘IO次数就少。另外,B+树所有的Data域在叶子节点,并且所有的叶子节点都用指针串起来。这样遍历叶子节点就能获得全部数据,能极大的提升区间访问的效率。

    展开全文
  • 二:动态查找表(Dynamic Search Table) 主要操作: 三:顺序查找(Sequential Search)【线性查找】 1.查找过程 2.时间复杂度 四:折半查找(Binary Search)【二分查找】【有序表查找】 1.查找过程 2.时间...
  • 动态查找表分析.pptx

    2020-02-15 07:44:58
    8.2 动态查找表 也即树表的查找 本节介绍一种以树的形式来组织查找表的方法 以实现动态高效率的查找 1二叉排序树 2平衡二叉树 3B树 4B+树 ;45;45;三二叉排序树的查找 查找方法 若根结点的关键字值等于查找的关键字...
  • 静态查找表与动态查找

    千次阅读 2020-09-16 10:36:22
    动态查找表:在查询之后,还需要将查询结果不在查找表中的数据元素插入到查找表中;或者,从查找表中删除其查询结果为在查找表中的数据元素; 简而言之,动态查找表的结构是可以随时修改或变化的,表结构本身在查找...
  • 已解锁-查找(2)动态查找.pdf
  • BST实现动态查找表.doc

    2021-10-08 21:35:44
    BST实现动态查找表.doc
  • 数据结构Data Structures张 凯计算机学院 软件工程系2011年3月12日第9章 查找查找的基本概念静态查找表动态查找表哈希表9.2 动态查找动态查找表 特点表结构本身是在查找过程中动态生成的即对于给定值 key 若表中...
  • c语言(树的动态查找)

    2010-02-16 10:48:10
    c语言树的动态查找c语言树的动态查找c语言树的动态查找c语言树的动态查找
  • 静态查找和动态查找

    千次阅读 2016-10-17 10:26:22
    参考:http://blog.csdn.net/pamchen/article/details/8476134首先无论是静态查找还是动态查找,都要有查找的对象,也就是包含很多同类型数据的“表”,这个“表”可以理解为一个由同类型数据元素组成的一个“集合”...
  • 实现动态查找表的基本操作,其中包括查找,插入以及删除
  • 1、分割数组 2、动态查找XML文件内容 3、如有疑问可进专主页留言
  • C语言动态查找表之二叉排序树

    千次阅读 2019-05-02 20:04:14
    1.静态查找表与动态查找表的比较 2.二叉排序树(Binary Sort Tree) 2.1二叉排序树的定义 2.2二叉排序树的查找算法 2.3二叉排序树的插入算法 2.4二叉排序树的构造算法 2.5二叉排序树的删除算法 3.源代码示例 ...
  • 查找--静态查找与动态查找

    千次阅读 2016-04-19 17:06:49
    静态查找: ...动态查找: 1.在查找表中插入一个元素; 2.从查找表中删去某个数据元素。 (需要借助于顺序表) //SeqList.h #ifndef _SEQLIST_H_ #define _SEQLIST_H_ typedef void SeqList; typedef void
  • £9.1.1 查找表 £9.2 静态查找表 £9.3 动态查找表 £9.4 哈希表
  • 1.动态查找表 特点:表结构在查找过程中动态生成。 要求:对于给定值 key, 若表中存在其关键字等于 key的记录,则查找成功返回,并且对查找成功的关键字可做删除操作;查找失败则可以做插入关键字等于 key的记录的....
  • 二叉排序树查找-动态查找

    千次阅读 2013-11-20 08:48:54
    二叉排序树查找-动态查找 更新:2013-11-20 ////////////////////////////////////////////////////////////////////// 从这篇开始学习动态查找,下一篇是二叉排序平衡树查找。 名称:二叉排序树查找 关键字:...
  • 数据结构 - 动态查找

    千次阅读 2015-05-03 09:48:19
    动态查找当查找表以顺序存储结构存储且需要保持有序时,若对查找表进行插入、删除或排序操作,就必须移动大量的记录,当记录数很多时,这种移动的代价很大。 若查找表无序,则插入删除可无需移动大量记录,但于查找...
  • 数据结构 报告 动态查找表用二叉平衡树结构的实验
  • 此资源为源代码文件。 采用VS2008(VC9.0)调试通过。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 677,389
精华内容 270,955
关键字:

动态查找