AVL平衡二叉搜索树

目录AVL树前瞻AVL树的起源AVL树创建背景新变动节点AVL树的节点插入平衡因子的更新具体更新规则旋转(Rotate)单旋右单旋代码实现左单旋代码实现双旋左右双旋右左双旋AVL树的平衡检测AVL树前瞻AVL树的起源AVL树是一种自平衡二叉搜索树由Adelson-Velsky和Landis在1962年提出。其核心特性是任意节点的左右子树高度差平衡因子不超过1通过旋转操作维护平衡确保查找、插入和删除操作的时间复杂度为O(log N)。AVL树创建背景AVL树是继二叉搜索树唯一限制条件—小节点放在左侧大节点放在右侧。后的优化版本。优化原因在普遍情况下可能存在左右子树高度差不均衡的情况导致搜索树效率大大退化。新变动为解决高度不均衡问题引入了一个额外指针parent与一个额外变量bf(平衡因子(balance factor))。parent指向父节点。bf(平衡因子)在当前节点 右子树高度-左子树高度 / 左子树的高度-右子树的高度 的值。节点//private: 此处应当公共域因为后续要用Node内的指针 平衡因子templateclass T struct AVLNode { AVLNode(const T data T()) : _left(nullptr) , _right(nullptr) , _parent(nullptr) , _val(data) , _bf(0) { } //private: 此处应当公共域因为后续要用Node内的指针 平衡因子 AVLNodeT* _left; AVLNodeT* _right; AVLNodeT* _parent; T _val; int _bf; // 节点的平衡因子 };※在创建节点后在.cpp文件中测试(显示未识别)为什么string呢 因为即使你在.h中包含了头文件string但是我常常不使用using namespace std;展开 所以在.cpp中要以AVLNodestd::string n;而不是AVLNodestring n;AVL树的节点插入插入一个值按照二叉搜索树的规则进行插入。新增节点后会影响祖先节点的平衡因子所以平衡因子需要更新。平衡因子的更新平衡因子左子树高度-右子树高度。节点来源于右支bf来源于左支bf--。具体更新规则更新的对象是p指向的bf不是cur指向的bf。因为cur的存在是为了决定bf加加还是减减(在模拟实现中bf常用直接赋值就报名了过大(2)与过小(-2))。if (cur p-_right) p-_bf; else p-_bf--;1.更新后bf为0代表新增的节点弥补空缺高度没有增加停止更新。2.更新后bf为1/-1只能的情况0-1或者-1-0 代表高度增加一侧高一侧低——影响祖先节点若不为根(cur ! _root)需要继续向上更新3.更新后bf为2/-2需要根据实际情况来判断进行的旋转类型。旋转(Rotate)旋转的前提是p-bf 2/-2 cur-bf 1/-1;//二者排列组合出现四种情况2 1 2 -1 -2 1 -2 -1前言1.及时解决高度差过大的问题。2.旋转是节点移动的具象化表述非完全的旋转。※3.旋转要注意两点①p与_root的关系 ②节点的三指针指向变动单旋单旋情景较为单一单旋情景下左单旋p-_bf -2 cur-_bf -1右单旋p-_bf 2 cur-_bf 1右单旋代码实现左单旋代码实现单旋情景下p、cur的bf都变成了0。 原因在于旋转后的高度一致。双旋两种双旋各自有三种场景分别对应在subLR/subRL左支插入、右支插入和空情况 双旋。深刻理解其的本质1.分别旋转的节点移动。2.分别旋转的分支移动。左右双旋分作三种情况1.subLR-bf -1;2.subLR-bf 1;3.subLR-bf 0;此处的差异导致旋转后平衡因子的更新差异。右左双旋分作三种情况1.subRLbf -1;2.subRL-bf 1;3.subRL-bf 0;此处的差异导致旋转后平衡因子的更新差异。AVL树的平衡检测能否以检测平衡因子的值来检测是否平衡 // 不能在尚需的实现中若出现超出范围的平衡因子的值会直接报错 所以这种思路行不通。能否使用Height辅助函数返回左右两侧高度差值来判断 //不能 Height调用非空 空返回0相当于false矛盾。正确做法利用height计算此树高度再利用高度差判断是否合法。