visio网站开发流程图,东莞住房和建设局网站,wordpress媒体库 扩容,四川省住房与建设厅网站前文介绍了符号表的两种实现#xff0c;无序链表和有序数组#xff0c;无序链表在插入的时候具有较高的灵活性#xff0c;而有序数组在查找时具有较高的效率#xff0c;本文介绍的二叉查找树(Binary Search Tree#xff0c;BST)这一数据结构综合了以上两种数据结构的优点。… 前文介绍了符号表的两种实现无序链表和有序数组无序链表在插入的时候具有较高的灵活性而有序数组在查找时具有较高的效率本文介绍的二叉查找树(Binary Search TreeBST)这一数据结构综合了以上两种数据结构的优点。 二叉查找树具有很高的灵活性对其优化可以生成平衡二叉树红黑树等高效的查找和插入数据结构后文会一一介绍。 一 定义 二叉查找树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) 0){node node.Right;}else if (key.CompareTo(node.Key) 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的时间复杂度。原因在于插入和删除元素的时候树没有保持平衡。我们追求的是在最坏的情况下仍然有较好的时间复杂度这就是后面要讲的平衡查找树的内容了。下文首先讲解平衡查找树的最简单的一种2-3查找树。 希望本文对您了解二叉查找树有所帮助。 转载于:https://www.cnblogs.com/yangecnu/p/Introduce-Binary-Search-Tree.html
