24二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?.pdf
《24二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?.pdf》由会员分享,可在线阅读,更多相关《24二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?.pdf(17页珍藏版)》请在三一文库上搜索。
1、24|二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树? file:/F/temp/geektime/数据结构与算法之美/24二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?.html2019/1/15 15:35:54 24|二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树? 上一节我们学习了树、二叉树以及二叉树的遍历,今天我们再来学习一种特殊的的二叉树,二叉查找树。二叉查找树最大的特点就是,支持动态数据集合的快速 插入、删除、查找操作。 我们之前说过,散列表也是支持这些操作的,并且散列表的这些操作比二叉查找树更高效,时间复杂度是O(1)。既然有了这么高效的散
2、列表,使用二叉树的地方 是不是都可以替换成散列表呢?有没有哪些地方是散列表做不了,必须要用二叉树来做的呢? 带着这些问题,我们就来学习今天的内容,二叉查找树! 二叉查找树(Binary Search Tree) 二叉查找树是二叉树中最常用的一种类型,也叫二叉搜索树。顾名思义,二叉查找树是为了实现快速查找而生的。不过,它不仅仅支持快速查找一个数据,还支 持快速插入、删除一个数据。它是怎么做到这些的呢? 这些都依赖于二叉查找树的特殊结构。二叉查找树要求,在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大 于这个节点的值。 我画了几个二叉查找树的例子,你一看应
3、该就清楚了。 24|二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树? file:/F/temp/geektime/数据结构与算法之美/24二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?.html2019/1/15 15:35:54 前面我们讲到,二叉查找树支持快速查找、插入、删除操作,现在我们就依次来看下,这三个操作是如何实现的。 1.二叉查找树的查找操作 首先,我们看如何在二叉查找树中查找一个节点。我们先取根节点,如果它等于我们要查找的数据,那就返回。如果要查找的数据比根节点的值小,那就在左子 树中递归查找;如果要查找的数据比根节点的值大,那就在右子树中递归查找。
4、24|二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树? file:/F/temp/geektime/数据结构与算法之美/24二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?.html2019/1/15 15:35:54 这里我把查找的代码实现了一下,贴在下面了,结合代码,理解起来会更加容易。 public class BinarySearchTree private Node tree; public Node find(int data) Node p = tree; while (p != null) if (data p.data) p = p.right; el
5、se return p; return null; 24|二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树? file:/F/temp/geektime/数据结构与算法之美/24二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?.html2019/1/15 15:35:54 public static class Node private int data; private Node left; private Node right; public Node(int data) this.data = data; 2.二叉查找树的插入操作 二叉查找树的插入过程有点类似查找操
6、作。新插入的数据一般都是在叶子节点上,所以我们只需要从根节点开始,依次比较要插入的数据和节点的大小关系。 如果要插入的数据比节点的数据大,并且节点的右子树为空,就将新数据直接插到右子节点的位置;如果不为空,就再递归遍历右子树,查找插入位置。同理, 如果要插入的数据比节点数值小,并且节点的左子树为空,就将新数据插入到左子节点的位置;如果不为空,就再递归遍历左子树,查找插入位置。 24|二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树? file:/F/temp/geektime/数据结构与算法之美/24二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?.html2019/1/
7、15 15:35:54 同样,插入的代码我也实现了一下,贴在下面,你可以看看。 public void insert(int data) if (tree = null) tree = new Node(data); return; Node p = tree; while (p != null) if (data p.data) if (p.right = null) p.right = new Node(data); return; 24|二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树? file:/F/temp/geektime/数据结构与算法之美/24二叉树基础(下):有了
8、如此高效的散列表,为什么还需要二叉树?.html2019/1/15 15:35:54 p = p.right; else / data p.data) p = p.right; else p = p.left; if (p = null) return; / 没有找到 / 要删除的节点有两个子节点 24|二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树? file:/F/temp/geektime/数据结构与算法之美/24二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?.html2019/1/15 15:35:54 if (p.left != null Node minP
9、P = p; / minPP表示minP的父节点 while (minP.left != null) minPP = minP; minP = minP.left; p.data = minP.data; / 将minP的数据替换到p中 p = minP; / 下面就变成了删除minP了 pp = minPP; / 删除节点是叶子节点或者仅有一个子节点 Node child; / p的子节点 if (p.left != null) child = p.left; else if (p.right != null) child = p.right; else child = null; if (
10、pp = null) tree = child; / 删除的是根节点 else if (pp.left = p) pp.left = child; else pp.right = child; 实际上,关于二叉查找树的删除操作,还有个非常简单、取巧的方法,就是单纯将要删除的节点标记为“已删除”,但是并不真正从树中将这个节点去掉。这样原 本删除的节点还需要存储在内存中,比较浪费内存空间,但是删除操作就变得简单了很多。而且,这种处理方法也并没有增加插入、查找操作代码实现的难度。 4.二叉查找树的其他操作 除了插入、删除、查找操作之外,二叉查找树中还可以支持快速地查找最大节点和最小节点、前驱节点和后
11、继节点。这些操作我就不一一展示了。我会将相应的 代码放到GitHub上,你可以自己先实现一下,然后再去上面看。 二叉查找树除了支持上面几个操作之外,还有一个重要的特性,就是中序遍历二叉查找树,可以输出有序的数据序列,时间复杂度是O(n),非常高效。因此,二 叉查找树也叫作二叉排序树。 支持重复数据的二叉查找树 前面讲二叉查找树的时候,我们默认树中节点存储的都是数字。很多时候,在实际的软件开发中,我们在二叉查找树中存储的,是一个包含很多字段的对象。我 们利用对象的某个字段作为键值(key)来构建二叉查找树。我们把对象中的其他字段叫作卫星数据。 前面我们讲的二叉查找树的操作,针对的都是不存在键值相
12、同的情况。那如果存储的两个对象键值相同,这种情况该怎么处理呢?我这里有两种解决方法。 第一种方法比较容易。二叉查找树中每一个节点不仅会存储一个数据,因此我们通过链表和支持动态扩容的数组等数据结构,把值相同的数据都存储在同一个节 点上。 第二种方法比较不好理解,不过更加优雅。 每个节点仍然只存储一个数据。在查找插入位置的过程中,如果碰到一个节点的值,与要插入数据的值相同,我们就将这个要插入的数据放到这个节点的右子 树,也就是说,把这个新插入的数据当作大于这个节点的值来处理。 24|二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树? file:/F/temp/geektime/数据结构与
13、算法之美/24二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?.html2019/1/15 15:35:54 当要查找数据的时候,遇到值相同的节点,我们并不停止查找操作,而是继续在右子树中查找,直到遇到叶子节点,才停止。这样就可以把键值等于要查找值的 所有节点都找出来。 24|二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树? file:/F/temp/geektime/数据结构与算法之美/24二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?.html2019/1/15 15:35:54 对于删除操作,我们也需要先查找到每个要删除的节点,然后再按前面讲的删除操
14、作的方法,依次删除。 24|二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树? file:/F/temp/geektime/数据结构与算法之美/24二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?.html2019/1/15 15:35:54 二叉查找树的时间复杂度分析 好了,对于二叉查找树常用操作的实现方式,你应该掌握得差不多了。现在,我们来分析一下,二叉查找树的插入、删除、查找操作的时间复杂度。 实际上,二叉查找树的形态各式各样。比如这个图中,对于同一组数据,我们构造了三种二叉查找树。它们的查找、插入、删除操作的执行效率都是不一样的。 图中第一种二叉查找树,根节点的左
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 24 二叉 基础 有了 如此 高效 列表 为什么 需要
链接地址:https://www.31doc.com/p-5529905.html