平衡二叉树(AVL树)-5.7

程序员日记      2019-08-11
定义平衡二叉树的定义如下:1.它是一颗二叉排序树2.其中每一个结点的左子树和右子树的高度差之多等于1平衡因子二叉树结点的左子树深度减去右子树深度的值称为平衡因子,所有结点的平衡因子只可能是 -1,0,1。只要树上有结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的我们可以尝试分辨一下图中的树是否平衡二叉树说明:1.图2不是排序二叉树2.图3结点58左子树深度为2,右子树深度为0,平衡因子大于一最小不平衡子树距离插入结点最近的,且平衡因子的绝对值大于1的节点为根的子树,我们成为最小不平...
标签:
72 人看过

二叉排序树-5.6

程序员日记      2019-08-10
定义二叉排序树(BinarySortTree),又称二叉查找树(BinarySearchTree),亦称二叉搜索树。二叉排序树是一颗空树,或者是具有以下性质的二叉树:1.若左子树不为空,则左子树上所有结点的值均小于根结点的值2.若右子树不为空,则右子树上所有结点的值均大于根结点的值3.左右子树同时也分别为二叉排序树二叉排序树的查找步骤如下:1.若根结点的关键字等于查找的关键字,成功。2.否则。小于根结点的值,递归查询左子树。3.若大于根结点,递归查询右子树4.若子树为空,查询不成功/***二叉排...
标签:
50 人看过

斐波那契查找-5.5

程序员日记      2019-08-10
斐波那契查找是利用黄金分割原理进行查找实现/***函数:产生斐波契纳数列*/functionfbi($k){if($k<2){return($k==0?0:1);}returnfbi($k-1)+fbi($k-2);}/***斐波那查找法*@paramarray$arr*/functionsearch($key,$arr=[]){$len=count($arr);$start=0;$end=$len-1;$k=0;//计算$count位于斐波那契数列的位置while($len>(Fb...
标签:
70 人看过

插值查找-5.4

程序员日记      2019-08-10
定义插值查找是二分查找法的一个变种,用于提高二分查找法的效率,其根据要查找的关键字key与查找表中最大记录和最小记录比较后的查找方法公式插值=最小记录+(最大记录-最小记录)*(关键字-$arr[最小记录])/(关键字-$arr[最大记录])实现/***插值查找法*@param$key查找关键字*@paramarray$arr要查找的数组*/functionsearch($key,$arr=[]){$len=count($arr);//获取数组长度$start=0;//最低值从数组下标0开始$e...
标签:
43 人看过

二分查找-5.3

程序员日记      2019-08-10
定义二分查找,又称为折半查找,它的前提必须是关键码有序,通常是从小到大有序,线性表必须是顺序存储。二分查找的基本思想是:取中间记录作为比较对象,相等,则查找成功,小于中间记录的关键字,左半区继续查找,大于中间记录的关键字,右半区继续查找。不断重复,知道查找成功或者在所有查找区域已经没有记录了,查找失败为止。循环实现/***二分查找法-循环实现*@param$key查找关键字*@paramarray$arr要查找的数组*/functionsearch($key,$arr=[]){$len=coun...
标签:
36 人看过

顺序查找-5.2

程序员日记      2019-08-10
定义顺序查找又叫线性查找,是最基本的查找技术,他的查找过程是,从表中第一个(或最后一个)元素开始,逐个进行记录的关键字和给定值比较,若某个记录的关键字和给定值相等,则查找成功,找到所查找的记录。如果直到最后一个(第一个)记录,没有找到元素,则查找不成功。基本实现/***顺序查找-普通*@param$key关键字*@param$arr要查找的数组*/functionsearch($key,$arr=[]){$len=count($arr);//获取数组长度for($i=0;$i<$len;$...
标签:
47 人看过

查找概论-5.1

程序员日记      2019-08-09
查找表查找表是由同一类型的数据元素(或记录)构成的集合。关键字关键字是数据元素中的某个数据项的值主关键字若关键字可以唯一标识一个记录,此关键字称为主关键字次关键字可以识别多个记录的关键字,称为次关键字查找查找就是根据给定的某个值,在查找表中确定一个关键字等于给定值的数据元素或记录。静态查找表只能查找操作的表。动态查找表在查找过程中同时插入查找表中不存在的数据元素,或者从表中删除已经存在的某个数据元素...
标签:
51 人看过