前言

树是数据库系统领域最重要的数据结构之一，例如：Mysql中索引结构是B+树，Hbase的底层结构是LSM树（Log Structure Tree）是Hbase底层检索的数据结构，红黑树是Java8里HashMap的底层数据结构，哈弗曼树在编码和压缩领域有着重要的应用。
树在计算机里应用广泛，所以树结构无论是面试、考研，还是工作、自学都会用到。

常见的树介绍

二叉查找树（BST）

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点（因此，插入的时候一定是叶子节点）。
插入有序节点，退化成单支树
    1.查找效率最好O(logn)，最坏O(n)
    2.插入效率和查找效率相同（只插入叶子节点）
    3.删除效率最好O(logn)+O(1)->只有左子树或者右子树
    最差O(logn)+O(logn)->左子树和右子树同时存在

二叉搜索树.JPG

AVL树-自平衡二叉查找树

AVL树本质上是一颗二叉查找树，但是它又具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为平衡二叉树。下面是平衡二叉树和非平衡二叉树对比的例图：

AVL树.png

红黑树

B-树

B+树

LSM树

霍夫曼树

参考文献

常见树介绍
AVL树-自平衡二叉查找树
图解数据结构树之AVL树