数据结构算法——二叉树、平衡二叉树详细介绍

2018年6月26日10:35:54 发表评论

一点PHP分享介绍关于数据结构中二叉树以及平衡二叉树两种算法的区别。二叉树(binary)是一种最基本的树形数据结构,用来方便存储基本数据并且能有很高的查询效率,很多其他树形数据结构算法都是参考二叉树慢慢优化演变而来。其中包括平衡二叉树(AVL),平衡二叉树和二叉树的主要区别就是在于如何保持结构的平衡,如何更高效率的获取出数据。

 

二叉树(binary)

二叉树具有以下性质:左子树的键值小于根的键值,右子树的键值大于根的键值。

数据结构算法——二叉树、平衡二叉树详细介绍

叶子根(root)节点为6,左边依次是3、2全部小于根(root)节点。右边依次是7、8全部大于根节点,完全符合上述对二叉树的描述,而左侧叶子节点3处又开叉左右两个分支,依旧符合规则左小右大2<3<5。

通过描述可以很容易理解出二叉树在数据查询中的优势高效率,不同的深度查询的IO次数将不一样,我们取平均值 (1+2+2+3+3+3) / 6 = 2.3次,效率非常高。

下面这个也符合二叉树的规则,所以也是二叉树,但是...

数据结构算法——二叉树、平衡二叉树详细介绍

这棵二叉树的效果很明显会低很多,有的查询甚至需要5次io,平均计算也要(1+2+3+4+5+5)/6 = 3.3。虽然看着只是多一点点,如果数据量增大那效果将是非常明显的,并且就算多一次的IO操作也会对性能效率降低很多,所以这时候就需要引出平衡二叉树的概念。

 

平衡二叉树(AVL)

平衡二叉树(AVL树)在符合二叉查找树的条件下,它的任何节点的两个子树的高度最大差必须为1。下面的两张图片,左边是AVL树,它的任何节点的两个子树的高度差<=1;右边的不是AVL树,其根节点的左子树高度为3,而右子树高度为1

数据结构算法——二叉树、平衡二叉树详细介绍

 

有些情况我们会对这种树进行插入或者删除,这个时候就会出现不平衡的情况,这时候就需要使用旋转的方式来让它继续保持平衡,而不同的结构旋转的方法也不同例如下面:

 

LL的旋转。LL失去平衡的情况下,可以通过一次旋转让AVL树恢复平衡。步骤如下:

  1. 将根节点的左孩子作为新根节点。
  2. 将新根节点的右孩子作为原根节点的左孩子。
  3. 将原根节点作为新根节点的右孩子。

数据结构算法——二叉树、平衡二叉树详细介绍

 

RR的旋转:RR失去平衡的情况下,旋转方法与LL旋转对称,步骤如下:

  1. 将根节点的右孩子作为新根节点。
  2. 将新根节点的左孩子作为原根节点的右孩子。
  3. 将原根节点作为新根节点的左孩子。

数据结构算法——二叉树、平衡二叉树详细介绍

 

RL的旋转:RL失去平衡的情况下也需要进行两次旋转,旋转方法与LR旋转对称,步骤如下:

  1. 围绕根节点的右孩子进行LL旋转。
  2. 围绕根节点进行RR旋转。

数据结构算法——二叉树、平衡二叉树详细介绍

 

LR的旋转:LR失去平衡的情况下,需要进行两次旋转,步骤如下:

  1. 围绕根节点的左孩子进行RR旋转。
  2. 围绕根节点进行LL旋转。

数据结构算法——二叉树、平衡二叉树详细介绍

 

一点PHP,每天一点技术分享。

x

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: