什么是树

上一篇文章已经介绍过了数组和链表，下面我们看看两者查找和操作的时间开销

可以看到，已有的数据结构不能很好的平衡静态操作和动态操作的时间开销。所以引入了树的概念

二叉排序树(也叫二叉搜索树，BST，Binary Search Tree)

大于根节点的放在根节点的右子树上，小于根节点的放在根节点的左子树上(如果等于根节点，则可视情况而定)。

如果写程序的话，可以采用递归的方式，而且由于不存在重叠子问题的情况，因此递归的性能已经足够好(不考虑栈溢出的情况)。

二叉排序树在通常情况下可以达到O(lgN)的静态、动态操作的时间复杂度。

时间复杂度 O(1)

存在一种特殊情况，即输入的数据本身就是有序的，这时二叉排序树退化成数组。

平衡二叉树(Self-balancing binary search tree）（AVL）

为了消除二叉排序树对于输入敏感的特性，引入平衡二叉树

保证每个节点左子树和右子树的高度差小于等于1就可以了

左子树深度 - 右子树深度 = 平衡因子（小于等于1）

B树&B+树

b树（balance tree）和b+树应用在数据库索引

数据库索引是存储在磁盘上的，当数据量大时，就不能把整个索引全部加载到内存了，只能逐一加载每一个磁盘页（对应索引树的节点）。所以我们要减少IO次数，对于树来说，IO次数就是树的高度，而“矮胖”就是b树的特征之一，它的每个节点最多包含m个孩子，m称为b树的阶，m的大小取决于磁盘页的大小。

b+树，是b树的一种变体，查询性能更好。有n棵子树的非叶子结点中含有n个关键字（b树是n-1个），这些关键字不保存数据，只用来索引，所有数据都保存在叶子节点（b树是每个关键字都保存数据）

红黑树（R-B Tree）

红黑树可以看做是二叉搜索树和AVL树的一个折中，可以尽量维持树的平衡，又不用话过多的时间来维持数据结构的性质。

每个结点要么是红的要么是黑的。

根结点是黑的。

每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。

如果一个结点是红的，那么它的两个儿子都是黑的。

对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

应用

广泛用在C++的STL中。map和set都是用红黑树实现的。

著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块。

epoll在内核中的实现，用红黑树管理事件块

nginx中，用红黑树管理timer等

Java的TreeMap实现