做推送的网站推荐,佛山网站建设a068,网站建设公制度,淘客客怎么做自己的网站原文地址#xff1a;https://www.cnblogs.com/xuzhp/p/4638937.html 基本查找算法 一、查找的基本概念 查找#xff0c;也可称检索#xff0c;是在大量的数据元素中找到某个特定的数据元素而进行的工作。查找是一种操作。 二、顺序查找 针对无序序列的一种最简单的查找方式…原文地址https://www.cnblogs.com/xuzhp/p/4638937.html 基本查找算法 一、查找的基本概念 查找也可称检索是在大量的数据元素中找到某个特定的数据元素而进行的工作。查找是一种操作。 二、顺序查找 针对无序序列的一种最简单的查找方式。 时间复杂度为O(n)。 三、折半查找 针对已排序序列的一种查找方式。并且只适用于顺序存储结构的序列。要求序列中的元素基本不变在需要做删除和插入操作的时候会影响检索效率。 时间复杂度为O(logN)。 四、B树 B树又称二叉排序树Binary Sort Tree。 1、概念 它或者是一棵空树或者是具有下列性质的二叉树 (1)若左子树不空则左子树上所有结点的值均小于左子树所在树的根结点的值 (2)若右子树不空则右子树上所有结点的值均大于右子树所在树的根结点的值 (3)左、右子树也分别为二叉排序树 2、B树的查找 时间复杂度与树的深度的有关。 步骤若根结点的关键字值等于查找的关键字成功。 否则若小于根结点的关键字值递归查左子树。 若大于根结点的关键字值递归查右子树。 若子树为空查找不成功。 3、B树的插入 首先执行查找算法找出被插结点的父亲结点。 判断被插结点是其父亲结点的左儿子还是右儿子。将被插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。 注意新插入的结点总是叶子结点所以算法复杂度是O(h)。 4、B树的删除 如果删除的结点没有孩子则删除后算法结束 如果删除的结点只有一个孩子则删除后该孩子取代被删除结点的位置 如果删除的结点有两个孩子则选择该结点的后继结点该结点右孩子为根的树中的左子树中的值最小的点作为新的根同时在该后继结点开始执行前两种删除算法删除算法结束。 5、B树 一棵m阶的B树满足下列条件 1每个结点最多m个孩子。 2除根结点和叶子结点外其它每个结点至少有ém/2ù个孩子。 3根结点至少有两个孩子。 4所有的叶子结点在同一层且包含了所有关键字信息。 5有k个孩子的分支结点包含k个关键字。 例如: 五、散列hash表 关键字哈希函数、装填因子、冲突、同义词 关键字和和存储的地址建立一个对应的关系 Add Hash(key) 解决冲突方法 开放定址法 – 探测方式线性探测、二次探测。 分离链接法 – 利用链表的方式。 查找找效率不依赖于数据长度n查找效率非常快很多能达到O(1)查找的效率是a装填因子的函数而不是n的函数。因此不管n多大都可以找到一个合适的装填因子以便将平均查找长度限定在一个范围内。 一 定义 二叉查找树Binary Search Tree也称有序二叉树ordered binary tree,排序二叉树sorted binary tree是指一棵空树或者具有下列性质的二叉树 1. 若任意节点的左子树不空则左子树上所有结点的值均小于它的根结点的值 2. 若任意节点的右子树不空则右子树上所有结点的值均大于它的根结点的值 3. 任意节点的左、右子树也分别为二叉查找树。 4. 没有键值相等的节点no duplicate nodes。 如下图这个是普通的二叉树 在此基础上加上节点之间的大小关系就是二叉查找树 二 实现 在实现中我们需要定义一个内部类Node它包含两个分别指向左右节点的Node一个用于排序的Key以及该节点包含的值Value还有一个记录该节点及所有子节点个数的值Number。 public class BinarySearchTreeSymbolTableTKey, TValue : SymbolTablesTKey, TValue where TKey : IComparableTKey, IEquatableTValue
{private Node root;private class Node{public Node Left { get; set; }public Node Right { get; set; }public int Number { get; set; }public TKey Key { get; set; }public TValue Value { get; set; }public Node(TKey key, TValue value, int number){this.Key key;this.Value value;this.Number number;}
}… }
查找
查找操作和二分查找类似将key和节点的key比较如果小于那么就在Left Node节点查找,如果大于则在Right Node节点查找如果相等直接返回Value。 该方法实现有迭代和递归两种。
递归的方式实现如下
public override TValue Get(TKey key)
{TValue result default(TValue);Node node root;while (node ! null){if (key.CompareTo(node.Key) gt; 0){node node.Right;}else if (key.CompareTo(node.Key) lt; 0){node node.Left;}else{result node.Value;break;}
}
return result;}
迭代的如下
public TValue Get(TKey key)
{return GetValue(root, key);
}private TValue GetValue(Node root, TKey key) { if (root null) return default(TValue); int cmp key.CompareTo(root.Key); if (cmp 0) return GetValue(root.Right, key); else if (cmp 0) return GetValue(root.Left, key); else return root.Value; }
插入
插入和查找类似首先查找有没有和key相同的如果有更新如果没有找到那么创建新的节点。并更新每个节点的Number值代码实现如下
public override void Put(TKey key, TValue value)
{root Put(root, key, value);
}private Node Put(Node x, TKey key, TValue value) { //如果节点为空则创建新的节点并返回 //否则比较根据大小判断是左节点还是右节点然后继续查找左子树还是右子树 //同时更新节点的Number的值 if (x null) return new Node(key, value, 1); int cmp key.CompareTo(x.Key); if (cmp 0) x.Left Put(x.Left, key, value); else if (cmp 0) x.Right Put(x.Right, key, value); else x.Value value; x.Number Size(x.Left) Size(x.Right) 1; return x; }
private int Size(Node node) { if (node null) return 0; else return node.Number; } 插入操作图示如下 下面是插入动画效果 随机插入形成树的动画如下可以看到插入的时候树还是能够保持近似平衡状态 最大最小值
如下图可以看出二叉查找树的最大最小值是有规律的 从图中可以看出二叉查找树中最左和最右节点即为最小值和最大值所以我们只需迭代调用即可。
public override TKey GetMax()
{TKey maxItem default(TKey);Node s root;while (s.Right ! null){s s.Right;}maxItem s.Key;return maxItem;
}public override TKey GetMin() { TKey minItem default(TKey); Node s root; while (s.Left ! null) { s s.Left; } minItem s.Key; return minItem; }
以下是递归的版本
public TKey GetMaxRecursive()
{return GetMaxRecursive(root);
}private TKey GetMaxRecursive(Node root) { if (root.Right null) return root.Key; return GetMaxRecursive(root.Right); }
public TKey GetMinRecursive() { return GetMinRecursive(root); }
private TKey GetMinRecursive(Node root) { if (root.Left null) return root.Key; return GetMinRecursive(root.Left); }
Floor和Ceiling
查找Floor(key)的值就是所有key的最大值相反查找Ceiling的值就是所有key的最小值下图是Floor函数的查找示意图 以查找Floor为例我们首先将key和root元素比较如果key比root的key小则floor值一定在左子树上如果比root的key大则有可能在右子树上当且仅当其右子树有一个节点的key值要小于等于该key如果和root的key相等则floor值就是key。根据以上分析Floor方法的代码如下Ceiling方法的代码类似只需要把符号换一下即可
public TKey Floor(TKey key)
{Node x Floor(root, key);if (x ! null) return x.Key;else return default(TKey);
}private Node Floor(Node x, TKey key) { if (x null) return null; int cmp key.CompareTo(x.Key); if (cmp 0) return x; if (cmp 0) return Floor(x.Left, key); else { Node right Floor(x.Right, key); if (right null) return x; else return right; } }
删除
删除元素操作在二叉树的操作中应该是比较复杂的。首先来看下比较简单的删除最大最小值得方法。
以删除最小值为例我们首先找到最小值及最左边左子树为空的节点然后返回其右子树作为新的左子树。操作示意图如下 代码实现如下
public void DelMin()
{root DelMin(root);
}private Node DelMin(Node root) { if (root.Left null) return root.Right; root.Left DelMin(root.Left); root.Number Size(root.Left) Size(root.Right) 1; return root; }
删除最大值也是类似。
现在来分析一般情况假定我们要删除指定key的某一个节点。这个问题的难点在于删除最大最小值的操作删除的节点只有1个子节点或者没有子节点这样比较简单。但是如果删除任意节点就有可能出现删除的节点有0个1 个2个子节点的情况现在来逐一分析。
当删除的节点没有子节点时直接将该父节点指向该节点的link设置为null。 当删除的节点只有1个子节点时将该自己点替换为要删除的节点即可。 当删除的节点有2个子节点时问题就变复杂了。
假设我们删除的节点t具有两个子节点。因为t具有右子节点所以我们需要找到其右子节点中的最小节点替换t节点的位置。这里有四个步骤
1. 保存带删除的节点到临时变量t
2. 将t的右节点的最小节点min(t.right)保存到临时节点x
3. 将x的右节点设置为deleteMin(t.right)该右节点是删除后所有比x.key最大的节点。
4. 将x的做节点设置为t的左节点。
整个过程如下图 对应代码如下
public void Delete(TKey key)
{root Delete(root, key);}
private Node Delete(Node x, TKey key) { int cmp key.CompareTo(x.Key); if (cmp 0) x.Right Delete(x.Right, key); else if (cmp 0) x.Left Delete(x.Left, key); else { if (x.Left null) return x.Right; else if (x.Right null) return x.Left; else { Node t x; x GetMinNode(t.Right); x.Right DelMin(t.Right); x.Left t.Left; } } x.Number Size(x.Left) Size(x.Right) 1; return x; }
private Node GetMinNode(Node x) { if (x.Left null) return x; else return GetMinNode(x.Left); }
以上二叉查找树的删除节点的算法不是完美的因为随着删除的进行二叉树会变得不太平衡下面是动画演示。 三 分析
二叉查找树的运行时间和树的形状有关树的形状又和插入元素的顺序有关。在最好的情况下节点完全平衡从根节点到最底层叶子节点只有lgN个节点。在最差的情况下根节点到最底层叶子节点会有N各节点。在一般情况下树的形状和最好的情况接近。 在分析二叉查找树的时候我们通常会假设插入的元素顺序是随机的。对BST的分析类似与快速排序中的查找 BST中位于顶部的元素就是快速排序中的第一个划分的元素该元素左边的元素全部小于该元素右边的元素均大于该元素。
对于N个不同元素随机插入的二叉查找树来说其平均查找/插入的时间复杂度大约为2lnN这个和快速排序的分析一样具体的证明方法不再赘述参照快速排序。 四 总结
有了前篇文章 二分查找的分析对二叉查找树的理解应该比较容易。下面是二叉查找树的时间复杂度 它和二分查找一样插入和查找的时间复杂度均为lgN但是在最坏的情况下仍然会有N的时间复杂度。原因在于插入和删除元素的时候树没有保持平衡。我们追求的是在最坏的情况下仍然有较好的时间复杂度这就是后面要讲的平衡查找树的内容了。分类: 数据结构 标签: 数据结构, 查找算法, 二叉树 上一篇数据结构中的基本排序算法总结» 下一篇[软件架构]模块化编程思想及C实践
