BST

为什么Binary Tree

结合了有序数组（查找）和链表（插入和删除）的优点

1）有序数组

二分查找：O(logN)-----快

插入删除：某部分元素需要移位O(N)-----慢

2）链表

插入删除：只需改变一些引用的值O(1)-----快

查找：需要根据链接一个个遍历O(N)-----慢

树

节点Node：数据结构中存储的数据，OOL中的对象实例

边Edge：对程序而言，从一个节点到另一个节点的方式（非常快），OOL中的reference或者pointer

根Root：树的顶层总是只有一个节点，然后由边依次联系到其他节点。根到其他人任意节点都必须有且只有一个路径（即树中无环）

叶节点leaf node：没有子节点的节点

深度Depth：根的深度是0

层Level：根的level是1

高度height：The height of a node is the number of edges from the node to the deepest leaf. The height of a tree is a height of the root.

二叉树：每个节点最多有两个子节点

1)complete BT: 每一level都满，除了最后一level，数组实现中左到右的顺序填

2)full BT：每个节点要么没有子节点，要么有两个子节点

3)perfect BT: 前两种的组合，完美！节点数：2^k - 1 (k is num of level)

二叉树中的一类：BST

key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in right sub-tree

注意：根据定义的不同，BST有时候也可以有duplicate value，但简单起见一般是没有的

BST代码实现

1)树class

数据：root node

方法：查找，插入，删除......

2)节点class

数据：要存储的内容，左child，右child

3)Find

key与当前考虑节点值比较：

if == : 找到

else if > : 当前考虑节点移到右child，

else < : 当前考虑节点移到左child

if 当前考虑节点 == null：找不到

效率：因此查找节点的用时取决于节点所在的层数，因此是O(logN)

4)Insert

插入节点首先要找到该插入的地方，相等于是需要查找一个不存在的节点

效率：O(logN)

5)中序遍历inorder traversal

只包含3步：

1）Traverse the left subtree by recursively calling the in-order function.调用自身遍历左子树

2）Display the data part of the root (or current node).访问（获取并处理）当前节点

3）Traverse the right subtree by recursively calling the in-order function.调用自身遍历右子树

private void inOrder(node currentRoot) {
    //base case
    if(currentRoot == null) return;
    //recursive case
    else {
        inOrder(currentRoot.leftChild);
        System.out.println(currentRoot.data);
        inOrder(currentRoot.rightChild);
    }
}

因为访问当前节点是第二步，即中步，所以叫中序。同理得到前序与后序。

6）Find Min/Max

Min:一直往左走直到找到没有左子节点的节点 Max：一直往右走知道找到没有右子节点的节点

7）Delete

比较复杂，一般不用

Inorder Successor

思想：找比当前节点值大的节点集中值最小的

BST的效率

无论是插入或者删除，都是先得使用查找，然后此基础上进行常数操作

关键：层数决定了计算复杂度，即O(logN)---相当快

注意：O(logN)的前提是BST是一颗blanced tree，如果是一颗unblanced的tree，那么层数会大于logN，极端unblanced的情况甚至可以达到O(N)

BST的另一种存在形式：数组

数组中存储的节点顺序是：由上到下，由左到右。节点中无数据，数组中存null

当前节点index，则：

左子：2*index + 1

右子：2*index + 2

父节点：(index-1)/2

Drawback: 浪费存储空间

二叉树的其他类：Huffman Tree

根据字符的二进制编码就是树中的路径:0向左，1向右，字符在叶节点

BST

BST