数据结构-二叉查找树

发表于 分类于 Disqus：
二叉查找树

树(Tree)

树(Tree)是由多个节点(Node)的集合组成，每个节点又有多个与其关联的子节点(ChildNode)。子节点就是处于节点下的节点，而父节点就是处于节点上的节点。树的根(root)指一个没有父节点的单独节点。

特点

  1. 只有一个根节点。
  2. 除了根节点，所有的节点都有且只有一个父节点。
  3. 无环。将任意一个节点作为起始节点，都不存在任何回到该节点的路径。

术语

  1. 根(Root)：树种最顶端的节点，根没有父节点。
  2. 子节点(Child)：节点所拥有子树的根节点称为该节点的子节点。
  3. 父节点(Parent)：如果节点拥有子节点，则该节点为子节点的父节点。
  4. 兄弟节点(Sibling)：与节点拥有相同父节点的节点。
  5. 子孙节点(Descendant)：节点向下路径上可达的点。
  6. 叶节点(Leaf)：没有子节点的节点。
  7. 内节点(Internal Node)：至少有一个子节点的节点。
  8. 度(Degree)：节点拥有子树的数量。
  9. 边(Edge)：两个节点中间的链接。
  10. 路径(Path)：从节点到子孙节点过程中的边和节点所组成的序列。
  11. 层级(Level)：根为Level0层，根的子节点为Level1层，以此类推。
  12. 高度(Height)/深度(Depth)：树中层的数量。比如只有Level0,Level1，Level2，则高度为3。

二叉树(Binary Tree)

二叉树是一种特殊的树类型，每个节点最多只能有两个子节点。这两个子节点分别称为当前节点的左孩子(left child)和右孩子(right child)。


上图中，二叉树(a)包含8个节点，其中节点1是它的根节点。节点1的左孩子为节点2，右孩子为节点3。并没有要求一个节点同时具备左孩子与右孩子(如二叉树(a)的节点4只有右孩子)，节点也可以没有孩子(如二叉树(b)的4,5,6,7节点都没有孩子)。没有孩子的节点称为叶节点，有孩子的节点称为内节点。如，二叉树(a)中6,8为叶节点，节点1,2,3,4,5,7为内节点。

完全二叉树(Complete Binary Tree)

深度为h，有n个节点的二叉树，当且仅当每一个节点都与深度为h的满二叉树序号为1至n的节点对应时，称为完全二叉树。

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
一个完整的二叉树是一个二进制树，其中除了最后一个之外的每个级别都被完全填充，所有的节点尽可能地都是最左边的。

满二叉树(Full Binary Tree)

一颗深度为h，且有 2^h - 1 个节点称为满二叉树。

A full binary tree is a tree in which every node other than the leaves has two children.
一个满二叉树是除叶子节点外每个节点都有两个孩子的一棵树。

type 完全二叉树 满二叉树
总节点树k 2^(h-1) <= k < 2^h -1 k = 2^h -1
树高h h = log<2>k + 1 h = log<2>(k+1)

数组是将元素连续的排列在内存当中，而二叉树却不是采用连续的内存存放。实际上BinaryTree类的实例仅包含根节点(Root Node)实例的引用，而根节点实例又分别指向它的左右孩子节点实例。关键的不同之处在于，组成二叉树的节点对象实例可以分散到堆中的任意位置，没必要像数组那样连续存放。

若要访问二叉树中的某个节点，通常需要逐个遍历二叉树中的节点，来定位那个节点。它不像数组那样能对指定的节点进行直接访问。所以查找二叉树的渐进时间是线性的O(n)，在最坏的情况下需要查找树中所有的节点。也就是说，随着节点数的增加，查找任一节点的步骤数量也将相应的增加。

如果一个二叉树的查找时间是线性的，定位时间也是线性的，那相比数组来说，优势在哪里呢？毕竟数组的查找时间虽然是线性的，但是定位时间却是O(1)级的。的确是这样的，通常来说，普通二叉树却是不能提供比数组更好的性能。然而，如果我们按照一定的规则来组织排列二叉树中的元素时，就可以很大的改善查询时间和定位时间。

二叉查找树(BST)

二叉查找树(BST：Binary Search Tree)是一种特殊的二叉树，它改善了二叉树节点查找的效率。

特点

对于任意一个节点n，

  • 其左子树(left subtree) 下的每个后代节点(descendant node)的值都小于节点n的值。
  • 其右子树(right subtree) 下的每个后代节点的值都大于节点n的值。

图(b)是一个二叉查找树，它符合二叉查找树的性质。而图(a)不是一个二叉查找树，因为节点10的右孩子8小于节点10，却出现在了节点10的右子树中。

从二叉查找树的特点可以看出，BST各节点存储的数据必须能够与其他的节点进行比较。给定任意两个节点，BST必须能够判断这两个节点的值是小于、大于还是等于。

查找

假设我们要查找BST中的某一个节点。例如要查找上图中二叉查找树(b)中值为10的节点。我们从根开始查找，可以看到根节点值为7，我们要查找节点值为10，若节点值为10存在，必然存在于右子树，跳到节点11继续查找。此时，节点值10小于节点11，则节点10必然存在于节点11的左子树。再查找节点11的左孩子，此时我们已经找到了目标节点10，定位于此。

总结来说，我们使用查找算法的过程如下：
假设我们要查找节点n，从BST的根节点开始。算法不断的比较节点值大小知道找到该节点，或者判定不存在。每一步我们都要处理两个节点：树中的一个节点，称为节点c，和要查找的节点n，然后比较c和n的值。开始时，节点c为BST的根节点。然后执行以下步骤：

  1. 若c值为空，则n不在BST中。
  2. 比较c和n的值。
  3. 若值相同，则找到了指定的节点n。
  4. 若n的值小于c，如果n存在，必然在c的左子树中。回到第1步，将c的左孩子作为c。
  5. 若n的值大于c，如果n存在，必然在c的右子树中。回到第1步，将c的右孩子作为c。

通过BST查找节点，理想情况下我们需要检查的节点数可以减半。如下图中的BST树，包含了15个节点。从根节点开始执行查找算法，第一次比较决定我们是移向左子树还是右子树。对于任意一种情况，一旦执行这一步，我们需要访问的节点数就减少了一半，从15降到了7，同样下一步访问的节点也减少了一半，从7降到了3，以此类推。

根据这一特点，查找算法的时间复杂度应该是 O(log<2>n)，简写为O(lgn)。即，如果节点数量增加时，查找时间只是缓慢地增加到log<2>n。举例来说，查找一个具有1000个元素的数组，需要查询1000个元素，而查找一个具有1000个元素的BST树，仅仅查询不到10个节点(log<2>1024 = 10)。

实际上，对于BST查找算法来说，十分依赖树中节点的拓扑结构。下图描绘了一个节点插入顺序为20,50,90,150,175,200的BST树。这些节点是按照升序被插入的。也就是说，它的拓扑结构其实就是将节点排序在一条线上，而不是以扇形结构散开，所以查找时间也为O(n)。

当BST树中节点以扇形结构散开时，对它的插入、删除、和查找操作最优的情况下可以达到亚线性的运行时间O(log<2>n)，最坏的情况，就是上图这样，运行时间退减到线性时间O(n)，基本和数组类似了。

因此，BST算法查找时间依赖于树的拓扑结构。最佳情况是O(log<2>n),而最坏情况是O(n)。

插入

当向树中插入一个新节点时，该节点将总是作为叶子节点。最困难的地方是如何找到该节点的父节点。类似于查找算法中的描述，我们将这个新的节点称为节点n，而遍历的当前节点称为节点c。开始时，节点c为BST的根节点。定位节点n的父节点的步骤如下：

  1. 若节点c为空，则节点c的父节点将作为节点n的父节点。若节点n的值小于该父节点的值，则节点n将作为该父节点的左孩子；否则节点n将作为该节点的右孩子。
  2. 比较节点c和节点n的值。
  3. 若节点c的值和节点n的值相等，则说明用户在试图插入一个重复的节点。解决办法可以是直接丢掉节点n，或者可以抛出异常。
  4. 若节点c的值小于节点n的值，则说明节点n一定在节点c的左子树。则将父节点设置为节点c，并将节点n设置为节点c的左孩子，然后返回第1步。
  5. 若节点c的值大于节点n的值，则说明节点n一定在节点c的右子树。则将父节点设置为节点c，并将节点n设置为节点c的右孩子，然后返回第1步。

当找到合适的节点，该算法结束。新节点被放入BST中成为某一父节点合适的孩子节点。BST的插入算法的复杂度与查找算法的复杂度是一样的：最佳为O(log<2>n)，最坏情况为O(n)。因为他们的对节点的查找定位策略是相同的。

删除

从BST中删除节点比插入节点难度更大。因为删除一个非叶子节点，就必须选择其他节点来填补因删除节点所造成的树的断裂。若不选择节点来填补这个裂缝，那么就违背了BST的性质要求。

删除节点算法的第一步是定位要被删除的节点，可以使用前面的查找算法，因此运行时间为O(log<2>n)。接着应该选择合适的节点来代替删除节点的位置。

  1. 如果删除的节点没有右孩子，那么就选择它的左孩子来替代原来的节点。因此左子树的值要么都大于，要么都小于被删除节点的父节点的值，这取决于被删除节点是左孩子还是右孩子。二叉查找树的特点保证了被删除节点的左子树必然符合二叉查找树的特点。

  2. 若删除的节点的右孩子没有左孩子，那么这个右孩子被用来替代被删除节点。因为被删除节点的右孩子都大于被删除节点左子树的所有节点，同时也大于或小于被删除节点的父节点，这同样取决于被删除节点是左孩子还是右孩子。因此，用右孩子来替换被删除节点，符合二叉查找树的性质。

  3. 若被删除节点的右孩子有左孩子，就需要用被删除节点右孩子的左子树中的最下面的节点来替换它，就是说，我们用被删除节点的右子树中最小值的节点来替换。

我们知道，在 BST 中，最小值的节点总是在最左边，最大值的节点总是在最右边。因此替换被删除节点右子树中最小的一个节点，就保证了该节点一定大于被删除节点左子树的所有节点。同时，也保证它替代了被删除节点的位置后，它的右子树的所有节点值都大于它。因此这种选择策略符合二叉查找树的性质。

和查找、插入算法类似，删除算法的运行时间也与 BST 的拓扑结构有关，最佳情况是 O(log­2n)，而最坏情况是 O(n)。

遍历节点

对于线性的连续的数组来说，遍历数组采用的是单向的迭代法，从第一个元素开始，依次向后迭代每个元素。
BST有三种常用的遍历方式：

  1. 前序遍历
  2. 中序遍历
  3. 后序遍历

都是从根节点开始，然后访问其子节点。区别在于遍历时，访问节点本身和其子节点的顺序不同。

  1. 前序遍历
    前序遍历从当前节点(节点c)开始访问，然后访问其左孩子，再访问右孩子。开始时，节点c为BST的根节点。算法如下：

    • 访问节点c；
    • 对节点c的左孩子重复第1步；
    • 对节点c的右孩子重复第1步。

    上图遍历结果为：90,50,20,5,25,75,66,80,150,95,92,111,175,166,200。

  2. 中序遍历
    中序遍历时从当前节点(节点c)的左孩子开始访问，再访问当前节点，最后是其右节点。开始时，节点c是BST的根节点。算法如下：

    • 访问节点c的左孩子；
    • 对节点c重复第1步；
    • 对节点c的右孩子重复第1步。

    上图遍历结果为：5,20,25,50,66,75,80,90,92,95,111,150,166,175,200。

  3. 后续遍历
    后续遍历首先从当前节点(节点c)的左孩子开始访问，然后是右孩子，最后才是当前节点本身。开始时，节点c为BST的根节点。算法如下：

    • 访问节点c的左孩子；
    • 对节点c的右孩子重复第1步；
    • 对节点c重复第1步；

    上图遍历结果为：5,25,20,66,80,75,50,92,111,95,166,200,175,150,90.

总结来说，BST的遍历都是从根节点开始，然后访问其子节点，对于先中后序的遍历，如下图所示：

Java实现BST

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
package com.solverpeng.tree;


/**
 * @author solverpeng
 */
public class BinarySearchTree {
    /**
     * 根节点
     */
    private static TreeNode root;

    public BinarySearchTree() {
        root = null;
    }

    /**
     * 查找
     * 1.从root节点开始
     * 2.比当前节点值小，则找其左节点
     * 3.比当前节点值大，则找其右节点
     * 4.与当前节点值相等，查找返回true
     * 5.查找完毕未找到
     */
    public TreeNode search(int key) {
        TreeNode current = root;
        while (current != null && key != current.value) {
            if (key < current.value) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return current;
    }

    /**
     * 插入
     * 1.从root节点开始
     * 2.若root节点为空，插入值即为root
     * 循环：
     * 3.若当前节点值大于插入值，找左节点
     * 4.若当前节点值小于插入值，找右节点
     */
    public TreeNode insert(int key) {
        // 新增节点
        TreeNode newTreeNode = new TreeNode(key);
        // 当前节点
        TreeNode current = root;
        // 父级节点
        TreeNode parent = null;

        // 若根节点为空
        if (current == null) {
            root = newTreeNode;
            return newTreeNode;
        }

        while (true) {
            parent = current;
            if (key < current.value) {
                current = current.left;
                if (current == null) {
                    parent.left = newTreeNode;
                    return newTreeNode;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = newTreeNode;
                    return newTreeNode;
                }
            }
        }

    }

    /**
     * 删除节点
     * 1.找到删除的节点
     * 2.若删除节点的左节点为空，右节点也为空
     * 3.若删除节点只有一个子节点 左节点或右节点
     * 4.若删除节点左右子节点都不为空
     */
    public TreeNode delete(int key) {
        TreeNode parent = root;
        TreeNode current = root;

        boolean isLeftChild = false;

        // 找到删除节点 及 是否存在左子树
        while (current.value != key) {
            parent = current;
            if (current.value > key) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }

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

        // 如果删除节点做节点为空，右节点也为空
        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            }
            // 如果是左节点
            if (isLeftChild) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }
        // 如果删除节点只有一个子节点 右节点 或者 左节点
        else if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else if (isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        } else if (current.right == null) {
            if (current == root) {
                root = current.left;
            } else if (isLeftChild) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }
        }
        // 如果删除节点左右子节点都不为空
        else {
            // 找到删除节点的后继者
            TreeNode successor = getDeleteSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return current;
    }

    /**
     * 获取删除节点的后继者
     * 删除节点的后继者是在其右节点树中最小的节点
     */
    private TreeNode getDeleteSuccessor(TreeNode deleteNode) {
        // 后继者
        TreeNode successor = null;
        TreeNode successorParent = null;
        TreeNode current = deleteNode.right;

        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
        }

        // 检查后继者是否有右节点树
        // 如果它有右节点树，则替换后继者位置，加入到后继者父亲节点的左节点.
        if (successor != deleteNode.right) {
            successorParent.left = successor.right;
            successor.right = deleteNode.right;
        }
        return successor;
    }

    /**
     * 先序遍历
     */
    public void firstOrder(TreeNode root) {
        if (root != null) {
            System.out.println("value = " + root.value + " - >");
            firstOrder(root.left);
            firstOrder(root.right);
        }
    }

    /**
     * 中序遍历
     */
    public void inOrder(TreeNode root) {
        if (root != null) {
            inOrder(root.left);
            System.out.println("value = " + root.value + " - >");
            inOrder(root.right);
        }
    }

    /**
     * 后序遍历
     */
    public void postOrder(TreeNode root) {
        if (root != null) {
            postOrder(root.left);
            postOrder(root.right);
            System.out.println("value = " + root.value + " - >");
        }
    }
}

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

参考

二叉查找树
图解：二叉搜索树算法（BST）

0%