网站前置审批文件,常州设计公司排名,怎么做网站竞价推广,expedia电子商务网站建设数据结构、算法总述#xff1a;数据结构/算法 C/C-CSDN博客 AVL树
定义 空二叉树是一个 AVL 树如果 T 是一棵 AVL 树#xff0c;那么其左右子树也是 AVL 树#xff0c;并且 #xff0c;h 是其左右子树的高度树高为 平衡因子#xff1a;右子树高度 - 左子树高度 创建节点…数据结构、算法总述数据结构/算法 C/C-CSDN博客 AVL树
定义 空二叉树是一个 AVL 树如果 T 是一棵 AVL 树那么其左右子树也是 AVL 树并且 h 是其左右子树的高度树高为 平衡因子右子树高度 - 左子树高度 创建节点
由于 AVL 树的相关操作需要获取节点高度因此我们需要为节点类添加 height 变量
/* AVL 树节点类 */
struct TreeNode {int val{}; // 节点值int height 0; // 节点高度TreeNode *left{}; // 左子节点TreeNode *right{}; // 右子节点TreeNode() default;explicit TreeNode(int x) : val(x){}
}; “节点高度”是指从该节点到它的最远叶节点的距离即所经过的“边”的数量。需要特别注意的是叶节点的高度为 0 而空节点的高度为 −1 。我们将创建两个工具函数分别用于获取和更新节点的高度
/* 获取节点高度 */
int height(TreeNode *node) {// 空节点高度为 -1 叶节点高度为 0return node nullptr ? -1 : node-height;
}/* 更新节点高度 */
void updateHeight(TreeNode *node) {// 节点高度等于最高子树高度 1node-height max(height(node-left), height(node-right)) 1;
}
节点的平衡因子balance factor定义为节点左子树的高度减去右子树的高度同时规定空节点的平衡因子为 0 。我们同样将获取节点平衡因子的功能封装成函数方便后续使用
/* 获取平衡因子 */
int balanceFactor(TreeNode *node) {// 空节点平衡因子为 0if (node nullptr)return 0;// 节点平衡因子 左子树高度 - 右子树高度return height(node-left) - height(node-right);
}
旋转
我们将平衡因子绝对值 1 的节点称为“失衡节点”。根据节点失衡情况的不同旋转操作分为四种右旋、左旋、先右旋后左旋、先左旋后右旋。
右旋 /* 右旋操作 */
TreeNode *rightRotate(TreeNode *node) {TreeNode *child node-left;TreeNode *grandChild child-right;// 以 child 为原点将 node 向右旋转child-right node;node-left grandChild;// 更新节点高度updateHeight(node);updateHeight(child);// 返回旋转后子树的根节点return child;
}
左旋 /* 左旋操作 */
TreeNode *leftRotate(TreeNode *node) {TreeNode *child node-right;TreeNode *grandChild child-left;// 以 child 为原点将 node 向左旋转child-left node;node-right grandChild;// 更新节点高度updateHeight(node);updateHeight(child);// 返回旋转后子树的根节点return child;
}
先左旋后右旋 仅使用左旋或右旋都无法使子树恢复平衡。此时需要先对 child 执行“左旋”再对 node 执行“右旋”。
先右旋后左旋 旋转的选择 判断失衡节点的平衡因子以及较高一侧子节点的平衡因子的正负号来确定旋转方式
失衡节点的平衡因子子节点的平衡因子旋转方式1≥0右旋10先左旋后右旋-1≤0左旋-10先右旋后左旋
/* 执行旋转操作使该子树重新恢复平衡 */
TreeNode *rotate(TreeNode *node) {// 获取节点 node 的平衡因子int _balanceFactor balanceFactor(node);// 左偏树if (_balanceFactor 1) {if (balanceFactor(node-left) 0) {// 右旋return rightRotate(node);} else {// 先左旋后右旋node-left leftRotate(node-left);return rightRotate(node);}}// 右偏树if (_balanceFactor -1) {if (balanceFactor(node-right) 0) {// 左旋return leftRotate(node);} else {// 先右旋后左旋node-right rightRotate(node-right);return leftRotate(node);}}// 平衡树无须旋转直接返回return node;
}
基础操作
插入
在 AVL 树中插入节点后从该节点到根节点的路径上可能会出现一系列失衡节点。因此我们需要从这个节点开始自底向上执行旋转操作使所有失衡节点恢复平衡。
/* 插入节点 */
void insert(int val) {root insertHelper(root, val);
}/* 递归插入节点辅助方法 */
TreeNode *insertHelper(TreeNode *node, int val) {if (node nullptr)return new TreeNode(val);/* 1. 查找插入位置并插入节点 */if (val node-val)node-left insertHelper(node-left, val);else if (val node-val)node-right insertHelper(node-right, val);elsereturn node; // 重复节点不插入直接返回updateHeight(node); // 更新节点高度/* 2. 执行旋转操作使该子树重新恢复平衡 */node rotate(node);// 返回子树的根节点return node;
}
删除
在二叉搜索树的删除节点方法的基础上需要从底至顶执行旋转操作使所有失衡节点恢复平衡。
/* 删除节点 */
void remove(int val) {root removeHelper(root, val);
}/* 递归删除节点辅助方法 */
TreeNode *removeHelper(TreeNode *node, int val) {if (node nullptr)return nullptr;/* 1. 查找节点并删除 */if (val node-val)node-left removeHelper(node-left, val);else if (val node-val)node-right removeHelper(node-right, val);else {if (node-left nullptr || node-right nullptr) {TreeNode *child node-left ! nullptr ? node-left : node-right;// 子节点数量 0 直接删除 node 并返回if (child nullptr) {delete node;return nullptr;}// 子节点数量 1 直接删除 nodeelse {delete node;node child;}} else {// 子节点数量 2 则将中序遍历的下个节点删除并用该节点替换当前节点TreeNode *temp node-right;while (temp-left ! nullptr) {temp temp-left;}int tempVal temp-val;node-right removeHelper(node-right, temp-val);node-val tempVal;}}updateHeight(node); // 更新节点高度/* 2. 执行旋转操作使该子树重新恢复平衡 */node rotate(node);// 返回子树的根节点return node;
}
查找
与二叉搜索树一致
AVL树总代码
AVLTree.h
#include iostream
#include assert.h
using namespace std;templateclass K, class V
struct AVLTreeNode
{AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;int _bf; // balance factorpairK, V _kv;AVLTreeNode(const pairK, V kv): _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv){}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);}Node* cur _root;Node* parent nullptr;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first)parent-_left cur;elseparent-_right cur;cur-_parent parent;while (parent)//最坏情况一直更新到root此时parent为nullptr{if (cur parent-_left)//更新平衡因子parent-_bf--;elseparent-_bf;if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf -1)//向上查找检测是否出现不平衡{cur cur-_parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){//旋转if (parent-_bf 2 cur-_bf 1)//21说明右边子树深度阶梯式增加所以往左旋转RotateL(parent);//左单旋else if (parent-_bf -2 cur-_bf -1)//-2-1说明左边子树深度阶梯式增加所以往右旋转RotateR(parent);//右单旋else if (parent-_bf -2 cur-_bf 1)//-2, 1说明左边子树中间深先左单旋提高中间节点再右单旋提高中间节点RotateLR(parent);else if (parent-_bf 2 cur-_bf -1)//2, -1说明右边子树中间深先右单旋提高中间节点再左单旋提高中间节点RotateRL(parent);elseassert(false);break;}else //说明插入前AVL出现了问题直接报错{assert(false);}}return true;}//左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;Node* ppNode parent-_parent;parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (ppNode-_left parent)ppNode-_left subR;elseppNode-_right subR;subR-_parent ppNode;}parent-_bf 0;subR-_bf 0;}//右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* ppNode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppNode-_left parent)ppNode-_left subL;elseppNode-_right subL;subL-_parent ppNode;}parent-_bf 0;subL-_bf 0;}//左右双旋void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf -1){subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else if (bf 1){subLR-_bf 0;subL-_bf -1;parent-_bf 0;}else if (bf 0){subLR-_bf 0;subL-_bf 0;parent-_bf 0;}else{assert(false);}}//右左双旋void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf -1){subR-_bf 1;subRL-_bf 0;parent-_bf 0;}else if (bf 1){subR-_bf 0;subRL-_bf 0;parent-_bf -1;}else if (bf 0){subR-_bf 0;subRL-_bf 0;parent-_bf 0;}else{assert(false);}}//中序void InOrder(){_InOrder(_root);cout end endl;}private://中序void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first - ;_InOrder(root-_right);}Node* _root nullptr;
};应用
组织和存储大型数据适用于高频查找、低频增删的场景。 红黑树
红黑树是一种自平衡的二叉搜索树。每个节点额外存储了一个 color 字段 (RED or BLACK)用于确保树在插入和删除时保持平衡
性质 节点为红色或黑色根节点必须为黑色NIL 节点空叶子节点为黑色红色节点的子节点为黑色从根节点到 NIL 节点的每条路径上的黑色节点数量相同 创建节点
enum Colour
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pairK, V _kv;Colour _col;
};_left左子树_right右子树_parent父节点_kv节点存储的值_col该节点的颜色 构造函数
RBTreeNode(const pairK, V kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED)//初始化为红节点
{}红黑树本体类中只存储根节点_root
templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
private:Node* _root nullptr;
}插入
以二叉搜索树插入逻辑为基础
bool Insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);_root-_col BLACK;//保持根为黑节点}Node* cur _root;Node* parent nullptr;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first)parent-_left cur;elseparent-_right cur;cur-_parent parent;//调整红黑树//......//......//......return true;
}代码分析 if (_root nullptr)
{_root new Node(kv);_root-_col BLACK;//保持根为黑节点
}插入节点时根节点_root为空说明当前整棵树都为空那么直接插入值作为根节点即可但是根节点必须是黑色节点而我们新插入的节点是红色所以要将其调整为黑色节点。 while (cur)
{if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}
}找到合适的插入位置当key大于当前节点cur-_kv.first kv.first那么cur就向左寻找反之向右寻找。如果当前节点值等于key那么说明该节点已经存在返回false代表插入失败。当我们的cur为空指针说明已经找到了插入的节点此时跳出循环进行插入。 cur new Node(kv);if (parent-_kv.first kv.first)parent-_left cur;
elseparent-_right cur;cur-_parent parent;到达此处说明前面已经找到插入的位置了而parent节点就是插入位置的父亲节点。根据key的大小来判断插入到左边还是右边插入完成后再让新节点的_parent指向parent。 分情况调整红黑树
对于红黑树的插入我们需要关注新节点的父亲parent祖父grandfather叔叔uncle三个节点 1.根据parent节点的颜色来判断是否需要调整 parent节点为黑色 新插入的节点默认为红色所以新插入节点不会影响路径上黑色节点的数目而parent是黑节点我们也没有出现连续的红色节点所以这种情况无需任何调整直接插入就可以。 parent节点为红色 如果父亲节点为红色我们就会出现连续的红色节点这时我们就需要进行调整了 当parent为红色我们就需要再根据uncle的颜色将插入分类两类uncle为红色以及uncle为黑色 注意由于parent是红色节点此时的grandfather一定是黑色节点
2.根据uncle节点的颜色来判断如何调整
uncle节点为红色
当uncle节点为红色此时需要进行变色 由于新插入了红色的cur节点此时parent与cur出现了连续的红色节点于是我们将parent改为黑色。但是此时以parent为根的所有路径就会多出一个黑节点于是把grandfather变为红色来抵消这个新增的黑节点。但是此时以uncle为根的路径又会少一个黑节点于是把uncle变黑
但是我们将grandfather变为了红色这有可能会影响到上一层节点 grandfather变红之后可能出现两个红色节点相连的情况所以我们要写一个while循环来反复向上检查。
while (parent parent-_col RED)//只有parent为红才更新 (parent可能不存在)
{Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;//uncle存在且为红节点if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//uncle为黑节点 {//其它处理}}else{Node* uncle grandfather-_left;//uncle存在且为红节点if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//uncle为黑节点 {//其它处理}}
}_root-_col BLACK;//在循环内部不判断root情况统一处理代码分析 while (parent parent-_col RED)用于检测cur的parent的颜色通过我们前面的推导如果parent为红色才需要调整因此进入循环的条件之一是parent为红色。另外的parent有可能为NIL此时我们要避免访问空指针所以空指针也不能进循环 if (parent grandfather-_left)
{ }
else
{ }检测parent 节点是grandfather的左子树还是右子树这将涉及到如何找uncle以及下一种情况的调整此时我们要分类讨论 当parent grandfather-_left成立那么uncle就是grandfather的右子树Node* uncle grandfather-_right;反之就是左子树 if (uncle uncle-_col RED)
{parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;
} 找到uncle后如果uncle是红色那么直接进行变色操作把parent和uncle的颜色变为黑色grandfather变为红色。 随后由于我们的变色操作可能会影响上一层此时调整节点进入下一次while循环 _root-_col BLACK;在先前的while循环中有可能出现对_root节点的操作导致_root的颜色改变而_root需要保持黑色。如果我们在循环内部每一次都检测_root有点麻烦了于是我们直接在每一次调整完节点后把_root强行矫正为黑色 uncle节点为黑色
又因为红黑树中NIL也算作黑色节点所以uncle为黑色分为以下两种情况 uncle为空指针uncle不为空指针 如果 uncle为空指针那么cur一定是新插入的节点。 因为如果cur不是新插入的节点那么cur和parent一定有一个原先是黑色节点不然会出现连续的红色节点。但是如果cur和parent有一个是黑色节点那么grandfather的左子树就比右子树多出一个黑节点这就违背了红黑树规则。无论怎样原先的树都不可能符合规则所以cur一定是新插入的节点破坏了规则。 如果 uncle不为空指针那么cur一定是从黑色节点变成的红色节点不是新插入的。 因为如果uncle存在那么grandfather的右子树就存在一个黑节点而parent是红节点所以cur和parent的右子树中都至少有一个黑节点才能保证每一条路径黑节点数目相同。因此cur原先一定是黑节点是因为cur下层插入了新节点然后通过while循环向上走影响到了当前层。
对于这种uncle为黑色的情况我们需要通过旋转变色来维持红黑树。
旋转又分单旋和双旋同AVL树 当cur与parent的关系和parent与grandfather的关系一致时需要进行单旋 当cur与parent的关系和parent与grandfather的关系不一致时需要进行双旋 当parent grandfather-_left
else//uncle为黑节点 (旋转)
{if (cur parent-_left){RotateR(grandfather);//右单旋parent-_col BLACK;//变色grandfather-_col RED;//变色}else{RotateL(parent);//左右双旋 - 左单旋RotateR(grandfather);//左右双旋 - 右单旋cur-_col BLACK;//变色grandfather-_col RED;//变色}break;//旋转后一定平衡
}当parent grandfather-_right
else//uncle为黑节点 (旋转)
{if (cur parent-_right){RotateL(grandfather);//左单旋parent-_col BLACK;//变色grandfather-_col RED;//变色}else{RotateR(parent);//右左双旋 - 右单旋RotateL(grandfather);//右左双旋 - 左单旋cur-_col BLACK;//变色grandfather-_col RED;//变色}break;//旋转后一定平衡
}insert总代码
bool Insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);_root-_col BLACK;//保持根为黑节点}Node* cur _root;Node* parent nullptr;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first)parent-_left cur;elseparent-_right cur;cur-_parent parent;while (parent parent-_col RED)//只有parent为红才更新 (parent可能不存在){Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;//uncle存在且为红节点if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//uncle不存在或为黑节点 (旋转){if (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;//旋转后一定平衡}}else{Node* uncle grandfather-_left;//uncle存在且为红节点if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//uncle不存在或为黑节点 (旋转){if (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;//旋转后一定平衡}}}_root-_col BLACK;//在循环内部不判断root情况统一处理return true;
}红黑树总代码
RBTree.h
#include iostream
#include assert.h
using namespace std;enum Colour
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pairK, V _kv;Colour _col;RBTreeNode(const pairK, V kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;//保持根为黑节点}Node* cur _root;Node* parent nullptr;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first)parent-_left cur;elseparent-_right cur;cur-_parent parent;while (parent parent-_col RED)//只有parent为红才更新 (parent可能不存在){Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;//uncle存在且为红节点if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//uncle不存在或为黑节点 (旋转){if (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;//旋转后一定平衡}}else{Node* uncle grandfather-_left;//uncle存在且为红节点if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//uncle不存在或为黑节点 (旋转){if (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;//旋转后一定平衡}}}_root-_col BLACK;//在循环内部不判断root情况统一处理return true;}//左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;Node* ppNode parent-_parent;parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (ppNode-_left parent)ppNode-_left subR;elseppNode-_right subR;subR-_parent ppNode;}}//右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* ppNode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppNode-_left parent)ppNode-_left subL;elseppNode-_right subL;subL-_parent ppNode;}}size_t Size(){return _Size(_root);}size_t _Size(Node* root){if (root nullptr)return 0;;return _Size(root-_left) _Size(root-_right) 1;}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key){cur cur-_right;}else if (cur-_kv.first key){cur cur-_left;}else{return cur;}}return nullptr;}//中序void InOrder(){_InOrder(_root);cout end endl;}int Height(){return _Height(_root);}private://中序void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first - ;_InOrder(root-_right);}//求高度int _Height(Node* root){if (root nullptr)return 0;return max(Height(root-_left), Height(root-_right)) 1;}Node* _root nullptr;
};应用
作为mapset的底层
