-
2020-08-03 12:46:56更多相关内容
-
二叉排序树查找成功时的平均查找长度公式及证明
2020-07-28 14:58:23设二叉排序树的高度为h,共有n个结点 有如下性质: 1.前h-1层结点全部占满(即为满二叉树) 2.最后一层结点可以通过平移使得整个树转化成完全二叉树 思路: 首先求前h-1层的对比次数 之后求最后一层的对比次数 公式...二叉排序树是基于二分查找步骤生成的二叉树。
设二叉排序树的高度为h,共有n个结点
有如下性质:
1.前h-1层结点全部占满(即为满二叉树)
2.最后一层结点可以通过平移使得整个树转化成完全二叉树思路:
首先求前h-1层的对比次数
之后求最后一层的对比次数公式为:
下面给出证明过程:
-
数据结构与算法—二叉排序(查找)树
2019-08-19 13:23:31再数据结构中`树`、`图`才是数据结构标志性产物,(线性表大多都现成api可以使用),因为树的`难度相比线性表大一些`并且树的`拓展性很强`,你所知道的树、二叉树、**二叉排序树**,**AVL树**,线索二叉树、**红黑树**...前言
前面介绍学习的大多是线性表相关的内容,把指针搞懂后其实也没有什么难度。规则相对是简单的。
再数据结构中
树
、图
才是数据结构标志性产物,(线性表大多都现成api可以使用),因为树的难度相比线性表大一些
并且树的拓展性很强
,你所知道的树、二叉树、二叉排序树,AVL树,线索二叉树、红黑树、B数、线段树等等高级数据结构。然而二叉排序树是所有的基础,所以彻底搞懂二叉排序树也是非常重要的。树
参考王道数据结构
二叉树也是树的一种,而二叉排序树又是二叉树的一种。
- 树是
递归
的,将树的任何一个节点以及节点下的节点都能组合成一个新的树
。并且很多操作基于递归完成。 - 根节点: 最上面的那个节点(root),根节点
没有前驱节点
,只有子节点(0个或多个都可以) - 层数: 一般认为根节点是
第1层
(有的也说第0层)。而树的高度就是层数最高(上图层数开始为1)节点的层数 - 节点关系:
父节点
:就是链接该节点的上一层节点,孩子节点:
和父节点对应,上下关系。而祖先节点
是父节点的父节点(或者祖先)节点。兄弟节点:
拥有同一个父节点的节点们! - 度: 节点的度就是节点拥有
孩子节点
的个数(是孩子不是子孙).而树的度(最大)节点的度。同时,如果度大于0就成为分支节点
,度等于0就成为叶子节点
(没有子孙)。
相关性质:
- 树的节点数=所有节点度数+1.
- 度为m的树第i层最多有mi-1个节点。(i>=1)
- 高度而h的m叉树最多(mh-1)/(m-1)个节点(
等比数列求和
) - n个节点的m叉树最小高度[logm(n(m-1)+1)]
二叉树
二叉树是一树的一种,但应用比较多,所以需要深入学习。二叉树的每个节点
最多只有两个节点
。二叉树与度为2的树的区别:
- 一:度为2的的树必须有三个节点以上,二叉树可以为空。
- 二:二叉树的度不一定为2:比如说斜树。
- 三:二叉树有左右节点区分,而度为2的树没有左右节点的区分。
几种特殊二叉树:
- 满二叉树。高度为n的满二叉树有2n-1个节点
- 完全二叉树:上面一层全部满,最下一层从左到右顺序排列
- 二叉排序树:树按照一定规则插入排序(本文详解)。
- 平衡二叉树:树上任意节点左子树和右子树深度差距不超过1.
二叉树性质:
相比树,二叉树的性质就是树的性质更加具体化。- 非空二叉树叶子节点数=
度为2的节点树+1
.本来一个节点如果度为1.那么一直延续就一个叶子,但如果出现一个度为2除了延续原来的一个节点,会多出一个节点需要维系。所以到最后会多出一个叶子
。 - 非空第i层最多有2i-1个节点。
- 高为h的树最多有2h-1个节点(等比求和)。
完全二叉树
若从左往右,从上到下编号如图:
二叉排序(搜索)树
概念
前面铺垫那么多,咱们
言归正传
,详细实现一个二叉排序树。首先要了解二叉排序树的规则:- 从任意节点开始,节点左侧节点值总比节点右侧值要小。
例如。一个二叉排序树依次插入15,6,23,7,4,71,5,50
会形成下图顺序
构造
首先二叉排序树是由若干
节点
构成。- 对于node需要这些属性:
left,right,和value
。其中left和right是左右指针,而value是储存的数据,这里用int 类型。
node
类构造为:class node {//结点 public int value; public node left; public node right; public node() { } public node(int value) { this.value=value; this.left=null; this.right=null; } public node(int value,node l,node r) { this.value=value; this.left=l; this.right=r; } }
既然节点构造好了,那么就需要节点等其他信息构造成树。有了链表构造经验,很容易得知一棵树最主要的还是
root根节点
。
所以树的构造为:public class BinarySortTree { node root;//根 public BinarySortTree() {root=null;} public void makeEmpty()//变空 {root=null;} public boolean isEmpty()//查看是否为空 {return root==null;} //各种方法 }
主要方法
- 既然已经构造号一棵树,那么就需要实现主要的方法。因为二叉排序树中每个节点都能看作一棵树。所以我们创建方法的是时候加上
节点参数
(也就是函数对每一个节点都能有效
)
findmax(),findmin()
findmin()找到最小节点:
- 因为所有节点的最小都是往左插入,所以只需要找到最左侧的返回即可。
findmax()找到最大节点:
- 因为所有节点大的都是往右面插入,所以只需要找到最右侧的返回即可。
代码使用递归函数
public node findmin(node t)//查找最小返回值是node,调用查看结果时需要.value { if(t==null) {return null;} else if(t.left==null) {return t;} else return(findmin(t.left)); } public node findmax(node t)//查找最大 { if(t==null) {return null;} else if(t.right==null) {return t;} else return(findmax(t.right)); }
isContains(int x)
这里的意思是查找二叉查找树中是否存在x。
- 假设我们我们插入x,那么如果存在x我们一定会在查找插入
路径的过程中遇到x
。因为你可以如果已经存在的点,再它的前方会走一次和它相同的步骤。也就是说前面固定,我来1w次x,那么x都会到达这个位置
。那么我们直接进行查找比较即可!
public boolean isContains(int x)//是否存在 { node current=root; if(root==null) {return false;} while(current.value!=x&¤t!=null) { if(x<current.value) {current=current.left;} if(x>current.value) {current=current.right;} if(current==null) {return false;}//在里面判断如果超直接返回 } //如果在这个位置判断是否为空会导致current.value不存在报错 if(current.value==x) {return true;} return false; }
insert(int x)
插入的思想和前面
isContains
类似。找到自己的位置(空位置)插入。但是又不太一样。你可能会疑问为什么不直接找到最后一个空,然后将current赋值过去current=new node(x)
。这样的化current就相当于指向一个new node(x)节点。和树就脱离关系,所以要提前判定是否为空,若为空将它的left或者right
赋值即可。public node insert(int x)// 插入 t是root的引用 { node current = root; if (root == null) { root = new node(x); return root; } while (current != null) { if (x < current.value) { if (current.left == null) { return current.left = new node(x);} else current = current.left;} else if (x > current.value) { if (current.right == null) { return current.right = new node(x);} else current = current.right; } } return current;//其中用不到 }
- 比如说上面结构
插入51
delete(int x)
删除操作算是一个相对较难理解的操作了。
删除节点规则:- 先找到这个点。这个点用这个点的子树可以补上的点填充该点,然后在以这个点为头删除替代的子节点(调用递归)然后在添加到最后情况(只有一个分支,等等)。
- 首先要找到移除的位置,然后移除的那个点
分类讨论
,如果有两个儿子,就选右边儿子的最左侧那个点替代
,然后再子树删除替代的那个点
。如果是一个节点,判断是左空还是右空,将这个点指向不空的那个
。不空的那个就替代了这个节点。入股左右都是空,那么他自己变空null就删除了。
删除的节点没有子孙:
- 这种情况不需要考虑,直接删除即可。(途中红色点)。另
节点=null
即可。
左节点为空、右节点为空:
- 此种情况也很容易,直接将
删除点的子节点放到被删除位置
即可。
左右节点均不空
- 这种情况相对是复杂的。因为这
涉及
到一个策略问题。
- 如果拿
19或者71
节点填补。虽然可以保证部分侧大于小于该节点,但是会引起合并的混乱
.比如你若用71替代23节点。那么你需要考虑三个节点(19,50,75)
之间如何处理,还要考虑他们是否满,是否有子女。这是个极其复杂的过程。 - 首先,我们要分析我们要的这个点的属性:能够继承被删除点的所有属性。如果取左侧节点(例如17)那么首先能满足所有右侧节点都比他大(右侧比左侧大)。那么就要再这边
选一个最大的点
让左半枝都比它小。我们分析左支最大的点
一定是子树最右侧
! - 如果这个节点是最底层我们很好考虑,可以
直接替换值,然后将最底层的点删除
即可。但是如果
这个节点有左枝
。我们该怎么办? - 这个分析起来也不难,用递归的思想啊。我们删除这个节点,用可以
满足的节点替换
了。会产生什么样的后果?
- 多出个用过的19节点,转化一下,在左子树中删除
19
的点!那么这个问题又转化为删除节点的问题,查找左子树中有没有能够替代19
这个点的。
所以整个删除算法流程为:
代码为public node remove(int x, node t)// 删除节点 { if (t == null) { return null; } if (x < t.value) { t.left = remove(x, t.left); } else if (x > t.value) { t.right = remove(x, t.right); } else if (t.left != null && t.right != null)// 左右节点均不空 { t.value = findmin(t.right).value;// 找到右侧最小值替代 t.right = remove(t.value, t.right); } else // 左右单空或者左右都空 { if (t.left == null && t.right == null) { t = null; } else if (t.right != null) { t = t.right; } else if (t.left != null) { t = t.left; } return t; } return t; }
完整代码
二叉排序树完整代码为:
package 二叉树; import java.util.ArrayDeque; import java.util.Queue; import java.util.Stack; public class BinarySortTree { class node {// 结点 public int value; public node left; public node right; public node() { } public node(int value) { this.value = value; this.left = null; this.right = null; } public node(int value, node l, node r) { this.value = value; this.left = l; this.right = r; } } node root;// 根 public BinarySortTree() { root = null; } public void makeEmpty()// 变空 { root = null; } public boolean isEmpty()// 查看是否为空 { return root == null; } public node findmin(node t)// 查找最小返回值是node,调用查看结果时需要.value { if (t == null) { return null; } else if (t.left == null) { return t; } else return (findmin(t.left)); } public node findmax(node t)// 查找最大 { if (t == null) { return null; } else if (t.right == null) { return t; } else return (findmax(t.right)); } public boolean isContains(int x)// 是否存在 { node current = root; if (root == null) { return false; } while (current.value != x && current != null) { if (x < current.value) { current = current.left; } if (x > current.value) { current = current.right; } if (current == null) { return false; } // 在里面判断如果超直接返回 } // 如果在这个位置判断是否为空会导致current.value不存在报错 if (current.value == x) { return true; } return false; } public node insert(int x)// 插入 t是root的引用 { node current = root; if (root == null) { root = new node(x); return root; } while (current != null) { if (x < current.value) { if (current.left == null) { return current.left = new node(x);} else current = current.left;} else if (x > current.value) { if (current.right == null) { return current.right = new node(x);} else current = current.right; } } return current;//其中用不到 } public node remove(int x, node t)// 删除节点 { if (t == null) { return null; } if (x < t.value) { t.left = remove(x, t.left); } else if (x > t.value) { t.right = remove(x, t.right); } else if (t.left != null && t.right != null)// 左右节点均不空 { t.value = findmin(t.right).value;// 找到右侧最小值替代 t.right = remove(t.value, t.right); } else // 左右单空或者左右都空 { if (t.left == null && t.right == null) { t = null; } else if (t.right != null) { t = t.right; } else if (t.left != null) { t = t.left; } return t; } return t; } }
结语
- 这里我们优先学习了树,二叉树,以及二叉搜素树的基本构造。对于二叉搜素树
插入查找比较容易
理解但是实现的时候要注意函数对参数的引用等等。需要认真考虑。 - 而偏有难度的是二叉树的删除,利用一个递归的思想,要找到特殊情况和普通情况,递归一定程度也是
问题的转化
(转成自己相同问题,作用域减小)需要思考。 - 下面还会介绍二叉搜素树的三序遍历(
递归和非递归
).和层序遍历。需要的朋友请持续关注。另外,笔者数据结构专栏欢迎查房。! - 如果对
后端、爬虫、数据结构算法
等感性趣欢迎关注我的个人公众号交流:bigsai
。回复爬虫,数据结构等有精美资料一份。
- 树是
-
数据结构—二叉排序树的原理以及Java代码的完全实现
2020-04-27 17:34:41本文详细介绍了二叉排序树的原理,并且提供了Java代码的完全实现。二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。本文详细介绍了二叉排序树的原理,并且提供了Java代码的完全实现。
文章目录
1 二叉排序树的概述
本文没有介绍一些基础知识。对于常见查找算法,比如顺序查找、二分查找、插入查找、斐波那契查找还不清楚的,可以看这篇文章:常见查找算法详解以及Java代码的实现。对于树和二叉树的概念还不清楚的,建议看这个专栏:树。
假设查找的数据集是普通的顺序存储,那么插入操作就是将记录放在表的末端,给表记录数加一即可,删除操作可以是删除后,后面的记录向前移,也可以是要删除的元素与最后一个元素互换,表记录数减一,反正整个数据集也没有什么顺序,这样的效率也不错。应该说,插入和删除对于顺序存储结构来说,效率是可以接受的,但这样的表由于无序造成查找的效率很低。
如果查找的数据集是有序线性表,并且是顺序存储的,查找可以用折半、插值、斐波那契等查找算法来实现,可惜,因为有序,在插入和删除操作上,为了维持顺序,需要移动大量元素,就需要耗费大量的时间。
有没有一种即可以使得插入和删除效率不错,又可以比较高效率地实现查找的算法呢?这就是二叉排序树。
二叉排序树(Binary Sort Tree),又称为二叉查找树/二叉搜索树(binary search tree)。它是具有下列性质的二叉树:
- 若它的左子树不空,则左子树上所有节点的值均小于它的根结构的值;
- 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
- 它的左、右子树也分别为二叉排序树;
- 二叉排序树也可以是一个空树。
构造一棵二叉排序树的目的,其主要目的并不是为了排序,而是为了提高查找和插入删除关键字的速度,用以提升数据结构的综合能力。不管怎么说,在一个有序数据集上的查找,速度总是要快于无序的数据集的,而二叉排序树这种非线性的结构,也有利于插入和删除的实现。
2 二叉排序树的构建
2.1 类架构
首先,最简单的节点对象还是需要一个数据域和两个引用域。
另外还需要一个比较器的引用,因为需要对元素进行排序,自然需要比较元素的大小,如果外部传递了比较器,那么就使用用户指定的比较器进行比较,否则,数据类型E必须是Comparable接口的子类,否则因为不能比较而报错。
另外,还需要提供中序遍历的方法,该遍历方法对于二叉排序树的结果将会顺序展示。
public class BinarySearchTree<E> { /** * 外部保存根节点的引用 */ private BinaryTreeNode<E> root; /** * 自定义比较器 */ private Comparator<? super E> cmp; /** * 树节点的数量 */ private int size; /** * 内部节点对象 * * @param <E> 数据类型 */ public static class BinaryTreeNode<E> { //数据域 E data; //左子节点 BinaryTreeNode<E> left; //右子节点 BinaryTreeNode<E> right; public BinaryTreeNode(E data) { this.data = data; } @Override public 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 ((Comparable<E>) e1).compareTo(e2); } } /** * 保存遍历出来的节点数据 */ List<BinaryTreeNode<E>> 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(BinaryTreeNode<E> root) { BinaryTreeNode<E> left = getLeft(root); if (left != null) { //如果左子节点不为null,则继续递归遍历该左子节点 inorderTraversal(left); } //添加数据节点 str.add(root); //获取节点的右子节点 BinaryTreeNode<E> right = getRight(root); if (right != null) { //如果右子节点不为null,则继续递归遍历该右子节点 inorderTraversal(right); } } /** * 获取左子节点 * * @param parent 父节点引用 * @return 左子节点或者null--表示没有左子节点 */ public BinaryTreeNode<E> getLeft(BinaryTreeNode<E> parent) { return parent == null ? null : parent.left; } /** * 获取右子节点 * * @param parent 父节点引用 * @return 右子节点或者null--表示没有右子节点 */ public BinaryTreeNode<E> getRight(BinaryTreeNode<E> parent) { return parent == null ? null : parent.right; } /** * 获取根节点 * * @return 根节点 ;或者null--表示空树 */ public BinaryTreeNode<E> 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, BinaryTreeNode<E> root) { /*null校验*/ if (root == null) { return false; } /*调用比较的方法*/ int i = compare(e, root.data); /*如果大于0,则说明e>root.date 继续查询右子树*/ if (i > 0) { return contains(e, root.right); /*如果小于0,则说明e<root.date 继续查询左子树*/ } else if (i < 0) { return contains(e, root.left); } else { /*如果等于0,则说明e=root.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 BinaryTreeNode<E> insert(E e, BinaryTreeNode<E> root) { /*没有查找到,那么直接构建新的节点返回,将会在上一层方法中被赋值给其父节点的某个引用,这个插入的位置肯定是该遍历路径上的最后一点 * 即插入的元素节点肯定是属于叶子节点*/ if (root == null) { size++; return new BinaryTreeNode<>(e); } /*调用比较的方法*/ int i = compare(e, root.data); /*如果大于0,则说明e>root.date 继续查询右子树*/ if (i > 0) { //重新赋值 root.right = insert(e, root.right); /*如果小于0,则说明e<root.date 继续查询左子树*/ } else if (i < 0) { //重新赋值 root.left = insert(e, root.left); } else { /*如果等于0,则说明e=root.date 即存在节点 什么都不做*/ } //没查询到最底层,则返回该节点 return root; }
2.3.1 测试
现在我们想要构建如下一颗排序二叉树:
首先要插入根节点47,然后是第二层的节点16、73,然后是第三层的节点1、24、59、88,然后是第四层的节点20、35、62、77。每一层内部节点的顺序可以不一致,但是每一层之间的大顺序一定要保持一致,否则虽然中序遍历输出的时候能够正常输出,但是树的结构不能保证。
public class BinarySearchTreeTest { BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>(); @Test public 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 BinaryTreeNode<E> findMin(BinaryTreeNode<E> root) { if (root == null) { return null; /*如果该节点没有左右子节点,那么该节点就是最小的节点,返回*/ } else if (root.left == null) { return root; } /*如果该节点存在左子节点,那么继续向左递归查找*/ return findMin(root.left); } /** * 查找最大的节点 * * @param root 根节点 * @return 最大的节点 */ private BinaryTreeNode<E> findMax(BinaryTreeNode<E> 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 BinaryTreeNode<E> delete(E e, BinaryTreeNode<E> root) { /*没有查找到,那么什么都不做*/ if (root == null) { return null; } /*调用比较的方法*/ int i = compare(e, root.data); /*如果大于0,则说明e>root.date 继续查询右子树*/ if (i > 0) { //从新赋值 root.right = delete(e, root.right); /*如果小于0,则说明e<root.date 继续查询左子树*/ } else if (i < 0) { //从新赋值 root.left = delete(e, root.left); } else { /*如果等于0,则说明e=root.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(BinaryTreeNode<E> root, BinaryTreeNode<E> 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 { BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>(); @Test public 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次比较才可以得到结果,二者差异很大。
也就是说,我们希望二叉排序树是比较平衡的,即其深度与完全二叉树相同,均为|log2n+1|(|x|表示不大于x的最大整数),那么查找的时间复杂也就为O(logn),近似于折半查找,事实上,上图的左图也不够平衡,明显的左重右轻。而极端情况下的右图,则完全退化成为链表,查找的时间复杂度为O(n),这等同于顺序查找。
因此,如果我们希望对一个集合按二叉排序树查找,最好是把它构建成一棵平衡的二叉排序树,防止极端情况的发生。这样我们就引申出另一个问题,如何让二叉排序树平衡的问题。关于这个问题,在后续的平衡二叉树(AVL树)的部分将会详细解释!
相关参考:
- 《算法》
- 《算法图解》
- 《大话数据结构》
如果有什么不懂或者需要交流,可以留言。另外希望点赞、收藏、关注,我将不间断更新各种Java学习博客!
-
排序算法 归并排序(普通归并排序、自然归并排序)
2019-10-19 14:51:16将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。归并排序是一种稳定的排序方法。 归并排序是稳定排序,需... -
十大经典排序算法
2021-11-02 10:01:51第1关:冒泡排序 任务描述 本关任务:实现冒泡排序算法,并将乱序数列变成升序。 相关知识 为了完成本关任务,你需要掌握:1.冒泡排序算法。 冒泡排序算法 冒泡排序重复地遍历待排序的数列,每次比较两个相邻... -
排序算法 选择排序(简单排序、堆排序)
2019-10-18 14:08:30最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录。最坏情况下,即待排序记录初始状态是按第一条记录最小,之后的记录从小到大顺序排列,则需要移动记录的次数最多为3(n-1)。简单选择排序... -
排序算法整合(冒泡,快速,希尔,拓扑,归并)
2019-08-20 14:09:50冒泡排序介绍 冒泡排序(Bubble Sort),又被称为气泡排序或泡沫排序。 它是一种较简单的排序算法。它会遍历若干次要排序的数列,每次遍历时,它都会从前往后依次的比较相邻两个数的大小;如果前者比后者大,则... -
数据结构复习(排序)
2021-06-02 22:09:34在具有n个元素的序列中进行查找,平均查找长度为O(n)的方法是( )。 A 顺序查找方法 B 散列查找方法 C 分块查找方法 D 树形查找方法 顺序查找方法的优点之一是( )。 A 对于被查找对象几乎没有限制 B 适合排序连续顺序... -
万字手撕七大排序(代码+动图演示)
2022-04-29 13:53:41万字手撕七大排序(代码+动图演示) -
二叉排序树和平衡二叉树
2019-11-29 16:14:091)左子树不为空,则左子树上所有关键字的值均小于根关键字的值。 2)右子树不为空,则右子树上所有关键字的值均大于根关键字的值。 3)左右子树各是一棵二叉排序树。 存储结构 二叉排序树采用二叉链表进行存储,... -
Python实现冒泡排序
2020-07-06 23:22:30Python实现冒泡排序 -
数据结构课程设计(七)---排序算法比较
2020-06-22 11:43:04利用随机函数产生N个随机整数(N = 500,1000,1500,2000,2500,…,30000),利用直接插入排序、折半插入排序、希尔排序(对于不同数量的数据,生成不同的增量序列)、起泡排序、快速排序、选择排序、堆排序、两路... -
数据结构期末复习-二叉排序树的构造
2021-06-20 15:28:41二叉排序树 定义: 二叉排序树或者是一棵空树;或者是具有如下特性的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于根结点的值; 它的左、... -
二叉排序树的创建,插入及删除 - C语言
2020-11-09 22:17:08这里的二叉排序树的创建是根据课本上写的,其中掺杂了递归思想,之前的写的二叉树的创建是为非递归的方法https://blog.csdn.net/qq_43402544/article/details/109228383。 完整代码如下: #include <stdio.h> ... -
c语言合并排序算法_合并排序算法
2020-07-28 22:29:17c语言合并排序算法 合并排序算法 (Merge Sort Algorithm) Merge Sort follows the rule of Divide and Conquer to sort a given set of numbers/elements, recursively, hence consuming less time. 合并排序遵循... -
二叉排序树的理解和实现(Java)
2019-03-12 15:12:53二叉排序树的定义和性质 二叉排序树又称二叉排序树。它或者是一个空树,或者是一个具有下列性质的二叉树: 若它的左子树不空,则左子树上所有节点的值均小于它的根结构的值 若它的右子树不空,则右子树上所有结点的... -
置换选择排序算法详解(C语言实现)
2020-03-18 17:48:24上一节介绍了增加 k-路归并排序中的 k 值来提高外部排序效率的方法,而除此之外,还有另外一条路可走,即减少初始归并段的个数,也就是本章第一节中提到的减小 m 的值。 m 的求值方法为:m=⌈n/l⌉(n 表示为外部... -
【数据结构】第10章 排序
2021-11-22 23:59:319.1概述 1. 排序方法的稳定和不稳定 在排序前后,含相等关键字的记录的相对位置保持不变,... 排序期间文件的全部记录不能同时存放在计算机的内存中,要借助计算机的外存才能完成排序,称之为“外部排序”。 ... -
排序算法:堆排序算法实现及分析
2018-02-23 20:48:53堆排序介绍堆排序(Heap Sort)就来利用堆(假设利用大顶堆)进行排序的方法。它的基本思想是,将待排序的序列构成一个大顶堆。此时,整个序列的最大值就是堆顶的根结点。将它移走(其实就是将其与堆数组的末尾元素... -
二叉排序树平均检索长度(ASL)的算法
2018-12-01 13:20:05对于二叉排序树的ASL算法 二叉排序树的特点是左孩子小于根节点,右孩子大于根节点 之前寻找博客上计算ASL的算法时,看到用的是设置一个max值来判断是否换层,遍历二叉排序树,若是大于max则是属于同一层,赋值给... -
听说你还在纠结自己没访问量?成不了“博客专家”?
2019-12-18 16:29:19或者这样想过:“这文章写得明明比我烂很多,凭什么这么多浏览量?”; 虽然在我看来这是极其严重的内耗,对自己一点帮助都没有,但是自己认认真真写的东西没人看,确实比较打击信心和热情,既然如此,我就在文章... -
Python常用 排序算法
2020-02-09 22:02:221.1 冒泡排序 1.2 选择排序 1.3 插入排序 NB 三人组 2.1 快速排序 2.2 堆排序 2.3 归排序 算法常识 3.1 时间复杂度/空间复杂度/稳定性 3.2 二分查找 3.3 递归 数据结构: 栈 队列 链表 3.1 单向链表 3.2 单向... -
68,45,139,70,58,101,10,88,94)建立一个二叉排序树,画出该树,并求在等概率情况下查找成功的平均...
2020-12-02 23:05:39用序列(46,68,45,139,70,58,101,10,88,94)建立一个二叉排序树,画出该树,并求在等概率情况下查找成功的平均查找长度 二叉排序树: 二叉排序树要么是空二叉树,要么具有如下特点: 二叉排序树中,如果其... -
❤️爆肝3万字,最硬核丨Mysql 知识体系、命令全集 【建议收藏 】❤️
2021-09-01 11:06:12关键字和函数建议用大写 3) 如果提示符为 '> 那么需要输入一个'回车 4) 命令打错了换行后不能修改, 可以用 \c 取消 2. 数据库操作 查看数据库 show databases; 创建数据库 create database 库名 default charset=... -
详解数据结构【八大排序】(源码实现)(动图分析)
2021-12-21 14:55:22八大排序!!!排序的概念及其运用,常见排序算法的实现,排序算法复杂度及稳定性分析 -
几种常用的排序算法(快速排序,希尔排序,堆排序,选择排序,冒泡排序)
2017-10-17 20:47:19(1)将所要进行的排序序列分为左右两个部分,如果要进行排序的序列的起始元素下标为first,最后一个元素的下标为last,那么左右两部分之间的临界点下标mid=(first+last)/2,这两部分分别是A[first … -
数据结构 作业答案 第8章 排序
2020-06-14 18:19:25(2)从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端的方法,称为( )。 A.归并排序 B.冒泡排序 C.插入排序 D.选择排序 答案:D (3)对n个不同的关键字由小到大进行冒泡排 -
numpy模块安装不成功简单解决方法总结
2020-06-17 19:06:41如果你装的vs版本是2013可以使用下面命令: SETVS90COMNTOOLS=%VS120COMNTOOLS% 不一定会成功,但可以一试~ 方法二: 看清楚根据你的python版本和你电脑的bit数来选择whl文件。为了能够安装whl文件,你需要首先安装... -
linux内核双链表实现快速排序
2020-09-22 03:20:02C语言,linux内核双链表实现快速排序,主要涉及到内核链表的基础操作,基地址转换和内核链表两个任意结点互换的实现。