怎么查一个网站做的外链,网站模板的好处,国内设计品牌,怎样进行seo推广二叉排序树#xff08;Binary Sort Tree#xff09;#xff0c;又称二叉查找树#xff08;Binary Search Tree#xff09;#xff0c;亦称二叉搜索树。本文详细介绍了二叉排序树的原理#xff0c;并且提供了Java代码的完全实现。 文章目录 1 二叉排序树的概述2 二叉排序… 二叉排序树Binary Sort Tree又称二叉查找树Binary Search Tree亦称二叉搜索树。本文详细介绍了二叉排序树的原理并且提供了Java代码的完全实现。 文章目录 1 二叉排序树的概述2 二叉排序树的构建2.1 类架构2.2 查找的方法2.3 插入的方法2.3.1 测试 2.4 查找最大值和最小值2.5 删除的方法2.5.1 测试 3 二叉排序树的总结 1 二叉排序树的概述
本文没有介绍一些基础知识。对于常见查找算法比如顺序查找、二分查找、插入查找、斐波那契查找还不清楚的可以看这篇文章常见查找算法详解以及Java代码的实现。对于树和二叉树的概念还不清楚的建议看这个专栏树。
假设查找的数据集是普通的顺序存储那么插入操作就是将记录放在表的末端给表记录数加一即可删除操作可以是删除后后面的记录向前移也可以是要删除的元素与最后一个元素互换表记录数减一反正整个数据集也没有什么顺序这样的效率也不错。应该说插入和删除对于顺序存储结构来说效率是可以接受的但这样的表由于无序造成查找的效率很低。
如果查找的数据集是有序线性表并且是顺序存储的查找可以用折半、插值、斐波那契等查找算法来实现可惜因为有序在插入和删除操作上为了维持顺序需要移动大量元素就需要耗费大量的时间。
有没有一种即可以使得插入和删除效率不错又可以比较高效率地实现查找的算法呢这就是二叉排序树。
二叉排序树Binary Sort Tree又称为二叉查找树/二叉搜索树binary search tree。它是具有下列性质的二叉树
若它的左子树不空则左子树上所有节点的值均小于它的根结构的值若它的右子树不空则右子树上所有节点的值均大于它的根节点的值它的左、右子树也分别为二叉排序树二叉排序树也可以是一个空树。
构造一棵二叉排序树的目的其主要目的并不是为了排序而是为了提高查找和插入删除关键字的速度用以提升数据结构的综合能力。不管怎么说在一个有序数据集上的查找速度总是要快于无序的数据集的而二叉排序树这种非线性的结构也有利于插入和删除的实现。
2 二叉排序树的构建
2.1 类架构
首先最简单的节点对象还是需要一个数据域和两个引用域。
另外还需要一个比较器的引用因为需要对元素进行排序自然需要比较元素的大小如果外部传递了比较器那么就使用用户指定的比较器进行比较否则数据类型E必须是Comparable接口的子类否则因为不能比较而报错。
另外还需要提供中序遍历的方法该遍历方法对于二叉排序树的结果将会顺序展示。
public class BinarySearchTreeE {/*** 外部保存根节点的引用*/private BinaryTreeNodeE root;/*** 自定义比较器*/private Comparator? super E cmp;/*** 树节点的数量*/private int size;/*** 内部节点对象** param E 数据类型*/public static class BinaryTreeNodeE {//数据域E data;//左子节点BinaryTreeNodeE left;//右子节点BinaryTreeNodeE right;public BinaryTreeNode(E data) {this.data data;}Overridepublic String toString() {return data.toString();}}/*** 指定比较器** param cmp 比较器*/public BinarySearchTree(Comparator? super E cmp) {this.cmp cmp;}/*** 空构造器*/public BinarySearchTree() {}/*** 是否是空树** return true 是 ;false 否*/public boolean isEmpty() {return size 0;}/*** 返回节点数** return 节点数*/public int size() {return size;}/*** 对元素进行比较大小的方法,如果传递了自定义比较器,则使用自定义比较器,否则则需要数据类型实现Comparable接口** param e1 被比较的第一个对象* param e2 被比较的第二个对象* return 0 相等 ;小于0 e1 e2 ;大于0 e1 e2*/private int compare(E e1, E e2) {if (cmp ! null) {return cmp.compare(e1, e2);} else {return ((ComparableE) e1).compareTo(e2);}}/*** 保存遍历出来的节点数据*/ListBinaryTreeNodeE str new ArrayList();/*** 中序遍历,提供给外部使用的api** return 遍历的数据*/public String toInorderTraversalString() {//如果是空树,直接返回空if (isEmpty()) {return null;}//从根节点开始递归inorderTraversal(root);//获取遍历结果String s str.toString();str.clear();return s;}/*** 中序遍历 内部使用的递归遍历方法,借用了栈的结构** param root 节点,从根节点开始*/private void inorderTraversal(BinaryTreeNodeE root) {BinaryTreeNodeE left getLeft(root);if (left ! null) {//如果左子节点不为null,则继续递归遍历该左子节点inorderTraversal(left);}//添加数据节点str.add(root);//获取节点的右子节点BinaryTreeNodeE right getRight(root);if (right ! null) {//如果右子节点不为null,则继续递归遍历该右子节点inorderTraversal(right);}}/*** 获取左子节点** param parent 父节点引用* return 左子节点或者null--表示没有左子节点*/public BinaryTreeNodeE getLeft(BinaryTreeNodeE parent) {return parent null ? null : parent.left;}/*** 获取右子节点** param parent 父节点引用* return 右子节点或者null--表示没有右子节点*/public BinaryTreeNodeE getRight(BinaryTreeNodeE parent) {return parent null ? null : parent.right;}/*** 获取根节点** return 根节点 ;或者null--表示空树*/public BinaryTreeNodeE getRoot() {return root;}}
2.2 查找的方法
查找的方法很简单
若根节点的关键字值等于查找的关键字成功返回true否则若小于根节点的关键字值递归查左子树若大于根节点的关键字值递归查右子树最终查找到叶子节点还是没有数据那么查找失败则返回false。
/*** 查找,开放给外部使用的api*/
public boolean contains(E e) {return contains(e, root);
}/*** 查找,内部调用的方法,从根节点开始查找** param e 要查找的元素* param root 节点* return false 不存在 true 存在*/
private boolean contains(E e, BinaryTreeNodeE root) {/*null校验*/if (root null) {return false;}/*调用比较的方法*/int i compare(e, root.data);/*如果大于0则说明eroot.date 继续查询右子树*/if (i 0) {return contains(e, root.right);/*如果小于0则说明eroot.date 继续查询左子树*/} else if (i 0) {return contains(e, root.left);} else {/*如果等于0则说明eroot.date 即查询成功*/return true;}
}
2.3 插入的方法
有了二叉排序树的查找函数那么所谓的二叉排序树的插入其实也就是将关键字放到树中的合适位置而已插入操作就好像在调用查找的操作如果找到了那么什么都不做返回false如果没找到则将要插入的元素插入到遍历的路径的最后一点上
若二叉树为空。则单独生成根节点返回true。执行查找算法找出被插节点的父亲节点。判断被插节点是其父亲节点的左、右儿子。将被插节点作为叶子节点插入返回true。如果原节点存在那么什么都不做返回false。注意新插入的节点总是叶子节点。
/*** 插入,开放给外部使用的api** param e 要插入的元素*/
public void insert(E e) {//返回root,但此时新的节点可能已经被插入进去了root insert(e, root);
}/*** 插入,开放给外部使用的api** param es 要插入的元素的数组,注意,数组元素的顺序存储的位置将会影响二叉排序树的生成*/
public void insert(E[] es) {//返回root,但此时新的节点可能已经被插入进去了for (E e : es) {root insert(e, root);}}/*** 插入,内部调用的方法,先从根节点开始递归查找要插入的位置,然后插入** param e 要插入的数据* param root 节点* return 原节点或者新插入的节点*/
private BinaryTreeNodeE insert(E e, BinaryTreeNodeE root) {/*没有查找到,那么直接构建新的节点返回,将会在上一层方法中被赋值给其父节点的某个引用,这个插入的位置肯定是该遍历路径上的最后一点* 即插入的元素节点肯定是属于叶子节点*/if (root null) {size;return new BinaryTreeNode(e);}/*调用比较的方法*/int i compare(e, root.data);/*如果大于0则说明eroot.date 继续查询右子树*/if (i 0) {//重新赋值root.right insert(e, root.right);/*如果小于0则说明eroot.date 继续查询左子树*/} else if (i 0) {//重新赋值root.left insert(e, root.left);} else {/*如果等于0则说明eroot.date 即存在节点 什么都不做*/}//没查询到最底层,则返回该节点return root;
}
2.3.1 测试
现在我们想要构建如下一颗排序二叉树 首先要插入根节点47然后是第二层的节点16、73然后是第三层的节点1、24、59、88然后是第四层的节点20、35、62、77。每一层内部节点的顺序可以不一致但是每一层之间的大顺序一定要保持一致否则虽然中序遍历输出的时候能够正常输出但是树的结构不能保证。
public class BinarySearchTreeTest {BinarySearchTreeInteger binarySearchTree new BinarySearchTree();Testpublic void insert() {//首先要插入根节点47然后是第二层的节点16,73然后是第三层的节点1,24,59,88然后是第四层的节点20,35,62,77。// 每一层内部节点的顺序可以不一致但是每一层之间的打顺序一定要保持一致否则虽然中序遍历输出的时候能够正常输出,但是树的结构不能保证。Integer[] es new Integer[]{47, 16, 73, 1, 24, 59, 88, 20, 35, 62, 77};binarySearchTree.insert(es);//中序遍历输出System.out.println(binarySearchTree.toInorderTraversalString());//查找某个数据是否存在System.out.println(binarySearchTree.contains(1));System.out.println(binarySearchTree.contains(2));}
}
在System.out处打上断点Debug可以看到树结构和我们预想的一致如果改变层间的大顺序那么使用Debug会发现树结构不如预期。 2.4 查找最大值和最小值
很简单最左边的节点一定是最小的最右边的节点一定是最大的。因此查找最小的节点只需要向左递归查找查找最大的节点只需要向右递归查找。
/*** 查找最小的节点** param root 根节点* return 最小的节点*/
private BinaryTreeNodeE findMin(BinaryTreeNodeE root) {if (root null) {return null;/*如果该节点没有左右子节点那么该节点就是最小的节点返回*/} else if (root.left null) {return root;}/*如果该节点存在左子节点那么继续向左递归查找*/return findMin(root.left);
}/*** 查找最大的节点** param root 根节点* return 最大的节点*/
private BinaryTreeNodeE findMax(BinaryTreeNodeE root) {if (root null) {return null;/*如果该节点没有右子节点那么该节点就是最大的节点返回*/} else if (root.right null) {return root;}/*如果该节点存在右子节点那么继续向右递归查找*/return findMax(root.right);
}
2.5 删除的方法
对于二叉排序树的删除就不是那么容易我们不能因为删除了节点而让这棵树变得不满足二叉排序树的特性所以删除需要考虑多种情况。一共有三种情况需要考虑
如果查找到的将要被删除的节点没有子节点那么很简单直接删除父节点对于该节点的引用即可如下图的红色节点 例如删除20之后 如果查找到的将要被删除的节点具有一个子节点那么也很简单直接绕过该节点将原本父节点对于该节点的引用指向该节点的子节点即可如下图的红色节点 例如删除59之后 如果查找到的将要被删除的节点具有两个子节点那么就比较麻烦了如下图的红色节点 比如我们需要删除73那么我们就必须要找出一个已存在的能够替代73的节点然后删除该节点。实际上该73节点的左子树的最大节点62和右子树的最小节点77都能够替代73节点即它们正好是二叉排序树中比它小或比它大的最接近73的两个数。
一般我们选择一种方式即可我们这次使用右子树的最小节点替代要删除的节点使用77替代73之后的结构如下 完整的代码如下 /*** 删除,开放给外部使用的api** param e 要删除的元素*/public void delete(E e) {//返回root,但此时可能有一个节点已经被删除了root delete(e, root);}/*** 删除,内部调用的方法,删除分为三种情况: 1、该节点没有子节点 2、该字节仅有一个子节点 3、该节点具有两个子节点** param e 要删除的数据* param root 根节点* return 该节点*/private BinaryTreeNodeE delete(E e, BinaryTreeNodeE root) {/*没有查找到,那么什么都不做*/if (root null) {return null;}/*调用比较的方法*/int i compare(e, root.data);/*如果大于0则说明eroot.date 继续查询右子树*/if (i 0) {//从新赋值root.right delete(e, root.right);/*如果小于0则说明eroot.date 继续查询左子树*/} else if (i 0) {//从新赋值root.left delete(e, root.left);} else {/*如果等于0则说明eroot.date 即查询成功 开始执行删除*//*如果两个子节点都不为null*/if (root.left ! null root.right ! null) {/*方法1、递归查找最小的节点然后递归删除 该方法不推荐使用*///root.data findMin(root.right).data;//root.right delete(root.data, root.right);/*方法2、递归查找并删除最小的节点 推荐*/root.data findAndDeleteMin(root.right, root);size--;} else {/*如果一个子节点不为null则返回该子节点或者两个子节点都为null则返回null* 此时该root节点已经被绕过了*/root (root.left ! null) ? root.left : root.right;size--;}}//没查询到最底层,则返回该节点return root;}/*** 查找最小的节点并删除* 最小的节点肯定不存在两个子节点,有可能没有子节点,有可能存在右子节点** param root 节点* param parent 节点的父节点* return 被删除的最小的节点*/private E findAndDeleteMin(BinaryTreeNodeE root, BinaryTreeNodeE parent) {//如果节点为null返回if (root null) {return null;/*如果节点的左子节点为null,那么该节点就是最小的节点*//*1、该最小节点肯定没有左子节点因为左子节点比父节点小但是可能有右子节点*//*2、此时该节点可能作为某个节点的左子节点也可能作为原父节点的右子节点即右子树是一颗右斜树这里需要分开讨论*/} else if (root.left null) {//如果该节点是父节点的右子节点,说明还没进行递归或者第一次递归就找到了最小节点.//那么此时,应该让该节点的父节点的右子节点指向该节点的右子节点,并返回该节点的数据该节点由于没有了强引用会被GC删除if (root parent.right) {parent.right root.right;} else {//如果该节点不是父节点的右子节点说明进行了多次递归。//那么此时,应该让该节点的父节点的左子节点指向该节点的右子节点,并返回该节点的数据该节点由于没有了强引用会被GC删除parent.left root.right;}//返回最小节点的数据return root.data;}//递归调用,注意此时是往左查找return findAndDeleteMin(root.left, root);}
2.5.1 测试
public class BinarySearchTreeTest {BinarySearchTreeInteger binarySearchTree new BinarySearchTree();Testpublic void test() {//首先要插入根节点47然后是第二层的节点16,73然后是第三层的节点1,24,59,88然后是第四层的节点20,35,62,77。// 每一层内部节点的顺序可以不一致但是每一层之间的打顺序一定要保持一致否则虽然中序遍历输出的时候能够正常输出,但是树的结构不能保证。Integer[] es new Integer[]{47, 16, 73, 1, 24, 59, 88, 20, 35, 62, 77};binarySearchTree.insert(es);//中序遍历输出System.out.println(binarySearchTree.toInorderTraversalString());//查找是否存在System.out.println(binarySearchTree.contains(1));System.out.println(binarySearchTree.contains(2));//移除binarySearchTree.delete(73);//中序遍历输出System.out.println(binarySearchTree.toInorderTraversalString());}
}
3 二叉排序树的总结
总之二叉排序树是以链接的方式存储保持了链接存储结构在执行插入或删除操作时不用移动元素的优点只要找到合适的插入和删除位置后仅需修改链接指针即可。
插入删除的时间性能比较好。而对于二叉排序树的查找走的就是从根节点到要查找的节点的路径其比较次数等于给定值的节点在二叉排序树的层数。极端情况最少为1次即根节点就是要找的节点最多也不会超过树的深度。也就是说二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于二叉排序树的形状是不确定的。
例如{47, 16, 73, 1, 24, 59, 88}这样的数组我们可以构建下图左的二叉排序树。但如果数组元素的次序是从小到大有序如{1, 16, 24, 47, 59, 73, 88}则二叉排序树就成了极端的右斜树注意它依然是一棵二叉排序树如下图右。此时同样是查找节点88左图只需要3次比较而右图就需要7次比较才可以得到结果二者差异很大。 也就是说我们希望二叉排序树是比较平衡的即其深度与完全二叉树相同均为|log2n1|(|x|表示不大于x的最大整数)那么查找的时间复杂也就为O(logn)近似于折半查找事实上上图的左图也不够平衡明显的左重右轻。而极端情况下的右图,则完全退化成为链表查找的时间复杂度为O(n)这等同于顺序查找。
因此如果我们希望对一个集合按二叉排序树查找最好是把它构建成一棵平衡的二叉排序树防止极端情况的发生。这样我们就引申出另一个问题如何让二叉排序树平衡的问题。关于这个问题在后续的平衡二叉树AVL树)的部分将会详细解释
相关参考
《算法》《算法图解》《大话数据结构》 如果有什么不懂或者需要交流可以留言。另外希望点赞、收藏、关注我将不间断更新各种Java学习博客
