Day 15：树(tree)

树是一种抽象资料结构，跟链结串列一样是由节点组成的资料集合。它的形状类似家族树，或者说像向下生长的树，最上面有一个根节点(如下图A)，每个节点都可以有零个或多的子节点。实作上可以像链结串列一样，由每个节点指向子节点的位址。

图片来源：维基百科

二分搜寻树(binary search tree)

我们之前提到，阵列的随机存取利於实现一些演算法，可是不太容易调整长度；链结串列的长度有弹性，但只能线性地存取元素。在一些情况下利用树的结构，可以兼得两者的优点：既可以保持资料顺序、快速搜寻，又容易插入及删除节点。

图片来源：维基百科

二分搜寻树(或称二元搜寻树)，是二元树的结构，也就是每个节点最多只会有两个子节点。二分搜寻树储存资料的方式如上图，每个节点的左边子节点的值会比自己小，右边子节点的值比自己大。

确保这样的结构，就可以进行快速的二分搜寻。

从任一个节点来看，其左半边的所有节点一定都比较小，右半边的一定都比较大(如同二分搜寻中的有序阵列)，所以从根节点开始搜寻，若目标较小则往左，不用再考虑树的右半边，也就是每次的搜寻都可以排除剩下一半的节点，达到O(log n)的搜寻。

值得注意的是，因为树本身的结构也是将所有节点分为左右两半，所以树的高度也会log n。另外，这个结构也体现了二分搜寻中的递回概念，也就是树中任一个节点的左右子结构也各是一个二分搜寻树，也代表我们可以用程序的递回来实作二分搜寻树。

来源：GeeksforGeeks

def search(root,key):
     
    # 基本情况: 树不存在或目标在根结点
    if root is None or root.val == key:
        return root
 
    # 目标大於根结点的值
    if root.val < key:
        return search(root.right,key)
   
    # 目标小於根结点的值
    return search(root.left,key)
    
# This code is contributed by Bhavya Jain

如果是要在树中插入新节点，步骤跟搜寻一样，要从根节点开始找到新节点的位置，所以执行时间也可以达到O(log n)，而且插入新节点只需改变原本节点的指向，不用更动到其他节点。

潜在问题

二分搜寻树当然也不是集所有优点於一身，还是有一些实作上必须注意的事情。其中一个问题可能是空间，因为所有的节点都要有更多的空间来储存参照。

另外一个问题是如果树的结构不平衡，效能也会变差。想像如果根节点的值最小，後来加入的新节点的值越来越大，这样整棵树会只往右边发展。如此一来，树的高度就会变得非常高(n)，搜寻或插入的执行时间也会变成O(n)。我们可以透过一些可以自己平衡结构的二分搜寻树(例如B树)，来避免这个的问题。