AVL树#xff1a;

对于BSTree虽然可以缩短查找的效率但如果数据有序它将退化为单支树

AVL树

它的每个结点的左右子树高度之差的绝对值不超过1它的左右子树都是AVL树

基本结构

//用pair封起来的键值对AVLTreeNode(const

pairK,

kv):_kv(kv),_bf(0),_left(nullptr),_right(nullptr),_parent(nullptr){}

};插入

kv){//1.按照搜索树规则插入先找到合适的位置然后链接if

(_root

nullptr;//父节点//方便记录父节点原来的子树Node*

cur

false;}}//查找完再判断是父节点的左树还是右数//标记为Acur

new

parent;//2.更新平衡因子根据AVL的规则进行旋转调整//

更新原则//

2.根据_parent-_bf是否为0来判断是否修改祖先的_bf//

_bf

cur){parent-_bf;}else{parent-_bf--;}if

(parent-_bf

1){RotateLR(parent);}else{RotateRL(parent);}break;//因为旋转完就是全都平衡了所以直接结束循环}else{throw(false);}}return

true;}旋转

将右节点的左子树变为祖先节点的右子树将祖先节点变为父节点的左子树

void

subR;}else{parent-_parent-_right

subR:}subR-_parent

subL;}else{parent-_parent-_right

subL:}subL-_parent

subLR-_bf;RotateL(parent-_left);RotateR(parent);if

(bf

subRL-_bf;RotateR(subR);RotateL(parent);subRL-_bf

0;if

root-_bf){throw(平衡因子异常);}return

我们可以发现这段代码还可以优化因为每一次的高度都是要重新求的有很多重复工作。

bool

height);这样树的高度就会再函数调用结束后被传出来并且不用修改返回值

bool

AVL树比搜索树要更优秀但具体逻辑指旋转要更复杂希望对你有帮助