搜索树:
搜索树：又叫二叉排序树，他是一颗空树，或者具有以下几个特性：
1、若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2、若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3、它的左右子树也分别为二叉搜索树
索搜结构之AVL树：
AVL树：一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
1、它的左右子树都是
AVL树
2、左子树和右子树高度之差(简称平衡因子)的绝对值不超过
1(-1、0、1)
AVL树：表示方法：
每个节点，添加一个
标识左右子树高度差的 int型 变量
pV = 左子树的高度 — 右子树的高度
每次插入节点后，改变插入点的pV，逐层向上改变，
PS:所有的例子中的平衡因子都是用 左子树的高度减去右子树的高度
1、在左边添加节点，双亲节点自加一：
2、在右边添加节点，双亲节点自减一：
在AVL树中插入一个节点有4种情况：
1、在较高的左子树的左边添加节点 即：
节点高度差为2，子节点高度差为1
这种情况：我们利用右单旋转：当我们在向上调整
df，
遇到-2时，需要调整，将为-2节点(即：20)的左子树向上提升，如下图：
2、
在较高的右子树的右边添加节点：
即：节点高度差为-2，子树高度差为-1
3、
在较高左子树，的右边添加节点 即
：节点高度差为2，子树节点高度差为-1
这种情况我们应该先将
子树
(20往下)的进行左单旋，则变成了
2 1
的情况了：
然后调用右单旋
即可完成平衡。
4、较高右子树的， 左边添加节点，在根树高度差为-2， 右子树高度差为1；
1、我们需要先将右子树进行
右单旋
，则情况又转变为-2 -1的情况，：
2、再对根树，进行左单旋：
总结：
PS：
平衡因子以
右子树
高度减去
左子树
高度
pParent平衡因子pCur平衡因子情况处理方法211、在较高右子树，的右边插入直接对pParent进行左旋2-12、在较高右子树，的左边插入先对pCur进行右旋，变为情况1-2-13、在较高左子树，的左边插入直接对pParent进行右旋-214、在较高左子树，的右边插入先对pCur进行左旋，变为情况3
在每一种情况处理完成之后，需要根据情况，对pCur、pParent、pCur->left/pCur->right 的平衡因子进行修正。
转载请注明原文地址: https://www.6miu.com/read-68085.html
