美文网首页
平衡二叉树(AVL)

平衡二叉树(AVL)

作者: edolovee | 来源:发表于2018-03-15 09:31 被阅读0次

定义

平衡二叉树是建立在二叉平衡树基础上,目的使得各个节点的深度尽可能小。
平衡二叉树是一颗二叉树,或者为空,或者满足如下两个性质:

  1. 左右子树深度之差的绝对值不大于1
  2. 左右子树都是平衡二叉树

实现

构造平衡二叉树的过程是动态调整的过程,主要的调整方式有四种,分别为LL型、RR型、LR型、RL型

  1. LL型
    LL型转换方式如下图所示


    image.png
  2. RR型
    RR型转换方式如下图所示


    image.png
  3. RL型
    RL型转换方式如下图所示


    image.png
  4. LR型
    LR型转换方式如下图所示


    image.png

时间复杂度

平衡二叉树的查找效率为O(lg2 n)

相关文章

网友评论

      本文标题:平衡二叉树(AVL)

      本文链接:https://www.haomeiwen.com/subject/ghxtqftx.html