- 浏览: 48565 次
- 性别:
- 来自: 北京
文章分类
最新评论
转载http://hxraid.iteye.com/blog/609312
当所有的静态查找结构添加和删除一个数据的时候,整个结构都需要重建。这对于常常需要在查找过程中动态改变数据而言,是灾难性的。因此人们就必须去寻找高效的动态查找结构,我们在这讨论一个非常常用的动态查找树——二叉查找树 。
二叉查找树的特点
下面的图就是两棵二叉查找树,我们可以总结一下他的特点:
(1) 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值
(2) 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值
(3) 它的左、右子树也分别为二叉查找树
我们中序遍历这两棵树发现一个有序的数据序列: 【1 2 3 4 5 6 7 8 】
二叉查找树的操作
插入操作:
现在我们要查找一个数9,如果不存在则,添加进a图。我们看看二叉查找树动态添加的过程:
1). 数9和根节点4比较(9>4),则9放在节点4的右子树中。
2). 接着,9和节点5比较(9>5),则9放在节点5的右子树中。
3). 依次类推:直到9和节点8比较(9>8),则9放在节点8的右子树中,成为节点8的右孩子。
这个过程我们能够发现,动态添加任何一个数据,都会加在原树结构的叶子节点上,而不会重新建树。 由此可见,动态查找结构确实在这方面有巨大的优势。
删除操作:
如果二叉查找树中需要删除的结点左、右子树都存在,则删除的时候需要改变一些子树结构,但所需要付出的代价很小。
具体的插入,删除算法请参加《数据结构算法与应用——搜索树》P5-8。[该章节已经上传到《查找结构专题(6):动态查找树比较 》中]。
二叉查找树的效率分析
那么我们再来看看二叉查找树的效率问题
很显然,在a,b两图的二叉查找树结构中查找一个数据,并不需要遍历全部的节点元素,查找效率确实提高了。但是有一个很严重的问题:我们在a图中查找8需要比较5次数据,而在B图中只需要比较3次。更为严重的是:如果按有序序列[1 2 3 4 5 6 7 8]建立一颗二叉查找树,整棵树就退化成了一个线性结构(如c输入图:单支树),此时查找8需要比较8次数据,和顺序查找没有什么不同。
总结一下:最坏情况下,构成的二叉排序树蜕变为单支树,树的深度为n,其查找时间复杂度与顺序查找一样O(N)。最好的情况是二叉排序树的形态和折半查找的判定树相同,其平均查找长度和log2(N)成正比(O(log2(n)))。
这说明:同样一组数据集合,不同的添加顺序会导致查找树的结构完全不一样,直接影响了查找效率。
那么如何解决这个问题呢? 我们会在下面的专题中:《平衡二叉树》 中来解决。
下面是java实现的二叉查找树(说句老实话,没有指针的java实现数据结构真是复杂):
- package net.hr.algorithm.search;
- import java.util.ArrayList;
- /**
- * 二叉树节点结构
- * @author heartraid
- */
- class BSTNode<E extends Comparable<E>>{
- /**结点关键字*/
- E key=null;
- /**直接父亲结点*/
- BSTNode<E> parent=null;
- /**结点左子树的根节点*/
- BSTNode<E> lchild=null;
- /**结点右子树的根节点*/
- BSTNode<E> rchild=null;
- BSTNode(E k){
- this.key=k;
- }
- }
- /**
- * 二叉查找树 Binary Search Tree(BST)
- * @author heartraid
- *
- */
- public class BST<E extends Comparable<E>> {
- /**树根*/
- private BSTNode<E> root=null;
- public BST(){
- }
- /**
- * BST 查询关键字
- * @param key 关键字
- * @return 查询成功/true, 查询失败/false
- */
- public boolean search(E key){
- System.out.print("搜索关键字["+key+"]:");
- if(key==null||root==null){
- System.out.println("搜索失败");
- return false;
- }
- else{
- System.out.print("搜索路径[");
- if(searchBST(root,key)==null){
- return false;
- }
- else return true;
- }
- }
- /**
- * BST插入关键字
- * @param key 关键字
- * @return 插入成功/true, 插入失败/false
- */
- public boolean insert(E key){
- System.out.print("插入关键字["+key+"]:");
- if(key==null) return false;
- if(root==null){
- System.out.println("插入到树根。");
- root=new BSTNode<E>(key);
- return true;
- }
- else{
- System.out.print("搜索路径[");
- return insertBST(root,key);
- }
- }
- public boolean delete(E key){
- System.out.print("删除关键字["+key+"]:");
- if(key==null||root==null){
- System.out.println("删除失败");
- return false;
- }
- else{
- System.out.print("搜索路径[");
- //定位到树中待删除的结点
- BSTNode<E> nodeDel=searchBST(root,key);
- if(nodeDel==null){
- return false;
- }
- else{
- //nodeDel的右子树为空,则只需要重接它的左子树
- if(nodeDel.rchild==null){
- BSTNode<E> parent=nodeDel.parent;
- if(parent.lchild.key.compareTo(nodeDel.key)==0)
- parent.lchild=nodeDel.lchild;
- else
- parent.rchild=nodeDel.lchild;
- }
- //左子树为空,则重接它的右子树
- else if(nodeDel.lchild==null){
- BSTNode<E> parent=nodeDel.parent;
- if(parent.lchild.key.compareTo(nodeDel.key)==0)
- parent.lchild=nodeDel.rchild;
- else
- parent.rchild=nodeDel.rchild;
- }
- //左右子树均不空
- else{
- BSTNode<E> q=nodeDel;
- //先找nodeDel的左结点s
- BSTNode<E> s=nodeDel.lchild;
- //然后再向s的右尽头定位(这个结点将替代nodeDel),其中q一直定位在s的直接父亲结点
- while(s.rchild!=null){
- q=s;
- s=s.rchild;
- }
- //换掉nodeDel的关键字为s的关键字
- nodeDel.key=s.key;
- //重新设置s的左子树
- if(q!=nodeDel)
- q.rchild=s.lchild;
- else
- q.lchild=s.lchild;
- }
- return true;
- }
- }
- }
- /**
- * 递归查找关键子
- * @param node 树结点
- * @param key 关键字
- * @return 查找成功,返回该结点,否则返回null。
- */
- private BSTNode<E> searchBST(BSTNode<E> node, E key){
- if(node==null){
- System.out.println("]. 搜索失败");
- return null;
- }
- System.out.print(node.key+" —>");
- //搜索到关键字
- if(node.key.compareTo(key)==0){
- System.out.println("]. 搜索成功");
- return node;
- }
- //在左子树搜索
- else if(node.key.compareTo(key)>0){
- return searchBST(node.lchild,key);
- }
- //在右子树搜索
- else{
- return searchBST(node.rchild,key);
- }
- }
- /**
- * 递归插入关键字
- * @param node 树结点
- * @param key 树关键字
- * @return true/插入成功,false/插入失败
- */
- private boolean insertBST(BSTNode<E> node, E key){
- System.out.print(node.key+" —>");
- //在原树中找到相同的关键字,无需插入。
- if(node.key.compareTo(key)==0)
- {
- System.out.println("]. 搜索有相同关键字,插入失败");
- return false;
- }
- else{
- //搜索node的左子树
- if(node.key.compareTo(key)>0){
- //如果当前node的左子树为空,则将新结点key node插入到左孩子处
- if(node.lchild==null) {
- System.out.println("]. 插入到"+node.key+"的左孩子");
- BSTNode<E> newNode=new BSTNode<E>(key);
- node.lchild=newNode;
- newNode.parent=node;
- return true;
- }
- //如果当前node的左子树存在,则继续递归左子树
- else return insertBST(node.lchild, key);
- }
- //搜索node的右子树
- else{
- if(node.rchild==null){
- System.out.println("]. 插入到"+node.key+"的右孩子");
- BSTNode<E> newNode=new BSTNode<E>(key);
- node.rchild=newNode;
- newNode.parent=node;
- return true;
- }
- else return insertBST(node.rchild,key);
- }
- }
- }
- /**
- * 得到BST根节点
- * @return BST根节点f
- */
- public BSTNode<E> getRoot(){
- return this.root;
- }
- /**
- * 非递归中序遍历BST
- */
- public void InOrderTraverse(){
- if(root==null)
- return;
- BSTNode<E> node=root;
- ArrayList<BSTNode<E>> stack=new ArrayList<BSTNode<E>>();
- stack.add(node);
- while(!stack.isEmpty()){
- while(node.lchild!=null){
- node=node.lchild;
- stack.add(node);
- }
- if(!stack.isEmpty()){
- BSTNode<E> topNode=stack.get(stack.size()-1);
- System.out.print(topNode.key+" ");
- stack.remove(stack.size()-1);
- if(topNode.rchild!=null){
- node=topNode.rchild;
- stack.add(node);
- }
- }
- }
- }
- /**
- * 测试
- */
- public static void main(String[] args) {
- BST<Integer> tree=new BST<Integer>();
- tree.insert(new Integer(100));
- tree.insert(new Integer(52));
- tree.insert(new Integer(166));
- tree.insert(new Integer(74));
- tree.insert(new Integer(11));
- tree.insert(new Integer(13));
- tree.insert(new Integer(66));
- tree.insert(new Integer(121));
- tree.search(new Integer(11));
- tree.InOrderTraverse();
- tree.delete(new Integer(11));
- tree.InOrderTraverse();
- }
- }
发表评论
-
红黑树【RBT】
2010-10-03 16:20 900转载http://hxraid.iteye.com/b ... -
平衡二叉查找树【AVL】
2010-10-03 16:15 1285转载http://hxraid.iteye.com/b ... -
静态查找结构综述
2010-10-03 16:12 770转载http://hxraid.iteye.com/b ... -
根据上排的数填写下排的数
2010-09-13 18:58 1212根据上排给出十个数,在其下排填出对应的十个数, 要求下排每个数 ... -
一个正方形5等分
2010-09-12 16:33 1035每次都二分绝对不能分出奇数个块。以下两张图就是解法,第一张都是 ... -
一个数组的所有的排列
2010-09-04 18:15 835题目:给一个数组,打印出所有的排列 import java. ... -
求1+2+…+n
2010-09-04 17:37 776求1+2+…+n,要求不能使用乘除法、for、while、if ...
相关推荐
代码支持《数据结构与算法分析》中的BST数据结构C++代码
也就一百五十行左右代码 欢迎初学数据结构的同学下载自己跑跑看
二叉树的应用,数据结构的上机试验题目!实现二叉树的各项功能。
问题描述 利用二叉查找树(BST)实现一个动态查找表。 基本要求 (1) 使用二叉树(BST)来实现。 (2) 二叉树使用链式结构(二叉链表)实现。 (3) 实现BST的构建,查找两个功能。
代码实现了二叉树基本操作:实现二叉树的基本操作(包括前序、中序、后序遍历);从键盘读数,利用前面实现的基本操作,生成一棵二叉查找树;通过遍历二叉树,输出该二叉树的叶节点数;通过遍历二叉树,求二叉树的...
湖南大学数据机构实验4-二叉树的应用(BST).zip
二叉搜索树是一种二叉树,但是它有附加的一些约束条件,这些约束条件必须对每个结点都成立:结点node的左子树所有结点的值都小于node的值。} 一个类似的解法是
js代码-二叉树-BST树
二叉树的基本操作实现 在计算机科学中,树是一种很常见的数据结构,它是一种非线性的数据结构。我们可以按照等级模式将数据存储起来。在基本的数据结构中,如有序数组,无序数组,链表等,都有些不足,如:无序数组...
C++写的二叉树类,能生成二叉平衡排序树,并进行前序,中序遍历
二叉树的应用:二叉排序树BST和平衡二叉树AVL的构造实验报告
bat二叉树,一个数据结构课程实验,对于初学者来说,可以看看。。
此代码为原创代码 主要描述排序二叉树即BST的创建,以及二叉树的中序遍历,BST的广度遍历下的层序遍历。
其中以树和二叉树最为常用,直观看来,树是以分支关系定义的层次结构。树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机领域中也得到广泛应用,如在编译程序中,可用...
二叉树的实现,还有测试,学生自打,请多关照
对于Java代码的手动编译: 用于编译。 javac FileName.java 用于运行已编译的代码。 java FileName 确保您在同一目录中。... 树木二叉树BST 哈希图优先队列本节将重点介绍动态编程,这是编程的高级
1、树value的范围在【0,100】,利用这个feature可以构建suffix_map2、BST的特性,可以直接计算后缀和,不需要判断List list =
③平衡的二叉排序树指满足BST性质的平衡二叉树。 ④AVL树中任一结点的左、右子树的高度之差的绝对值不超过1。在最坏情况下,n个结点的AVL树的高度约为1.44lgn。而完全平衡的二叉树高度约为lgn,AVL树是最接近最优...
①初始化二叉树。 ②调用插入函数建立二叉排序树。 ③调用查找函数在二叉树中查找指定的结点。 ④调用删除函数删除指定的结点为,并动态地显删除结果。 */ #include #include #include //#include ...