二叉搜索树的定义
和前面一篇讨论二叉树有一点不一样,二叉搜索树它本身是一种二叉树,但是它有一个特殊的地方。任何一个二叉树中间的节点都是可以比较的。他们有一个key的值用于比较节点之间的大小。而且,对于任意一个二叉搜索树中间的节点,它左子树中间的节点值小于它,而它右子树的节点值则大于或等于它。一个典型的搜索二叉树如下图所示:
在有的情况下,我们为了实现某些方法方便会在树中间增加一些属性,比如指向父节点的引用,当前节点所有子节点元素个数。
下面是一种二叉树节点的定义:
private static class BinaryNodeWithSize<T> extends BinaryNode<T> { BinaryNodeWithSize(T x) { super(x); size = 0; } int size; } class BinaryNode<T> { T element; BinaryNode<T> left; BinaryNode<T> right; BinaryNode<T> parent; BinaryNode(T element) { this.element = element; left = right = parent = null; } }
这里通过继承的方式实现一种包含指向父节点引用和子节点个数的节点类型。
前驱(predecessor)
前驱指的是对指定的一个节点找到一个比它小但是和它值最接近的节点。要求一个节点的前驱比较理想的情况是需要用到节点指向父节点的引用。在具体查找元素的时候需要向上访问。我们主要针对两种情况进行讨论:
1. 如果该节点有左子树,那么和它最接近的那个前驱元素肯定是左子树的最大值。这种情况对应的图如下所示:
实际上这种情况就是要找到节点左子树的最大值。
2. 如果该节点没有左子树,我们需要向上来查找。对于7这个节点来说,我们需要找到比它小的。但是如果它是它父节点的左儿子,则该父节点比它大,不符合要求。需要一直找到将它或者它上面的节点作为右儿子的那个节点。如下图:
所以针对这种情况我们可以得出如下的代码:
public BinaryNode<T> predecessor(BinaryNode<T> t) { if(t != null) { if(t.left != null) return findMax(t.left); BinaryNode<T> y = t.parent; while(y != null && t == y.left) { t = y; y = y.parent; } return y; } return null; }
里面的findMax实现如下:
private BinaryNode<T> findMax(BinaryNode<T> t) { if(t != null) while(t.right != null) t = t.right; return t; }
后继(successor)
后继节点就是比当前节点大的节点集合中最小的那个。求节点的后继和前驱类似。也要考虑两种情况。
1. 如果它有右子树,肯定后继是右子树的最小值。
2. 如果它没有右子树,则后继节点是它向上的树中第一个以它的上级节点为左子树的那个节点。如下图所示:
对应的实现代码则如下:
public BinaryNode<T> successor(BinaryNode<T> t) { if(t != null) { if(t.right != null) return findMin(t.right); BinaryNode<T> y = t.parent; while(y != null && t == y.right) { t = y; y = y.parent; } return y; } return null; } protected BinaryNode<T> findMin(BinaryNode<T> t) { if(t != null) while(t.left != null) t = t.left; return t; }
插入元素(insert)
假定我们要插入一个元素,最基本的思路就是先根据这个要插入的值和树中间的节点进行比较,如果该节点比目标值大,则在节点的左子树里面寻找插入的地方,否则在右子树里面寻找。这里的一个实现用到了递归的思路,使得很多需要考虑的细节都被简化了:
protected BinaryNode<T> insert(T x, BinaryNode<T> tt) { BinaryNodeWithSize<T> t = (BinaryNodeWithSize<T>) tt; if(t == null) t = new BinaryNodeWithSize<T>(); else if(x.compareTo(t.element) < 0) t.left = insert(x, t.left); else if(x.compareTo(t.element) > 0) t.right = insert(x, t.right); else throw new DuplicateItemException(x.toString()); t.size++; return t; }
这里递归的一个妙用就是在每次要插入一个元素的时候,我们需要修改经历过的节点size值。size表示该节点下面所有子树元素的个数。通过返回修改后的根节点很多需要考虑修改的细节都通过递归给自动实现了。
如果我们考虑一个非递归的版本实现,则会发现要繁琐一些,当然,这里返回的不再是修改后的树的根节点,而是当前插入的元素节点:
protected BinaryNode<T> insertIter(T x, BinaryNode<T> t) { BinaryNode<T> prev = null, node = t; while(t != null) { prev = t; if(x.compareTo(t.element) < 0) { t.size++; t = t.left; } else if(x.compareTo(t.element) > 0) { t.size++; t = t.right; } else throw new DuplicateItemException(x.toString()); } if(prev == null) node = new BinaryNode<T>(x); else { if(x.compareTo(prev.element) < 0) { prev.left = new BinaryNode<T>(x); prev.left.parent = prev; } else { prev.right = new BinaryNode<T>(x); prev.right.parent = prev; } } return node; }
通过比较这两部分的代码,我们会发现使用递归有的时候确实可以隐藏了很多需要考虑的细节,而且代码也会简单很多。
删除元素(remove)
和前面添加元素的方式相反,这里要找到需要删除的元素然后删除它。删除元素的过程可能会复杂一点。针对它所在节点的情况。我们分别进行讨论。
1. 如果该节点是一个叶节点。
直接删除该元素,将该父节点所指向它的引用置为null。
2. 如果该节点只有一个子树
将它的左/右子节点替换它本身。
3. 如果该节点有两个子树
笼统的来说,既然它有左右两个子节点,可以取它的后继元素,也就是右子树的最小值来替换它。然后在右子树中删除这个最小值节点。根据右子节点是否有左子树,具体的形式还会稍微有点不一样。
一种情况如下,右子节点没有左子树,这意味着它的右子节点就是右子树最小的元素:
如果节点的右子节点有左子树的话,则对应下面的情形:
针对前面的那些讨论,下面是remove方法的实现:
protected BinaryNode<T> remove(T x, BinaryNode<T> tt) { BinaryNodeWithSize<T> t = (BinaryNodeWithSize<T>) tt; if(t == null) throw new ItemNotFoundException(x.toString()); if(x.compareTo(t.element) < 0) t.left = remove(x, t.left); else if(x.compareTo(t.element) > 0) t.right = remove(x, t.right); else if(t.left != null && t.right != null) { t.element = findMin(t.right).element; t.right = removeMin(t.right); } else return (t.left != null) ? t.left : t.right; t.size--; return t; } protected BinaryNode<T> removeMin(BinaryNode<T> tt) { BinaryNodeWithSize<T> t = (BinaryNodeWithSize<T>) tt; if(t == null) throw new ItemNotFoundException(); if(t.left == null) return t.right; t.left = removeMin(t.left); t.size--; return t; }
remove方法在这里采用递归的方式返回待删除子树的根节点,和前面的思路类似。
第k小的元素
在节点增加了size属性之后,我们需要求这个第k小元素的问题就比较简单了。首先我们从树的根节点开始,比较这个目标k值和它的左子节点的元素个数,如果它小于或者等于左子节点元素个数的话,则需要在左子树里面继续查找。如果k大于左子树个数+1的话,则在右子树里查找k-t.left.size - 1。这里判断查找到的条件是k == t.left.size + 1。因为这正好表示k的值和当前节点对应。
protected BinaryNode<T> findKth(int k, BinaryNode<T> t) { if(t == null) throw new IllegalArgumentException(); int leftSize = (t.left != null) ? ((BinaryNodeWithSize<T>) t.left).size : 0; if(k <= leftSize) return findKth(k, t.left); if(k == leftSize + 1) return t; return findKth(k - leftSize - 1, t.right); }
总结
二叉搜索树的定义使得查找和插入元素的时候可以按照一个类似于二分法的思路去操作节点。在它的基础上衍生出来的计算节点和各种插入删除操作都比较常见,这里对他们的过程做一个简单的整理。里面还有一些结合指向父节点的小细节的地方考虑还不够成熟。
相关推荐
平衡二叉树是在构造二叉排序树的过程中,每当插入一个新结点时,首先检查是否因插入新结点而破坏了二叉排序树的平衡性,若是,则找出其中的最小不平衡子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各...
二叉搜索树是一种特殊的二叉树,它的每个节点的左子树中的所有元素都小于该节点,而右子树中的所有元素都大于该节点。 二叉搜索树的特性 二叉搜索树具有一些重要特性,如有序性、唯一性和高度平衡性,这些特性使得它...
可以是一颗空树,也可以是一颗具有如下特性的非空二叉树: 1. 若左子树非空,则左子树上所有节点关键字值均不大于根节点的关键字值; 2. 若右子树非空,则右子树上所有节点关键字值均不小于根节点的关键字值; 3...
本文使用 Python 实现二叉搜索树的删除功能,在此之前必须先知道二叉搜索树的特性: 1. 如果二叉树的左子树不为空,则左子树上所有节点的值均小于它的根节点的值。 2. 如果二叉树的右子树不为空,则右子树上所有...
14.4 带有相同关键字元素的二叉搜索树 14.5 索引二叉搜索树 14.6 应用 14.6.1 直方图 14.6.2 箱子装载问题的最优匹配法 14.6.3 交叉分布 第15章 平衡搜索树 15.1 AVL树 15.1.1 定义 15.1.2 AVL树的高度 15.1.3 AVL树...
二叉搜索树的特性 二叉搜索树由于其独特的数据结构,使得其无论在增删,还是查找,时间复杂度都是O(h),h为二叉树的高度。因此二叉树应该尽量的矮,即左右节点尽量平衡。 二叉搜索树的构造 要构造二叉搜索树,首先要...
(2)从第二课二叉树开始,依次把后一棵二叉树的根结点作为一棵二叉树根节点的右孩子,当所有二叉树连起来后,此时所得到的二叉树就是由森林转换得到的二叉树。 3、二叉树转换为树或森林 (1)加线——若某个结点x是...
考察点:二叉搜索树、优先队列、堆 栈和队列 考察点:栈、队列特性 考察点:优先队列、大根堆 查找和排序 考察点:线性查找、二分查找 递归和循环 考察点:递归、循环、动态规划 考察点:递归 注:等同于上一题,...
4.3 查找树ADT——二叉查找树 4.3.1 contains方法 4.3.2 findMin方法和findMax方法 4.3.3 insert方法 4.3.4 remove方法 4.3.5 平均情况分析 4.4 AVL树 4.4.1 单旋转 4.4.2 双旋转 4.5 伸展树 4.5.1 一个简单的想法...
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 例子:表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法...
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 例子:表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法...
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 例子:表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法...
常见的树结构包括二叉树、二叉搜索树、平衡二叉树、堆等。 图(Graph):由节点和边组成的非线性数据结构,用于表示各种关系。常见的图算法包括最短路径算法、深度优先搜索(DFS)、广度优先搜索(BFS)等。 哈希...
表达式树 4.3 查找树adt——二叉查找树 4.3.1 contains方法 4.3.2 findmin方法和findmax方法 4.3.3 insert方法 4.3.4 remove方法 4.3.5 平均情况分析 4.4 avl树 4.4.1 单旋转 4.4.2 双旋转 4.5...
表达式树 4.3 查找树adt——二叉查找树 4.3.1 contains方法 4.3.2 findmin方法和findmax方法 4.3.3 insert方法 4.3.4 remove方法 4.3.5 平均情况分析 4.4 avl树 4.4.1 单旋转 4.4.2 双旋转 4.5...
二叉搜索树 联合查找 高级结构(例如段树、二叉索引树等) 课程大纲 - Java 高级算法 算法进阶:同题对应的新问题 第四周 回顾概念 简单排序:插入排序是三者中最好的(比较,交换) 高级排序:快速排序(枢轴、就地...
e. 如有可能,请建立一个存储商品名称和数量的文本文件,并为二叉搜索树建立一个成员函数SetupInventory(),用于从该文本文件中读取库存商品的数据, 实验报告要求: 1、 按要求记录下二叉搜索树的完整实验...
11.1.8 二叉搜索树的高度 327 11.2 AVL树 328 11.2.1 基本概念 328 11.2.2 AVL树的高度 328 11.2.3 AVL树的描述 329 11.2.4 AVL搜索树的搜索 329 11.2.5 AVL搜索树的插入 329 11.2.6 AVL搜索树的删除 332 11.3 红-...
(二叉搜索树的一个特性:通过中序遍历所得到的序列,就是有序的。) 后:左右根 快速排序就是个二叉树的前序遍历,归并排序就是个二叉树的后续遍历 二叉树的问题难点在于,如何把题目的要求细化成每个节点需要做的...