数据结构之Tree-向日葵屋

数据结构之Tree

今天简单梳理一下数结构，树这种数据结构中常用的是二叉查找树，Avl平衡树，展开树，B树（我的理解是常用频率依次递减，红黑树目前还没有接触到，后续补充更新）。
二叉树：binary tree，即每个节点至多有两个儿子（子树），声明如下图，即由该节点的element信息加上两个到其他节点的引用（left and right）组成的结构。
class BinaryNode { 
    Object     element;
    BinaryNode left;
    BinaryNode right;
}

二叉查找树
好了，以上是二叉树的结构，那么查找呢？这里给上边的node生成tree制定一个规则：对于树中每个节点X，它的左子树中所有项的值都小于X的值；右子树中所有项的值都大于X的值。好了，这样定义的树便是二叉查找树。

之所以叫二叉查找树，因为适合查找，当你需要一种可以将你的一组数据进行排序储存的话，用它。

Avl树
Avl个人觉的适合查询和插入操作，Avl树即平衡树，它能够保证整个树不至于某些分支深度太大，规则是：树中每个节点的左右子树的高度最多差1的二叉查找树。当根据二叉查找的规则将新节点插入树中，发生左右高度大于1的情况，则进行树结构的调整，调整方式有两种: 1、单旋，即需调整的分支为左-左或右-右形式；2、双旋，即需调整的分支为左-右或右-左形式。

伸展树
基本想法是：当一个节点被访问后，它就要经过一系列Avl树的旋转被推到根上，但展开的方式又不完全仿照Avl树的旋转方式，第一种情况之字形，按照Avl的双旋形式；一种情况是一字形。

B树
是一种在将数据贮存在磁盘上的合适的数据结构，研究不深。