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