自学教程并查集基础
一、概念及其介绍 并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。 并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。 二、适用...
数据结构 第2页
二分搜索树的特性
一、顺序性 二分搜索树可以当做查找表的一种实现。 我们使用二分搜索树的目的是通过查找 key 马上得到 value。minimum、maximum、successor（后继）、predecessor（前驱）、floor（地板）、ceil（天...
二分搜索树节点删除
本小节介绍二分搜索树节点的删除之前，先介绍如何查找最小值和最大值，以及删除最小值和最大值。 以最小值为例（最大值同理）： 查找最小 key 值代码逻辑，往左子节点递归查找下去： 删除二分搜索树的最小 key 值，如果该节点没有右子树，那么直...
二分搜索树层序遍历
二分搜索树的层序遍历，即逐层进行遍历，即将每层的节点存在队列当中，然后进行出队（取出节点）和入队（存入下一层的节点）的操作，以此达到遍历的目的。 通过引入一个队列来支撑层序遍历： 如果根节点为空，无可遍历； 如果根节点不为空： 先将根节点入...
二分搜索树深度优先遍历
二分搜索树遍历分为两大类，深度优先遍历和层序遍历。 深度优先遍历分为三种：先序遍历（preorder tree walk）、中序遍历（inorder tree walk）、后序遍历（postorder tree walk），分别为： 1、前...
二分搜索树节点的查找
二分搜索树没有下标, 所以针对二分搜索树的查找操作, 这里定义一个 contain 方法, 判断二分搜索树是否包含某个元素, 返回一个布尔型变量, 这个查找的操作一样是一个递归的过程, 具体代码实现如下: 以下实例在二分搜索树中寻找 43 ...
二分搜索树节点的插入
首先定义一个二分搜索树，Java 代码表示如下: Node 表示节点，count 代表节点的数量。 以下实例向如下二分搜索树中插入元素 61 的步骤： （1）需要插入的元素 61 比 42 大，比较 42 的右子树根节点。 （2）61 比 ...
二分搜索树
一、概念及其介绍 二分搜索树（英语：Binary Search Tree），也称为 二叉查找树 、二叉搜索树 、有序二叉树或排序二叉树。满足以下几个条件： 若它的左子树不为空，左子树上所有节点的值都小于它的根节点。 若它的右子树不为空，右子...
索引堆及其优化
一、概念及其介绍 索引堆是对堆这个数据结构的优化。 索引堆使用了一个新的 int 类型的数组，用于存放索引信息。 相较于堆，优点如下： 优化了交换元素的消耗。 加入的数据位置固定，方便寻找。 二、适用说明 如果堆中存储的元素较大，那么进行交...
优化堆排序
上一节的堆排序，我们开辟了额外的空间进行构造堆和对堆进行排序。这一小节，我们进行优化，使用原地堆排序。 对于一个最大堆，首先将开始位置数据和数组末尾数值进行交换，那么数组末尾就是最大元素，然后再对W元素进行 shift down 操作，重新...