高子树是什么树

高子树是最古老的平衡二叉树，又叫AVL树。

AVL树性质：

1、左右子树高度差不超过1.

复杂度：

插入O(logn)，最多做两次旋转，若干次维护树高。

删除O(logn)，最坏情况做logn次平衡。

旋转操作

插入：

与BST一样，小于当前节点往左子树，大于往有子树。回溯时平衡树高。

删除：

递归查找到目标值的节点

1、如果目标节点是单链节点（只有一个儿子），或没有儿子的节点，则就地删除，用空指针或儿子替代它。

2、如果目标节点有两个儿子，则递归查找它的前驱，用前驱替代它，然后删除前驱节点。

树高修正：

当插入或删除节点时，可能引发高度差超过1，则进行修正。

大前提：左右子树高度差大于1。

最终目的是使树达到平衡

那么只有从高子树旋转向低子树才能做得到。

高子树总是向父亲方向旋转的

对于高子树，还有保证父同侧的儿子节点的树高不大于另一个儿子树高， 如果不满足则需要旋转。