平衡二叉树-AVL

title: "平衡二叉树-AVL"
date: 2015-06-25 09:09:49
categories: 数据结构
tags: 数据结构

由来

  • 一棵斜树也可以是一棵二叉排序树，但是斜树 查找慢；
  • 所以最好把BST构建成平衡二叉树 AVL，查找快；
  • 深度越小，查找结点路径越短，查找也就越快；
  • 可以称AVL是一种特殊的 BST；

定义

  • 平衡因子-BF（blance Factor）：结点的左子树深度 - 右子树深度，有三种可能值 -1 、0、1；
  • BF绝对值 <=1；

最小不平衡子树

  • 向BST中插入新结点，导致某棵子树的BF绝对值 >1；

  • 称这棵子树为最小不平衡子树；


    AVL-one
    AVL-one

插入一个新结点调整平衡

  • 当插入一个新结点后，导致整棵二叉树失去平衡；
  • 调整最小不平衡子树为平衡二叉树；
  • 最小不平衡子树根结点 BF符号与子结点BF相同：
    • 都是正数：左高右低，右旋转；
    • 都是负数：左低右高，左旋转；
  • 最小不平衡子树根结点 BF符号与子结点BF不同：
  • 将子结点作为根结点进行相应旋转，使其子结点BF符号与根结点符号相同；
  • 然后在进行相应的旋转，达到平衡的目的；

讨论版图

AVL
AVL
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容