一、平衡二叉树

　　特点： 保证查询的效率较高， 根节点的左右子树的高度差绝对值不超过1，左右子树都是平衡二叉树

 

　　左旋操作六大步骤

       

　　右旋的六大步骤

       

 

 

 

 　　当符合右旋操作时，如果左子树的右子树大于它的左子树高度，需要对当前节点进行左旋操作，再对根节点进行右旋操作。（双旋转）

     

 

 

 

二、 B 树

        

 

 

 

2-3树的基本介绍

2-3 树是最简单的B 树

基本特点： 1）2-3树的所有叶子节点都在同一层

                   2）有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点

                   3）有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点

                   4）2 - 3 树是由二节点和三节点构成的树

 

 

B树 (Balanced Tree)

基本特点： 1） B树的阶： 节点的最多子节点个数。比如 2-3 树的阶是3， 2- 3- 4树的阶是 4

                   2） B树的搜索， 从根节点开始，对节点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子节点；重复， 直到所对应的儿子指针为                              空，或已经是叶子节点

                   3） 关键字集合分布在整棵树中，即叶子节点和非叶子节点都存放数据

                   4） 搜索有可能在非叶子节点结束

                   5） 其搜索性能等价与在关键字全集内做一次二分查找、

                    

 

 

 

B + 树