- 浏览: 898072 次
- 性别:
- 来自: 武汉
文章分类
最新评论
-
小宇宙_WZY:
膜拜一下大神,解决了我一个大问题,非常感谢 orz
【解惑】深入jar包:从jar包中读取资源文件 -
JKL852qaz:
感谢,遇到相同的问题!
【解惑】深入jar包:从jar包中读取资源文件 -
lgh1992314:
为什么java中调用final方法是用invokevirtua ...
【解惑】Java动态绑定机制的内幕 -
鲁曼1991:
说的都有道理,protected只能被同一级包的类所调用
【解惑】真正理解了protected的作用范围 -
鲁曼1991:
...
【总结】String in Java
当所有的静态查找结构添加和删除一个数据的时候,整个结构都需要重建。这对于常常需要在查找过程中动态改变数据而言,是灾难性的。因此人们就必须去寻找高效的动态查找结构,我们在这讨论一个非常常用的动态查找树——二叉查找树 。
二叉查找树的特点
下面的图就是两棵二叉查找树,我们可以总结一下他的特点:
(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(); } }
评论
关于parent.rchild=nodeDel.lchild;这点是没有任何问题的!
当nodeDel右子树为空时,如果nodeDel是其parent的右子节点,那么 parent.rchild=nodeDel.lchild;不能保证二叉树结构吧,因为nodeDel.lchild.key不一定大于parent.key
//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; }
满足nodeDel.rchild==null的情况下,parent.lchild可能也为null,所以parent.lchild.key.compareTo(nodeDel.key)==0肯定会报java.lang.NullPointerException的
例如删除下图a的2这个叶子节点
发表评论
-
★经典问题—链表中的环问题
2010-06-29 14:43 4457转载:http://www.cppblog.com ... -
★经典问题—元素选择问题
2010-05-24 10:53 3361元素选择问题 : 给定线性序集中n个元素和一个整数k( ... -
【串和序列处理 8】最长平台问题
2010-04-28 16:41 37211、经典最长平台算法 已知一个已经从小到大 ... -
【排序结构7】 基数排序
2010-04-20 16:17 4588《桶排序 》中我们能够看到,数据值的范围越大,可能需要桶的个 ... -
【排序结构6】 桶排序
2010-04-19 20:28 23083从《基于比较的排序结构总结 》中我们知道:全依赖“比较”操作的 ... -
【排序结构5】 基于比较的内部排序总结
2010-04-18 16:15 6764★ 基于“比较”操作的内部排序性能大PK ... -
【排序结构4】 归并排序
2010-04-17 16:29 3324归并排序 O(N*logN) 是另一种效率很高的排序方法。&q ... -
【排序结构3】 选择排序
2010-04-14 21:10 3677(1) 简单选择排序 O(N^2) 一趟简单选择排序 ... -
【排序结构2】交换排序
2010-04-14 11:04 26501、起泡排序 O(N^2) ... -
【排序结构1】插入排序
2010-04-13 17:11 30361、基本概念介绍 (1) 如果待排序列中有两个 ... -
【串和序列处理 7】LIS 最长递增子序列
2010-03-25 16:37 5846LIS: 给定一个字符串序列S={x0,x1,x2,.. ... -
【串和序列处理 6】LCS 最长公共子序列
2010-03-23 17:38 8852LCS:又称 最长公共子序列。 其中子序列(subse ... -
【串和序列处理 5】KMP子串匹配算法
2010-03-22 19:59 9173模式匹配: 在字符串 ... -
★经典问题—欧几里得求最大公约数
2010-03-20 19:21 3392问题:快速求取正整数a,b的最大公约数? ... -
【串和序列处理 4】Suffix Trie 子串匹配结构
2010-03-20 15:15 9146Suffix Trie : 又称后 ... -
【串和序列处理 3】Trie Tree 串集合查找
2010-03-18 13:40 17722Trie 树, 又称字典树,单词查找树。它来源于retr ... -
【串和序列处理 2】字符串编辑距离算法
2010-03-15 08:45 11117我们来看一个实际应用。现代搜索技术的发展很多以提供优质、高效的 ... -
【串和序列处理 1】PAT Tree 子串匹配结构
2010-03-14 19:10 11327Patricia Tree 简称PAT tree ... -
【查找结构6】动态查找树比较
2010-03-12 13:32 11314我们这个专题介绍的动态查找树主要有: 二叉查找树(BST),平 ... -
【查找结构4】红黑树 [RBT]
2010-03-10 10:58 10620大部分转载:http://yanglongylj.blog.1 ...
相关推荐
二叉排序树在查找过程中类似于连续的折半查找,只不过是在树结构中进行,而折半查找是在数组中进行。 8. **应用**: 二叉排序树广泛用于数据库索引、文件系统和虚拟内存管理等场景,而折半查找常用于大量有序数据...
二叉查找树(Binary Search Tree,BST),也称为二叉排序树,是计算机科学中用于组织数据的一种数据结构。它是一种特殊的二叉树,每个节点包含一个键(key)、一个关联的值、一个指向左子树的引用以及一个指向右子树...
二叉排序树(Binary Search Tree,BST),是数据结构领域中一种重要的树形数据结构,它的每个节点都包含一个键值、一个指向左子树的指针和一个指向右子树的指针。在二叉排序树中,任何节点的左子树只包含键值小于该...
二叉排序树(Binary Search Tree, BST),又称为二叉查找树或有序二叉树,是一种特殊的二叉树数据结构。它具有以下性质: 1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 2. 若任意节点...
二叉查找树(Binary Search Tree,BST)是一种特殊的二叉树数据结构,它的每个节点都包含一个键(key)、一个关联的值、一个指向左子树的引用和一个指向右子树的引用。在二叉查找树中,对于任意节点,其左子树中的...
二叉查找树(Binary Search Tree,BST),也称为二叉排序树,是一种特殊的二叉树数据结构,它的每个节点都包含一个键值、一个指向左子树的指针和一个指向右子树的指针。在二叉查找树中,对于任意节点,其左子树中的...
二叉排序树(Binary Search Tree,BST),也称为二叉查找树或有序二叉树,是一种自平衡的二叉树数据结构,它在处理搜索、插入和删除操作时具有较高的效率。二叉排序树的主要特点是:对于任意节点,其左子树中的所有...
二叉排序树(Binary Sort Tree,BST),也称为二叉查找树或有序二叉树,是一种特殊类型的二叉树,其每个节点的左子树只包含比其小的元素,右子树包含比其大的元素,且整个树保持自平衡。在本实验报告中,我们将深入...
在上面的代码中,我们实现了一个二叉排序树的查找函数`Search_BST`,它接受一个二叉排序树`BST`和一个关键字`key`作为输入,返回该关键字在树中的位置。如果找不到,则返回-1。 哈希表 哈希表是一种基于哈希函数的...
二叉查找树(Binary Search Tree,BST),也称为二叉排序树,是一种特殊的二叉树数据结构。它的每个节点都包含一个键(key)、一个关联的值、一个指向左子节点的指针和一个指向右子节点的指针。在二叉查找树中,对于...
这些平衡树结构能保证在最坏情况下依然保持较好的性能。不过,对于初学者来说,理解和实现基本的二叉排序树已经是一项有价值的挑战。通过这个课程设计,学生可以深入理解二叉排序树的工作原理,掌握数据结构的基础...
二叉查找树(Binary Search Tree, BST)是一种特殊的数据结构,它在计算机科学中用于高效地存储和检索数据。在二叉查找树中,每个节点包含一个键(key)、一个关联的值、一个指向左子节点的引用以及一个指向右子节点...
二叉排序树(Binary Search Tree, BST),又称二叉查找树或有序二叉树,是一种特殊的二叉树,其特点在于对于任意节点而言,其左子树中的所有节点的值均小于该节点的值,而右子树中的所有节点的值均大于该节点的值。...
二叉排序树(Binary Sort Tree,BST),也称为二叉搜索树,是一种特殊的二叉树数据结构,它的每个节点都包含一个键值,且满足以下性质:对于任意节点,其左子树中的所有节点的键值都小于该节点的键值,而右子树中的...
通过动态规划方法,我们可以有效地找到具有最低平均查找成本的二叉查找树结构,从而显著提高查找效率。这一算法不仅理论意义重大,在实际应用中也具有广泛的适用性,如数据库索引、搜索引擎等高性能数据检索系统的...
二叉查找树(Binary Search Tree,简称BST),是一种特殊的二叉树数据结构,它具有以下特性:对于树中的任意一个节点,其左子树中所有节点的值都小于该节点的值,而右子树中所有节点的值都大于该节点的值。...
在数据结构的学习中,二叉排序树(Binary Search Tree,BST)是一种常见的树形数据结构,它具有查找、插入和删除等操作的高效性。在这个课程设计中,我们将重点探讨如何利用二叉链表作为存储结构来实现二叉排序树,...
**定义**:二叉排序树(Binary Search Tree,BST)是一种特殊的二叉树,其中每个节点的值都大于其左子树中的所有节点的值,并且小于其右子树中的所有节点的值。 **建立二叉排序树**: - **插入操作**:对于每个新...
二叉排序树(Binary Sort Tree,BST)是一种特殊的二叉树,其中每个节点的值都大于其左子树中的任何节点的值,且小于其右子树中的任何节点的值。本课设的目标是编写一个程序,判断给定的二叉树是否满足这一特性,即...
二叉查找树(Binary Search Tree, BST)是另一种用于快速查找和插入的数据结构。二叉查找树的每个节点都包含一个键值和左、右两个子树。在二叉查找树中,左子树上的所有节点的键值都小于其根节点的键值,而右子树上...