Java教程

[算法]——平衡二叉树(AVL树)+ B 树

本文主要是介绍[算法]——平衡二叉树(AVL树)+ B 树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一、平衡二叉树

  特点: 保证查询的效率较高, 根节点的左右子树的高度差绝对值不超过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 + 树

 

这篇关于[算法]——平衡二叉树(AVL树)+ B 树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!