平衡因子 $delta(T)$

为了度量一颗二叉树的平衡，可以比较左右分支的高度差，如果差很大，则说明树不平衡。
定义一棵树的高度差如下：

AVL树的定义

如果一棵二叉搜索树的所有子树都满足如下条件，称之为AVL树。

插入

向AVL树中插入一个新key，根节点的平衡因子的变化区间为[-1,1]，树的高度最多增加1。
算法描述：
定义插入算法的结果为一对值$(T',Delta H)$，其中$T'$为插入后的新树，$Delta H$为树高度的增加值。令函数 $first(pari)$ 取得一对值中的第一个元素，在二叉搜索树的插入算法上进行改动，定义AVL树的插入操作：

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!