AVL树平衡因子详解

AVL树就是平衡二叉树,左子树和右子树的高度之差绝对值不超过1

而且规定,平衡二叉树的每个节点的平衡因子只能是-1 1 0

按照公式   平衡因子 = 右子树的高度 左子树的高度

-1 : 表示左子树比右子树高

1  : 表示右子树比左子树高

0 : 表示左子树和右子树等高

但是很多人都知道公式,但却有时候不知道怎么去看一个平衡二叉树。

接下来我为大家详解一下平衡因子到底是怎么看的。

首先,我们先看一个普通的二叉树,非平衡树

因为这样能更好的说明问题:

《AVL树平衡因子详解》

此图为普通二叉树,方格内为各个点的平衡因子

接下来我为大家分析一下:

16的平衡因子(-3),左子树的高度为2,右子树的高度为5,所以是2-5 = -3

26的平衡因子(-1),在同一层次上看,即

《AVL树平衡因子详解》

 

26为根节点,左边的高度为1,右边的高度为0,所以26的平衡因子为: 0 – 1 = -1

 

18的平衡因子为(0),以18为根节点来看:

《AVL树平衡因子详解》

 

18为根节点,左边的高度为0,右边的高度为0,所以18的平衡因子为: 0 – 0 = 0

 

3的平衡因子为4.用图形表示为:

《AVL树平衡因子详解》

 

3为根节点,右子树的高度为4,左子树的高度为0,所以3的平衡因子为: 4 – 0 = 4

同理,其他节点的平衡因子的算法都是这要来的,所以大家现在一定会计算各个节点的平衡因子了吧。

当然,是平衡二叉树,我们把这个二叉树进行旋转来变换成平衡二叉树:

《AVL树平衡因子详解》

至于平衡二叉树的平衡因子,相信大家知道怎么去求解了吧。

    原文作者:AVL树
    原文地址: https://blog.csdn.net/travelerwz/article/details/52186357
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞