天水建设局网站渣土治理,腾讯企点app下载安装,淘宝做导航网站有哪些功能,大学生网页设计怎么做AVL 树的概念
也许因为插入的值不够随机#xff0c;也许因为经过某些插入或删除操作#xff0c;二叉搜索树可能会失去平衡#xff0c;甚至可能退化为单链表#xff0c;造成搜索效率低。 AVL Tree 是一个「加上了额外平衡条件」的二叉搜索树#xff0c;其平衡条件的建立是…AVL 树的概念
也许因为插入的值不够随机也许因为经过某些插入或删除操作二叉搜索树可能会失去平衡甚至可能退化为单链表造成搜索效率低。 AVL Tree 是一个「加上了额外平衡条件」的二叉搜索树其平衡条件的建立是为了确保整棵树的深度为 O(log2N)O(log_2N)O(log2N)。
AVL Tree 要求任何节点的左右子树高度相差最多为 1。当违反该规定时就需要进行旋转来保证该规定。
AVL 树的实现
节点的定义
AVL 树节点的定义比一般的二叉搜索树复杂它需要额外一个 parent 指针方便后续旋转。并在每个节点中引入平衡因子便于判断是否需要旋转。
/// brief AVL 树节点结构
/// tparam K 节点的 key 值
/// tparam V 节点的 value 值
template class K, class V
struct AVLTreeNode {AVLTreeNode(const pairK, V kv) : _kv(kv), _parent(nullptr), _left(nullptr), _right(nullptr), _bf(0){}pairK, V _kv;AVLTreeNodeK, V* _parent;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;// 左右子树高度相同平衡因子为0// 左子树高平衡因子为负// 右子树高平衡因子为正int _bf;
};接口总览
templateclass K, class V
class AVLTree {typedef AVLTreeNodeK, V Node;
public:Node* Find(const K key);bool Insert(const pairK, V kv);private:void RotateR(Node* parent);void RotateL(Node* parent);void RotateLR(Node* parent);void RotateRL(Node* parent);
private:Node* _root nullptr;
};查找
AVL 树的查找和普通的搜索二叉树一样
若 key 值大于当前节点的值在当前节点的右子树中查找若 key 值小于当前节点的值在当前节点的左子树中查找若 key 值等于当前节点的值返回当前节点的地址若找到空查找失败返回空指针
/// brief 查找指定 key 值
/// param key 要查找的 key
/// return 找到返回节点的指针没找到返回空指针
Node* Find(const K key) {Node* cur _root;while (cur ! nullptr) {// key 值与当前节点值比较if (key cur-_kv.first) {cur cur-_right;} else if (key cur-_kv.first) {cur cur-_left;} else {return cur;}}return nullptr;
}插入
AVL 的插入整体分为两步
按照二叉搜索树的方式将节点插入调整节点的平衡因子 平衡因子是怎么调整的 设新插入的节点为 pCur新插入节点的父节点为 pParent。在插入之前pParent 的平衡因子有三种可能0、-1、1。
插入分为两种
pCur 插入到 pParent 的左侧将 pParent 的平衡因子减 1pCur 插入到 pParent 的右侧将 pParent 的平衡因子加 1
此时pParent 的平衡因子可能有三种情况0、正负 1、正负 2。
0说明插入之前是正负 1插入后被调整为 0满足 AVL 性质插入成功正负 1说明插入之前是 0插入后被调整为正负 1此时 pParent 变高需要继续向上更新正负 2说明插入之前是正负 1插入后被调整为正负 2此时破坏了规定需要旋转处理
/// brief 插入指定节点
/// param kv 待插入的节点
/// return 插入成功返回 true失败返回 false
bool Insert(const pairK, V kv) {if (_root nullptr) {_root new Node(kv);return true;}// 先找到要插入的位置Node* parent nullptr;Node* cur _root;while (cur ! nullptr) {if (kv.first cur-_kv.first) {parent cur;cur cur-_right;} else if (kv.first cur-_kv.first) {parent cur;cur cur-_left;} else {// 已经存在插入失败return false;}}// 将节点插入cur new Node(kv);if (kv.first parent-_kv.first) {parent-_right cur;cur-_parent parent;} else {parent-_left cur;cur-_parent parent;}// 更新平衡因子直到正常while (parent ! nullptr) {// 调整父亲的平衡因子if (parent-_left cur) {--parent-_bf;} else {parent-_bf;}if (parent-_bf 0) {// 此时不需要再继续调整了直接退出break;} else if (parent-_bf 1 || parent-_bf -1) {// 此时需要继续向上调整cur parent;parent parent-_parent;} else if (parent-_bf 2 || parent-_bf -2) {// 此时需要旋转处理if (parent-_bf -2 cur-_bf -1) {RotateR(parent);} else if (parent-_bf 2 cur-_bf 1) {RotateL(parent);} else if (parent-_bf -2 cur-_bf 1) {RotateLR(parent);} else if (parent-_bf 2 cur-_bf -1) {RotateRL(parent);} else {assert(false);}// 旋转完了就平衡了直接退出break;} else {// 此时说明之前就处理错了assert(false);} // end of if (parent-_bf 0)} // end of while (parent ! nullptr)return true;
}旋转
假设平衡因子为正负 2 的节点为 X由于节点最多拥有两个子节点因此可以分为四种情况
插入点位于 X 的左子节点的左子树——左左右单旋插入点位于 X 的左子节点的右子树——左右左右双旋插入点位于 X 的右子节点的右子树——右右左单旋插入点位于 X 的右子节点的左子树——右左右左双旋 右单旋 假设平衡因子为正负 2 的节点为 parentparent 的父节点为 pParentparent 的左子树为 subLsubL 的右子树为 subLR。
右单旋的操作流程
让 subLR 作为 parent 的左子树让 parent 作为 subL 的右子树让 subL 作为整个子树的新根更新平衡因子
/// brief 进行右单旋
/// param parent 平衡因子为正负 2 的节点
void RotateR(Node* parent) {Node* pParent parent-_parent;Node* subL parent-_left;Node* subLR parent-_left-_right;// 更改链接关系// 1. subLR 作为 parent 的左子树parent-_left subLR;if (subLR ! nullptr) {subLR-_parent parent;}// 2. parent 作为 subL 的右子树subL-_right parent;parent-_parent subL;// 3. subL 作为整个子树的新根if (parent _root) {// parent 为 _root此时令 subL 为 _root_root subL;subL-_parent nullptr;} else {// parent 不为 _rootpParent 也就不为空if (parent pParent-_left) {pParent-_left subL;} else {pParent-_right subL;}subL-_parent pParent;}// 4. 更新平衡因子// 观察上图明显可知subL-_bf 0;parent-_bf 0;
}左单旋
左单旋与右单旋类似只是方向不同。
假设平衡因子为正负 2 的节点为 parentparent 的父节点为 pParentparent 的右子树为 subRsubR 的左子树为 subRL。
左单旋的操作流程
让 subRL 作为 parent 的右子树让 parent 作为 subR 的左子树让 subR 作为整个子树的新根更新平衡因子
/// brief 进行左单旋
/// param parent 平衡因子为正负 2 的节点
void RotateL(Node* parent) {Node* pParetn parent-_parent;Node* subR parent-_right;Node* subRL parent-_right-_left;// 更改链接关系// 1. subRL 作为 parent 的右子树parent-_right subRL;if (subRL ! nullptr) {subRL-_parent parent;}// 2. parent 作为 subR 的左子树subR-_left parent;parent-_parent subR;// 3. subR 作为整个子树的新根if (parent _root) {_root subR;subR-_parent nullptr;} else {if (parent pParetn-_left) {pParetn-_left subR;} else {pParetn-_right subR;}subR-_parent pParetn;}// 4. 更新平衡因子subR-_bf 0;parent-_bf 0;
}左右双旋 假设平衡因子为正负 2 的节点为 parentparent 的左子树为 subLsubL 的右子树为 subLR。
左右双旋就是对 subL 进行一次左单旋对 parent 进行一次右单旋。双旋也就完成了要注意的是双旋后平衡因子的更新。
此时分三种情况
新插入的节点是 subLR 的右子树 新插入的节点是 subLR 的左子树 新插入的是 subLR 结合上述情况写出如下代码
/// brief 进行左右双旋
/// param parent 平衡因子为正负 2 的节点
void RotateLR(Node* parent) {Node* subL parent-_left;Node* subLR parent-_left-_right;int bf subLR-_bf;RotateL(subL);RotateR(parent);if (bf 1) {// 新插入节点是 subLR 的右子树parent-_bf 0;subL-_bf -1;subLR-_bf 0;} else if (bf -1) {// 新插入的节点是 subLR 的左子树parent-_bf 1;subL-_bf 0;subLR-_bf 0;} else if (bf 0) {// 新插入的节点是 subLRparent-_bf 0;subL-_bf 0;subLR-_bf 0;} else {assert(false);}
}右左双旋
假设平衡因子为正负 2 的节点为 parentparent 的右子树为 subRsubR 的左子树为 subRL。
右左双旋就是对 subR 进行一次右单旋对 parent 进行一次左单旋。流程和左右双旋一样这里就不过多介绍了。
void RotateRL(Node* parent) {Node* subR parent-_right;Node* subRL parent-_right-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent);if (bf 1) {// 新插入节点是 subRL 的右子树parent-_bf -1;subR-_bf 0;subRL-_bf 0;} else if (bf -1) {// 新插入的节点是 subRL 的左子树parent-_bf 0;subR-_bf 1;subRL-_bf 0;} else if (bf 0) {// 新插入的节点是 subRLparent-_bf 0;subR-_bf 0;subRL-_bf 0;} else {assert(false);}
}
