口碑营销与病毒营销的区别_沈阳网页设计公司有哪些_做谷歌推广比较好的公司_全网推广推荐

二叉平衡搜索树概念

上一篇博客中讲解了二叉搜索树: C++ - 二叉搜索树讲解-CSDN博客
我们了解到, 二叉搜索树的最坏时间复杂度为 O(N). (插入的顺序是有序的)
所以在实际中, 直接使用二叉搜索树的情况很少.

那么为了解决二叉搜索树这种最坏情况, 就有大佬提出了 AVL 树.

AVL 树又称为二叉平衡搜索树, 可以看到, 多了两个字 "平衡".
那么平衡是什么意思:
之前的二叉搜索树在插入顺序是有序的情况下, 会形成一个链表的结构, 从而导致查找的时间复杂度变为 O(N).
那么如果我们在插入的时候, 顺便调整这棵树, 让它始终保持一个利于查询的形态, 那么问题就解决了.

二叉平衡搜索树特性

"平衡": 要保证任意一个节点的左右两边的子树的高度差不超过 1 ( |右树高度 - 左树高度| <= 1).

当我们规定了每个节点的左右子树高度差不超过 1 之后,

就能使得二叉树的搜索的时间复杂度稳定在 O(log n)了,

当我们插入节点破坏 "平衡之后", 就需要去进行 "旋转" 来调节树

二叉平衡搜索树基本框架

AVL 树的节点的定义:
和之前的搜索二叉树比较, 多了两个值:
1. 一个平衡因子 (_balancefactor )
2. 指向父节点的指针 (_parent)

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode(const std::pair<K, V>& kv):_data(kv){}~AVLTreeNode(){}AVLTreeNode<K, V>* _left = nullptr; // 指向左孩子AVLTreeNode<K, V>* _right = nullptr; // 指向右孩子AVLTreeNode<K, V>* _parent = nullptr; // 指向父节点std::pair<K, V> _data; // 存储数据int _balancefactor = 0; // 平衡因子
};

AVL 树定义

template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:AVLTree(){}~AVLTree(){}
private:Node* _root = nullptr; // 根节点
};

二叉平衡搜索树的插入

插入总结有三个步骤:

按照二叉树规则找到插入位置, 并插入数据
数据插入完毕后, 更新平衡因子
检查平衡因子, 平衡因子不正确, 采取相应的措施

更新平衡因子:

如果新插入节点在左边, 那么父节点 balance - 1
新增节点在右边, 那么父节点 balance + 1
更新完成后, 如果父节点的 balance != 0
那么说明数的高度发生了变化, 需要向上更新

可以看到, 当我们插入 0 这个节点后, 5 节点的左右子树高度差超过了 1,
所以接下来我们就需要去调整树的结构 "旋转".

1. 更新 balance

旋转过程比较复杂, 这里先给出更新 balance 的代码.

bool insert(const std::pair<K, V>& kv)
{if (_root == nullptr) // 如果树为空, 那么直接插入, 并且要更新根节点{_root = new Node(kv);return true;}Node* parent = nullptr; // 记录要插入位置的父节点Node* cur = _root; // 查找要插入的位置while (cur){if (cur->_data.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_data.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}if (parent->_data.first > kv.first) // 判断要插入在 parent 的左边还是右边{cur = new Node(kv);parent->_left = cur;cur->_parent = parent;}else{cur = new Node(kv);parent->_right = cur;cur->_parent = parent;}while (parent) // 插入完成后, 需要更新可能会被影响的父节点的平衡因子{if (parent->_left == cur) // 如果插入的节点位于 parent 的左边, 那么 balance - 1{--parent->_balancefactor;}else // 如果插入的节点位于 parent 的左边, 那么 balance + 1{++parent->_balancefactor;}// 如果 balance 更新完成后为 0, 说明对于 parent 来说树的高度没有发生变化, 可以直接返回if (parent->_balancefactor == 0){return true;}else if (parent->_balancefactor == 1 || parent->_balancefactor == -1){cur = parent;parent = parent->_parent;}else if (parent->_balancefactor == 2 || parent->_balancefactor == -2){// 此时树已经不平衡了需要进行旋转, 这里是旋转的代码}else{perror("_balancefactor error\n");assert(false);}}return true;
}

2. 旋转调整

旋转又存在着四种旋转方式:

左单旋
右单旋
左右双旋
右左双旋

首先来看简单的两种旋转方式: 左单旋和右单旋.

下面给出这两种双旋的代码, 代码中的变量和图中变量也是对应的, 方便理解

void RotateL(Node* parent) // 左旋
{Node* subr = parent->_right;Node* subrl = subr->_left; // 上面的图中, 是没有画这个节点的, 但是有可能会存在这个点的if (_root == parent) // {_root = subr;subr->_parent = nullptr;subr->_left = parent;parent->_parent = subr;parent->_right = subrl;if (subrl != nullptr) // 判断这个点是否存在, 如果存在则也需要连接上{subrl->_parent = parent;}}else{Node* pparent = parent->_parent;if (pparent->_left == parent){pparent->_left = subr;}else{pparent->_right = subr;}subr->_parent = pparent;subr->_left = parent;parent->_parent = subr;parent->_right = subrl;if (subrl != nullptr){subrl->_parent = parent;}}parent->_balancefactor = subr->_balancefactor = 0;
}void RotateR(Node* parent) // 右旋
{Node* subl = parent->_left;Node* sublr = subl->_right;if (parent == _root){_root = subl;subl->_parent = nullptr;subl->_right = parent;parent->_parent = subl;parent->_left = sublr;if (sublr != nullptr){sublr->_parent = parent;}}else{Node* pparent = parent->_parent;if (pparent->_left == parent){pparent->_left = subl;}else{pparent->_right = subl;}subl->_parent = pparent;subl->_right = parent;parent->_left = sublr;parent->_parent = subl;if (sublr != nullptr){sublr->_parent = parent;}}parent->_balancefactor = subl->_balancefactor = 0;
}

左右双旋适用于一下所有情况:

左单旋

右单旋

接下来还有左右双旋和右左双旋:
左右双旋: 先左旋, 再右旋
右左双旋: 先右旋, 再左旋

void RotateLR(Node* parent)
{Node* subl = parent->_left;Node* sublr = subl->_right;int bf = sublr->_balancefactor;RotateL(parent->_left);RotateR(parent);if (bf == 0){parent->_balancefactor = subl->_balancefactor = 0;}else if (bf == 1){subl->_balancefactor = -1;}else if (bf == -1){parent->_balancefactor = 1;}
}void RotateRL(Node* parent)
{Node* subr = parent->_right;Node* subrl = subr->_left;int bf = subrl->_balancefactor;RotateR(parent->_right);RotateL(parent);if (bf == 0){parent->_balancefactor = subr->_balancefactor = 0;}else if (bf == 1){parent->_balancefactor = -1;subrl = 0;}else if (bf == -1){subr->_balancefactor = 1;}
}

左右双旋:

右左双旋:

插入完整的代码放在这里

bool insert(const std::pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_data.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_data.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}if (parent->_data.first > kv.first){cur = new Node(kv);parent->_left = cur;cur->_parent = parent;}else{cur = new Node(kv);parent->_right = cur;cur->_parent = parent;}while (parent){if (parent->_left == cur){--parent->_balancefactor;}else{++parent->_balancefactor;}if (parent->_balancefactor == 0){return true;}else if (parent->_balancefactor == 1 || parent->_balancefactor == -1){cur = parent;parent = parent->_parent;}else if (parent->_balancefactor == 2 || parent->_balancefactor == -2){// 旋转代码if (parent->_balancefactor == 2 && parent->_right->_balancefactor == 1){RotateL(parent);}else if (parent->_balancefactor == -2 && parent->_left->_balancefactor == -1){RotateR(parent);}else if (parent->_balancefactor == 2 && parent->_right->_balancefactor == -1){RotateRL(parent);}else if(parent->_balancefactor == -2 && parent->_left->_balancefactor == 1){RotateLR(parent);}break;}else{perror("_balancefactor error\n");assert(false);}}return true;
}