二叉树

二叉树(binary tree)是一棵树,其中每个节点都不能有多余两个的子节点。
二叉树的一个性质是一颗平均二叉树的深度要比节点个数N小得多,这个性质有时候很重要。

实现

因为一个二叉树节点最多有两个子节点,所以可以保存直接链接到它们的链。树节点的声明在结构上类似于双链表的声明,在声明中,节点就是有element的信息加上两个到其他节点的引用(left和right)组成的结构

1
2
3
4
5
6
class BinaryNode
{
Object element;
BinaryNode left;
BinaryNode right;
}

例子:表达式树

表达式树的树叶是操作数,比如:常数或者变量名,而其他的节点为操作符。由于所有的操作都是二元的,因此这棵树正好是二叉树。如下图:

查找树ADT——二叉查找树

二叉树的一个重要应用就是它们在查找中的使用。
使二叉树成为查找树的性质是,对于树中的每个节点X,它的左子树中所有想的值小于X中的项,而它右子树中所有项的值大于X中的项。如下图(假设节点元素都是整数):

二叉树查找树要求所有的项都能够排序,需要写出一个interface来标识这个性质,这个接口就是Comparable。
该接口告诉我们树种的两项总可以使用compareTo方法进行比较。由此可以确定所有其他可能的关系,特别是不适用equals方法,而是根据两项相等当且仅当compareTo方法返回0来判断相等。

contains方法

如果在树T中存在还有项X的节点,那么这个操作需要返回true,如果这样的节点不存在则返回false。

findMin方法和findMax方法

这两个private分别返回树中包含最小和最大元素的节点的引用。执行findMin从根开始并且只要有左节点就向左进行,终点就是最小的元素,findMax向右同理。

insert方法

为了将X插入到树T中,可以像用contains那样沿着树查找。如果找到X则什么也不做(或者做一些“更新”),否则将X插入到遍历的路劲上的最后一点上。
重复元素的插入可以通过在节点记录中保留一个附加域以指示发生的频率来处理。这对整个树增加了某些附加空间,但是却比将重复信息放到树中要好(它将使树的深度变得很大)

remove方法

如果节点是一片树叶则立即删除。如果节点有一个子节点,则该节点可以在其父节点调整自己的链以绕过该节点后被删除。如果该节点有两个子节点,一般的删除策略是用其右子树的最小数据代替该节点的数据并递归地删除那个节点(现在它是空的),因为右子树中的最小的节点不可能有左节点,所以第二次remove要容易。

如果删除的次数不多,通常使用的策略是懒惰删除,当一个元素要被删除时,它仍被保留在树中,而是被标记为删除,这在有重复项时很常用,因为此时记录出现频率数的域可以减1.

AVL树

AVL树是带有平衡条件的二叉查找树。这个平衡条件必须要容易保持,而且它保证树的深度需是O(log N)。最简单的想法是要求左右子树具有相同的高度。另一种平衡条件是要求每个节点都必须有相同高度的左子树和右子树。

单旋转

双旋转

树的遍历

遍历的一般方法是首先处理左子树,然后是当前节点,最后是右子树。这个算法的有趣部分除它简单的特性外,还在于其总的运行时间是O(N)。

标准库中的集合与映射

List容器即ArrayList和Linkedlist用于查找效率很低。因此,Collections API提供了两个附加容器Set和Map,它们对诸如插入、删除、和查找等基本操作提供有效的实现。

关于Set接口

Set接口代表不允许重复元素的Collection。由接口SortedSet给出的一种特殊类型的Set保证其中的各项处于有序的状态。

关于Map接口

Map是一个接口,代表由关键字以及它们的值组成的一些项的集合。关键字必须是唯一的,但是若干关键字可以映射到一些相同的值。在SortMap接口中,映射中的关键字保持逻辑上有序的状态。
通过一个Map进行迭代要比Colection复杂,因为Map不提供迭代器而是提供3种方法讲Map对象的视图最为Collection对象返回。由于这些视图本身就是Collection,因此它们可以被迭代。如下:

1
2
3
Set<KeyType> keySet()
Collection<ValueType> values()
Set<Map.Entry<keyType.ValueType>> entrySet()

TreeSet类和TreeMap类的实现

Java要求TreeSet和TreeMap支持基本的add、remove和contains操作以对数最坏情形时间完成,因此基本的实现方法就是平衡二叉查找树。一般并不适用AVL树,而是使用一些自顶向下的红黑树。

小结

表达式树是更一般结构即所谓分析树的一个小例子,分析树是编译器设计中的核心数据结构。分析树不是二叉树,而是表达式树相对简单的扩充。
查找树在算法实际中是非常重要的,几乎支持所有有用的操作,而其对数平均开销很小。查找树的问题在于其性能严重依赖输入,而输入是随机的。处理这个问题的几种平衡树方案:AVL数、伸展树、B树等。
在实践中,所有平衡树方案的运行时间对于插入和删除操作(除查找稍微快一些)都不如简单二叉树省时,但一般来说是可以接受的,它防止轻易得到最坏情形的输入。
通过将一些元素插入到查找树然后执行一次中序遍历,我们得到的是拍过顺序的元素。

开发者首页 wechat
欢迎您扫一扫上面的微信公众号