二叉树

简介

如图所示，与堆相比，二叉树要更复杂。堆是一个数组，我们可以把它简单地可视化为一颗树，而二叉树和堆不同，它实际上是一颗有指针的树。

本次主要介绍二叉搜索树，二叉搜索树是指一颗空树或者具有下列性质的二叉树：

若任意结点的左子树不为空，则左子树上所有结点的值均小于它的根结点的值。
若任意结点的右子树不为空，则右子树上所有结点的值均大于它的根结点的值。
任意结点的左、右子树也分别为二叉搜索树。
没有键值相等的结点。

如下图所示，就是一颗二叉搜索树: 你可以看到根结点30的左子树的值都小于它，右子树的值都大于它

属性

深度: 对于任意结点n，n的深度为从根到n的唯一路径长，根的深度为0。
高度: 对于任意结点n，n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0。

图示如下(高度height，深度depth):

            d0h3
            / \
           /   \
         d1h1  d1h2
         /\      \
        /  \      \
      d2h0 d2h0  d2h1
                   /
                  /
                d3h0

某个结点的高度等于它左右子树高度的最大值+1

操作

这里先声明数的高度为h。并且在每个元素的结点加入一个表示子树大小的属性（在括号中表示）。

插入

如果我想插入一个元素18到下面的二叉搜索树，并且同时更新子树大小属性，那么流程如下

          30(5)         先将这个元素与根元素比较，18比根元素30小，所以把它插入左子树
          / \               并将元素30的子树大小属性5加上1
         /   \
       17(3)  40(1)    再将这个元素与17比较，18比17大，所以把它插入右子树
       /\                   并将元素17的子树大小属性3加上1
      /  \
   14(1) 20(1)         将这个元素与20比较，18比20小，所以把它插入左子树
                             并将元素20的子树大小属性1加上1，新插入的元素18子树大小为1

从上面的例子可以看出，对其进行插入操作的时间复杂度为O(h)，与树的高度有关。

查找最大与最小值

如果你想找到最小值，只需沿着树的左侧一直找下去，到达叶子结点即为最小值；最大值同理则为沿着右侧一直找下去，根据二叉搜索树的性质不难看出这一点。

对其进行查找最大与最小值操作的时间复杂度为O(h)，与树的高度有关。

查找相邻的较大较小数

对二叉搜索树进行中序遍历即可得到从小到大排序过的序列。

查找小于等于某个数的元素有多少个

遍历整个树查找你想要查找的元素
随着查找的路径逐个比较，若小于等于比较元素则加一
并且累加左子树的子树大小

例如我想查找小于等于40的元素有多少

             30(6)         先将这个元素与30比较，40大于30，(+1)
             / \            然后再累加左子树17的子树大小，(+2)，然后看右子树
            /   \
        17(2)  40(3)    再将这个元素与结点40比较，相等，(+1)
         /      / \       然后再累加左子树38的子树大小，(+1)，查找结束
        /      /   \
    14(1)   38(1) 44(1)

    将上面的数字累加起来，+1+2+1+1，最终得到5，所以小于等于40的元素有5个。

时间复杂度为O(h)，与树的高度有关。

小结

与堆相比，二叉搜索树可以找到相邻的较大较小数，这是堆所不具备的能力。
从上面的操作我们发现时间复杂度与树的高度有关，所以我们要尽量减少树的高度，使之成为平衡树。

平衡树

简介

平衡树是计算机科学中的一类改进的二叉搜索树。一般的二叉搜索树的查询复杂度是根目标结点到树根的距离(即深度)有关，因此当结点的深度普遍较大时，查询的均摊复杂度会上升，为了更高效的查询，平衡树应运而生了。

基本操作

几乎所有平衡树的操作都基于树旋转操作，通过旋转操作可以使得树趋于平衡。对一颗查找树(search tree)进行查询、新增、删除等动作，所花的时间与树的高度h成比例，并不与树的容量n成比例。如果可以让树维持矮矮胖胖的好身材，也就是让h维持在O(log n)左右，完成上述工作就很省时间。能够一直维持好身材，不因新增删除而长歪的搜寻树，叫做平衡树(balanced search tree)。

旋转(Rotate) —— 不破坏左小右大特性的小手术

各种平衡树

AVL树
红黑树
加权平衡树(WBT)
Treap(Tree+Heap)

这些均可以使查找树的高度为O(log n)

tags: #数据结构 #排序 #二叉搜索树

BlacAmDK's Blog