做网站客户尾款老不给怎么办,写代码做网站,微信公众号怎么做广告推广,葫岛百度seo7.3树表的查找
当表插入、删除操作频繁时#xff0c;为维护表的有序表#xff0c;需要移动表中很多记录。
改用动态查找表——几种特殊的树
表结构在查找过程中动态生成
对于给定值key
若表中存在#xff0c;则成功返回#xff1b;
否则#xff0…7.3树表的查找
当表插入、删除操作频繁时为维护表的有序表需要移动表中很多记录。
改用动态查找表——几种特殊的树
表结构在查找过程中动态生成
对于给定值key
若表中存在则成功返回
否则插入关键字等于key的记录
7.3.1二叉排序树
二叉排序树Binary Sort Tree又称为二叉搜索树、二叉查找树。
定义
二叉排序树或是空树或是满足如下性质的二叉树(1)若其左子树非空则左子树上所有结点的值均小于根结点的值(2)若其右子树非空则右子树上所有结点的值均大于等于根结点的值(3)其左右子树本身又各是一棵二叉树二叉排序树的性质
中序遍历非空的二叉排序树所得的数据元素序列时一个按关键字排序的递增有序序列。
二叉排序树的存储结构
typedef struct{KeyType key;//关键字项InfoType otherinfo;//其他数据域
}ElemType;typedef struct BSTNode{ElemType data;//数据域struct BSTNode *lchild,*rchild;//左右孩子指针
}BSTree T;
BSTree T//定义二叉排序树查找
若查找的关键字等于根结点成功否则 若小于根结点查其左子树若大于根结点查其右子树 在左右子树上的操作类似
1、二叉排序树的递归查找
【算法思想】
若二叉排序树为空则查找失败返回空指针。若二叉排序树非空将给定值key与根结点的关键字T-data.key进行比较 若key等于T-data.key则查找成功返回根结点地址若key小于T-data.key则进一步查找左子树若key大于T-data.key则进一步查找左子树。
BSTree SerachBT(BSTree T,KeyType key){if((!T)||keyT-data.key) return T;else if(keyT-data.key)return SearchBST(T-lchild,key);//在左子树中继续查找else return SearchBST(T-rchild,key);//在右子树中继续查找
}二叉排序树的查找分析
二叉排序树上查找某关键字等于给定值的结点过程其实就是走了一条从根到该结点的路径。
比较的关键字次数此结点所在层次数
最多的比较次数数的深度
问题如何提高形态不均衡的二叉排序树的查找效率
解决办法做“平衡化”处理即尽量让二叉树的形状均衡
2、二叉排序树的插入
若二叉排序树为空则插入结点作为根结点插入到空树中否则继续在其左、右子树上查找 树中已有不再插入树中没有 查找直至某个叶子结点的左子树或右子树为空为止则插入结点应为该叶子结点的左孩子或右孩子。
插入的元素一定在叶节点上
3、二叉排序树的删除
从二叉排序树中删除一个结点不能把以该结点为根的子树都删去只能删掉该结点并且还应保证删除后所得的二叉树仍然满足二叉排序树的性质不变。
由于中序遍历二叉排序树可以得到一个递增有序的序列。那么在二叉排序树删去一个结点相当于删去有序序列中的一个结点。
将因删除结点而断开的二叉链表重新链接起来防止重新链接后树的高度增加 4、二叉排序树的生成
从空树出发经过一系列的查找、插入操作之后可生成一棵二叉排序树。 一个无序序列可通过构造二叉排序树而变成一个有序序列。构造树的过程就是对无序序列进行排序的过程。
插入的结点均为叶子结点故无序移动其他结点。相当于在有序序列上插入记录而无需移动其他记录。
关键字的输入顺序不同建立的二叉排序树不同 7.3.2平衡二叉树
1.平衡二叉树的定义
平衡二叉树balance binary tree 又称AVL树 一棵平衡二叉树或者是空树或者是具有下列性质的二叉排序树 左子树与右子树的高度之差的绝对值小于等于1左子树和右子树也是平衡二叉排序树。 为了方便起见给每个结点附加一个数字给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子BF。 平衡因子 结点左子树的高度 - 结点右子树的高度 根据平衡二叉树的定义平衡二叉树上所有结点的平衡因子只能是-1、0或1。
2.失衡二叉排序树的分析与调整
当我们在一个平衡二叉排序树上插入一个结点时有可能导致失衡即出现平衡因子绝对值大于1的结点如2、-2。
如果在一棵AVL树中插入一个新结点后造成失衡则必须重新调整树的结果使之恢复平衡。
