赞
踩
平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
二叉树是每个节点最多有两个子树的树结构,如下图:
二叉树有五种基本形态:
- 二叉树可以是空集
- 根节点可以有空的左右子树
- 根节点只有一个左子树
- 根节点只有一个右子树
- 根节点可以有左右子树
如下图:
为了避免上图这种情况的发生,我们希望可以有一种算法,将我们的不平衡的二叉树排序树转化为平衡二叉排序树。这样就可以让我们的二叉排序树结构实现最优化。
该节点左子树的高度 - 该节点右子树的高度,即左右子树高度之差。
上图情况一,情况二,情况四的由于刚画,忘记了吧区别的子节点区分出来,画一次是真的麻烦,希望大家见谅,不过没有标出来,相信大家也能看出来,小编谢谢各位读者的谅解了。
综上分析,二叉树转换成平衡二叉树的所有情况都给大家罗列出来了,图形画的着实难受,希望能帮到大家,如有疑问请留言!!!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。