DomBro Studio

二叉搜索树

2017/12/29

前言

对于大量输入的数据,链表的线性访问时间太慢了。树是一种简单的数据结构,其大部分操作运行时间平均为 O(log N)。(tree)树在计算机科学中是非常有用的抽象概念。博客要介绍的二叉查找树(brinary scarch tree)也是Java语言中两种类库集合类 TreeSet 和 TreeMap 的实现基础。Are you ready?

开始之前

在正式开始之前,我们应该做一些准备工作。比如树是什么?二叉树是什么?他们的特点又是啥?弄不清这些,那就会陷入一个”我是谁?我在那?我在干什么?”的尴尬境地。

这里说的树当然不是大树的意思,树在计算机科学中就是一种数据结构,将它的抽象结构画出来很想一棵倒过来的树。树的应用也是很广泛,比如你电脑操作系统的文件系统等等balabala。

树的概念

引用书上的话

一棵树是一些节点的集合。这个集合可以是空集;若不是空集,则树由称作根的节点root以及 0个或多个非空的子树 T1,T2,T3,…Tn组成,这些子树的每个根都被来自根 root 的一条有向边所连接。
每一棵子树的根叫做root的儿子(child),而 root 是每一棵子树的父亲(parent)。

这段像绕口令的官方解释,翻译成普通话就是,树是由一个根节点和一堆子树组成的,注意这些子树也是树,也就是说树是可以通过递归来定义的。如下图就是利用递归定义的树

树的定义

一棵树是 N 个节点和 N-1 条边的集合(要不信自己画一个),其中的一个节点叫做根,除了根以外每个节点都会有一条边连接该节点的父亲,所以一棵树就有 N-1 条边!

树的特点

通过下面这张图告诉你树的特点

树的节点

1.每个节点可以有任意个儿子。
2.没有儿子的节点叫他叶子节点(或树叶或终端节点),如 B、F、H、J、K、L、M。
3.具有相同父亲的节点为兄弟(siblings),B、C、D、E、F 就互为兄弟。
4.一棵树中从根到每个节点恰好存在一条路径。
5.对任意节点,该节点的深度(depth)等于从根开始的层次数,如 H 在树的第三层,深度为3,以此类推。
6.由 特点5 ,根的深度为1.
7.树中最大层次成为树的深度或高度。
8.节点有几个子节点,称之为该节点的度,树叶节点的度为 0。如 G 的度为 3。

树的实现

那么如何用 Java 语言来实现一棵树呢?根据概念,树是由节点和边的集合。很容易想到类似链表的写法,定义一个节点类,其中包含对其孩子节点的引用(指针),可是问题来了:不同于链表知道每个节点后面只连接一个next节点,树的儿子结点是任意未知的,怎么破? 由于每个节点的儿子树可以变化很大并且实现不知道,因此在数据结构中建立到各个儿子结点的直接连接是不可行的,因为这样会长生太多浪费的空间
实际上解决方法很简单:利用上面提到的兄弟节点概念,在每个节点中仅包含两个链接,其中一个链接该节点的第一个儿子,另一个链接当前节点的兄弟节点。

1
2
3
4
5
6
7
8
class TreeNode{
//数据域
Object element;
//第一个儿子的引用
TreeNode firstChild;
//兄弟的引用
TreeNode nextSiblings
}

二叉树

二叉树的概念

首先二叉树(binary tree)是一棵树,特点是每个节点都不能有多于两个的儿子。下图是一颗由根和两个子树组成的二叉树,任意子树均可以为空

二叉树

二叉树的性质

以下图为例列举一些二叉树重要的性质

满二叉树

1.在二叉树的第 i (深度+1)层上至多有2i-1个节点 (i>=1)。
2.深度为 k 的二叉树至多有 2k-1个节点(k>=1)。
3.任意一棵二叉树 T,如果其终端节点数(叶子节点)为 n0 ,度为 2 的节点数为 n2 则 n0 = n2 + 1。
4.一棵深度为 k 且有 2k-1 个节点的二叉树叫做满二叉树。
5.二叉树中的所有节点约定 从根节点起,自上而下,从左至右的排列叫做完全二叉树,如下图

完全二叉树

下图则是非完全二叉树

非完全二叉树

6.满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。
7.具有n个节点的完全二叉树的深度为不大于 log2n+1 的整数。

二叉树的实现

因为一个二叉树节点最多有两个子节点,所以可以直接在节点在类中保存直接连接到他们的链,有点类似于双端链表的声明,下面是二叉树节点代码。

1
2
3
4
5
6
7
8
9
class BinaryNode{

Object element;
//左孩子引用
BinaryTree leftChild;
//右孩子引用
BinaryTree rightChild;

}

这里要注意的是,再画链表时习惯使用矩形表示数据域,并且用带有方向的直线连接,虽然二叉树的实现方式有双端链表类似但是习惯上用圆形便是数据,并且连接节点与孩子也不必表明方向,因为树和二叉树并不是线性结构。

二叉搜索树

经过前面的长途跋涉,终于看到了今天的主角,二叉搜索树。经过上面的二叉树小节,已经对二叉树有了一个简要的了解。二叉搜索树从名字的定义显然是一种二叉树!

二叉搜索树概念

按照国际惯例看一下二叉搜索树概念,二叉搜索树的一个重要应用是它们在查找中的使用。使二叉树成为二叉搜索树的性质是,对于二叉树中每个节点X,它的左子树中所有项的值都小于X中的项,而它的右子树中所有项的值都大于X中的项,如下图是以项的类型为整型为例。

二叉搜索树

根据二叉搜索树的概念,在二叉搜索树中每个节点的左子树中所有节点均比该节点项的值小。

二叉搜索树实现

实现原理

由于二叉搜索树要求每个项(节点)都可以进行排序(就是项与项之间可以进行比较),这是他在实现上区别于一般二叉树的地方。如何达到这个效果?你可能才想到了,利用 Comparable 这个接口。我的原则是利用 泛型+Comparable接口:泛型 AnyType 作为 每个节点数据项的类型,同时也需要是 Comparable 的子类型(即Comparable的实现),这样项与项之间就可以通过 compareTo 进行比较。所以代码的大体框架是下面这个样子滴

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>>{

//嵌套的节点类
private static class BinaryNode<AnyType>{
//见嵌套节点类小节
}

//根节点引用
private BinaryNode<AnyType> root;
//令二叉搜索树为空
public void makeEmpty(){//见二叉搜索树的初始化与置空小节};
//判断二叉树是否为空
public boolean isEmpty(){//见二叉搜索树的初始化与置空小节};
//寻找二叉树中最小值
public AnyType findMin(){//见最大值与最小值小节};
//寻找二叉树中最大值
public AnyType findMax(){//见最大值与最小值小节};
//插入节点
public void insert(AnyType x){//见插入新数据小节}
//删除节点
public void remove(AnyType x){//见删除操作小节}
//判断树中是否包含某项
public boolean contains(AnyType x){//见查找是否包含某项小节}
//打印树
public void printTree(){//见树的遍历小节}
}

嵌套节点类

由于二叉搜索树同样是二叉树,每个节点拥有数据项和左右两个儿子,所以节点类的代码是很简单的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static class BinaryNode<AnyType>{

//数据项
AnyType elements;
//左孩子节点
BinaryNode<AnyType> left;
//右孩子节点
BinaryNode<AnyType> right;

BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt){
elements = theElement;
left = lt;
right = rt;
}

BinaryNode(AnyType theElement){
this(theElement,null,null);
}
}

二叉搜索树的初始化与置空

树结构是从根节点开始向下插入节点,一棵树只有一个根,所以任何一棵树的初始化与置空操作都是判断根节点是否为空。这就好像如果一个家族,根本没有祖先(生育他们的人),那下面这些孩子是不可能存在的。

1
2
3
4
5
6
7
8
9
10
11
12
13
//利用构造方法初始化
public BinarySearchTree(){
root = null;
}

//令二叉搜索树为空
public void makeEmpty(){
root = null;
}
//判断二叉树是否为空
public boolean isEmpty(){
return root == null;
}

最大值与最小值

如果不是二叉搜索树,这个功能实现起来会异常麻烦并且毫无意义,而二叉搜索树作为存在大小规律的二叉树,最小值节点一定在根节点左子树中最左面的节点,最大值一定在根节点右子树中最右边的节点,掌握这个那就很好办了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//寻找最大最小一定是从根节点开始寻找

public AnyType findMin(){
if (isEmpty())
throw new BufferUnderflowException();
return findMin(root).elements;
}

public AnyType findMax(){
if (isEmpty())
throw new BufferUnderflowException();
return findMax(root).elements;
}

private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t){
if (t != null){
//当左子树中的左节点的左节点为空那一定是最小的
while (t.left != null){
t = t.left;
}
}
return t;
}

private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t){
if (t != null){
//当右树中的左节点的右节点为空那一定是最大的
while (t.right != null){
t = t.right;
}
}
return t;
}

查找是否包含某项

由于二叉树并不是线性的表结构,所以这里所说的查找并不会把位置说出来,当输入一个数据项时会判断树中是否含有该数据。实现起来也很简单,从根节点比较传入的数据项,如果相等则找到该节点,如果传入数据较小则根节点一定在根节点的左子树中,以此类推,聪明的你一定会想到使用递归了吧~~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//从根节点判断该二叉搜索树是否有节点的数据项与传入节点相同
public boolean contains(AnyType x){
return contains(x,root);
}

private boolean contains(AnyType x, BinaryNode<AnyType> t){
if (t == null)
return false;
int compareResult = x.compareTo(t.elements);
//如果传入数据比当前节点的数据小,则去当前节点的左孩子查找
if (compareResult < 0){
return contains(x,t.left);
//如果传入数据比当前节点的数据大,则去当前节点的右孩子查找
}else if (compareResult > 0){
return contains(x,t.right);
}else
return true;
}

插入新数据

二叉搜索树的插入实际上是最重要的了,原因就是我们上面所说的查找最小最大、查看是否包含、以及下面要提到的删除操作,都是基于插入操作正确插入的条件下,原因很简单上述操作我们会比较树中节点的大小,而这些节点一定要按照规则插入才行!而这个规则实际上就是二叉搜索树的定义呀,即每个节点的做儿子中的值比该节点值小,右儿子中的值比该节点值大!这里咱们约定一下,当插入树有已有数据时,不做插入即树中的个个节点的数据域是不同的。依然使用递归去实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//从根节点开始插入
public void insert(AnyType x){
root = insert(x,root);
}

private BinaryNode<AnyType> insert(AnyType x,BinaryNode<AnyType> t){

if (t == null){
return new BinaryNode<>(x,null,null);
}

int compareResult = x.compareTo(t.elements);
//如果插入项比当前节点的数据域小,则递归调用插入该节点的左儿子节点
if (compareResult < 0){
t.left = insert(x,t.left);
//如果插入项比当前节点的数据域大,则递归调用插入该节点的右儿子节点
}else if (compareResult > 0 )
t.right = insert(x,t.right);
else
;
return t;
}

删除操作

删除操作可以说是整个二叉搜索树最复杂的地方了。原因是在我们删除一个节点后,我们还要保持删除后的二叉搜索树依然是一个二叉搜索树,有点像绕口令哈~~为了在删除后保持原状分为以下三种情况:
1.被删除的节点没有儿子节点,直接删除(变为null)

2.被删除的节点有一个儿子节点,用该儿子节点替代该节点位置

3.被删除节点有两个儿子节点,这是最麻烦的情况,咋办?别急有一个技巧,这种情况下我们只需要找到被删除节点右子树中最小节点,并将其数据项的值赋给要删除节点,再删除该最小节点即可。为什么?想一下被删除节点的右子树中所有节点一定都比被删除节点左子树的大,而右子树中最小数据项我们可以轻易的获取(通过 上面的findMin方法)!

下面是代码,依然使用递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public void remove(AnyType x){
remove(x,root);
}

//删除节点
private BinaryNode<AnyType> remove(AnyType x,BinaryNode<AnyType> t){

if (t == null){
return t;
}

int compareResult = x.compareTo(t.elements);

if ( compareResult < 0){
remove(x,t.left);
}else if( compareResult > 0){
t.right = remove(x,t.right);
//要删除的节点有两个孩子
}else if ( t.left != null && t.right != null){
//使其右子树中最小的节点替代
t.elements = findMin(t.right).elements;
//删除该最小节点
t.right = remove(t.elements,t.right);
//要删除的节点只有一个孩子,则由该孩子替代
}else {
t = (t.left != null) ? t.left : t.right;
}
return t;
}

树的遍历

树的遍历有三种方法:
1.中序遍历,顺序为 左 -> 根 -> 右,以本节开头二叉搜索树图片为例,该树中序遍历顺序为 1 -> 2 -> 3 -> 4 -> 6 -> 8
2.前序遍历,顺序为 根 -> 左 -> 右,以本节开头二叉搜索树图片为例,该树中序遍历顺序为 6 -> 2 -> 1 -> 4 -> 3 -> 8
3.后序遍历,顺序为 左 -> 右 -> 根,以本节开头二叉搜索树图片为例,该树后序遍历顺序为 1 -> 3 -> 4 -> 2 -> 8 -> 6

我使用的是中序遍历方法,依然使用递归的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//打印树
public void printTree(){
printTree(root);
}


//中序遍历
private void printTree(BinaryNode<AnyType> t){
if (t != null && t.elements != null){
printTree(t.left);
System.out.println(t.elements);
printTree(t.right );
}
}

小结

你可能会发现,在二叉树的实现中用到了好多好多递归呀,插入、查找、删除、甚至遍历,没有错这就是二叉搜索树、树的特点,原因很简单我们将每个节点个和该节点的子树拿出来又是一颗树!这给了我们使用递归去定义二叉搜索树的机会,帮助我们更好的去理解树这种数据结构!完整代码见 github

二叉搜索树的效率

上一节提到的二叉搜索树的增(insert)、查(contains)、删除(remove)操作的平均时间复杂度均为 O(log N)。

CATALOG
  1. 1. 前言
  2. 2. 开始之前
    1. 2.1.
      1. 2.1.1. 树的概念
      2. 2.1.2. 树的特点
      3. 2.1.3. 树的实现
    2. 2.2. 二叉树
      1. 2.2.1. 二叉树的概念
      2. 2.2.2. 二叉树的性质
      3. 2.2.3. 二叉树的实现
  3. 3. 二叉搜索树
    1. 3.1. 二叉搜索树概念
    2. 3.2. 二叉搜索树实现
      1. 3.2.1. 实现原理
      2. 3.2.2. 嵌套节点类
      3. 3.2.3. 二叉搜索树的初始化与置空
      4. 3.2.4. 最大值与最小值
      5. 3.2.5. 查找是否包含某项
      6. 3.2.6. 插入新数据
      7. 3.2.7. 删除操作
      8. 3.2.8. 树的遍历
      9. 3.2.9. 小结
    3. 3.3. 二叉搜索树的效率