荔枝大人V
我从大学开始了解二叉树，中间间隔着又学了几次，觉得二叉树这种数据结构还是挺神奇的！
先来看下二叉树中涉及到的术语:
①，结点:存储着一个数据，并指向其他的结点。
②，子结点:结点的子树的根结点。
③，结点层:根为第一层，根的子结点为第二层，以此类推后面的层数。
④，深度:最大的结点层数为树的深度！
⑤，叶结点:没有子结点的结点（也叫终端结点）
其他诸如兄弟节点，双亲节点，祖先结点，路径，路径长度的概念并不直观，参考树结构了解即可！
什么是二叉树呢？二叉树是每个结点最多有两个子数存在的树形结构，是一个有限的结点的集合，每一层的结点有左右之分！
二叉树有两种存储方式:
1，顺序存储:可以通过简单的数学公式获取到后代结点或者祖先结点的位置，但是如果不是完全二叉树将会极大的浪费存储空间！
2，链式存储:像存链表一样将前后结点进行结合，虽然增加删除结点只需要更改原来的前后结点的指向，但是查找效率为O(N)，很不方便，适用于非完全二叉树！
如果，一棵二叉树再插入时是有序的，二叉树结构变为右单枝树结构或者左单枝树结构，则二叉树O(logN)的性能将会蜕变为链表O(N)，性能下降十分严重，这时候的树被称为不平衡的树！
那么什么是平衡的树(平衡树也称为AVL)呢？树的左右子树都为平衡树，而两边高度不超过1的树！
上文提到，非平衡二叉树的查找性能变为O(N)，而构建平衡树就是为了让树结构的查找效率始终在O(logN)级别！
链表到平衡二叉树之间的转变，最近的例子应该就是JAVA8中的hashMap了，原来的链表存储同一个key下面的值会出现大量冲突的情景，查找性能下降很多，而加入了红黑树后，hashMap会在链表个数超过阈值的时候，自动转变为红黑树进行存储数据，大大提升大量冲突时候的查找性能！
b＋－树在数据库索引中也得到了大量的应用，可以说平衡二叉树是作为数据结构与算法当中的必修课程，也是程序猿算法进阶的良方，篇幅有限，关于树的概念就说到这，后面会分享很多算法与数据结构的知识，更多的技术分享，敬请关注。。
