中山网站建设如何,做企业网站服务,门户cms系统,微信小程序排名关键词优化文章目录1、AVL树1.1 AVL树的插入1.2 总结与测试AVL树2、红黑树2.1 红黑树的插入2.2 红黑树的测试了解AVL树是为了了解红黑树#xff0c;了解红黑树是为了更好的理解set和map。 1、AVL树
AVL树是在二叉搜索树的基础上进行了严格的平衡#xff0c;能做到平衡的关键是通过平衡…
文章目录1、AVL树1.1 AVL树的插入1.2 总结与测试AVL树2、红黑树2.1 红黑树的插入2.2 红黑树的测试了解AVL树是为了了解红黑树了解红黑树是为了更好的理解set和map。 1、AVL树
AVL树是在二叉搜索树的基础上进行了严格的平衡能做到平衡的关键是通过平衡因子以及旋转。 AVL树有以下特性
任何根的左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。其中平衡因子是用右子树高度减去左子树高度。任何子树都是AVL树。 下面实现的AVL树还是KV结构的。 AVL树节点定义
#include iostream
#include assert.h
using namespace std;templateclass K, class V
struct AVLTreeNode
{//三叉链结构方便访问父节点struct AVLTreeNodeK, V* _left;struct AVLTreeNodeK, V* _right;struct AVLTreeNodeK, V* _parent;pairK, V _kv; //键值对 里面存储key和valueint _bf; //平衡因子AVLTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0)
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:private:Node* root nullptr;
};1.1 AVL树的插入 1、AVL树的插入首先一开始和二叉搜索树的插入一样先确定插入的位置再和父节点链接。 2、插入完后可能会破坏AVL树结构所以要判断平衡因子。 插入新结点后平衡因子会出现三种情况。 3、当平衡因子出现了-2或2的情况这个时候就需要对parent进行旋转。 旋转有以下情况。 bool insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);return true;}Node* cur _root;Node* parent _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;}}cur new Node(kv);//只能用kv值来确定parent和cur的指向if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}//判断平衡因子while (parent){if (parent-_left cur){//根节点左边插入节点根的平衡因子-1parent-_bf--;}else{//根节点右边插入节点根的平衡因子1parent-_bf;}//说明之前是-1或1变为平衡if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf -1){//下面子树高度差也影响了上面的根结点所以需要向上调整cur parent;parent cur-_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);}}//whilereturn true;}旋转 //右旋转void RotateR(Node* parent){//从下到上依次修改Node* sub parent-_left;Node* subR sub-_right;//先改变最下面的subR结点parent-_left subR;if (subR){subR-_parent parent;}//再改变parent结点sub-_right parent;Node* ppnode parent-_parent;parent-_parent sub;//最后改变sub结点if (ppnode nullptr){_root sub;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left sub;}else{ppnode-_right sub;}sub-_parent ppnode;}parent-_bf sub-_bf 0;}//左旋和右旋类似void RotateL(Node* parent){Node* sub parent-_right;Node* subL sub-_left;parent-_right subL;if (subL){subL-_parent parent;}sub-_left parent;Node* ppnode parent-_parent;parent-_parent sub;if (ppnode nullptr){_root sub;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left sub;}else{ppnode-_right sub;}sub-_parent ppnode;}parent-_bf sub-_bf 0;}void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;//保存subLR的平衡因子为了知道从subLR哪边插入int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf -1) // subLR左子树新增{subL-_bf 0;parent-_bf 1;subLR-_bf 0;}else if (bf 1) // subLR右子树新增{parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if (bf 0) // subLR自己就是新增{parent-_bf 0;subL-_bf 0;subLR-_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) // subRL左子树新增{subR-_bf 1;parent-_bf 0;subRL-_bf 0;}else if (bf 1) // subRL右子树新增{parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else if (bf 0) // subRL自己就是新增{parent-_bf 0;subR-_bf 0;subRL-_bf 0;}else{assert(false);}}可能会有的问题解释以下是自己的理解 1、如何想到旋转的情况 其实从所有情况看就这两个情况以及他们的翻转记住它们两个就好了。 2、如何看左右旋 拿上图举例左边是一个右旋能平衡的场景只需要将最高的结点往右放就行。 右边是一个双选的场景先将中间结点左旋就成了图左边的场景再右旋就行。 1.2 总结与测试AVL树 AVL树重点关注的是其平衡因子和选择如何使得AVL树平衡通过插入了解就足够了。 下面是如何测试结果是AVL树 1、通过每个结点的左右子树的高度判断平衡因子是否符合要求。 2、通过小和大的测试用例测试是不是AVL树 #pragma once
#include iostream
#include assert.h
using namespace std;templateclass K, class V
struct AVLTreeNode
{struct AVLTreeNodeK, V* _left;struct AVLTreeNodeK, V* _right;struct AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf;AVLTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:bool insert(const pairK, V kv){}void RotateR(Node* parent){}void RotateL(Node* parent){}void RotateLR(Node* parent){}void RotateRL(Node* parent){}int Height(Node* root){if (root nullptr){return 0;}int leftHight Height(root-_left);int rightHight Height(root-_right);return leftHight rightHight ? leftHight 1 : rightHight 1;}bool IsBalanceTree(){return _IsBalanceTree(_root);}bool _IsBalanceTree(Node* parent){if (parent nullptr){return true;}int leftHight Height(parent-_left);int rightHight Height(parent-_right);int diff rightHight - leftHight;if (diff ! parent-_bf || (diff 1 || diff -1)){cout 有错 endl;return false;}return _IsBalanceTree(parent-_left) _IsBalanceTree(parent-_right);}void Inorder(){_Inorder(_root);}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);}
private:Node* _root nullptr;
};//出错用小用例调
void test1()
{int arr[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };int arr2[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVLTreeint, int t;for (auto e : arr){if(e 18){ //调试断点int a 0;}t.insert(make_pair(e, e));t.IsBalanceTree();}t.Inorder();
}//没错用多数据看看能不能过
#include cstdlib
void test2()
{srand(time(NULL));AVLTreeint, int t;for (int i 0; i 100000; i){int num rand() % 10000;t.insert(make_pair(num, num));}t.IsBalanceTree();
}2、红黑树 AVL树因为其严格的平衡导致它因为大量的旋转导致效率相较红黑树低。 红黑树不要求严格平衡它为每个结点加上颜色区分使得它趋向于平衡。它有着以下规定。
根节点必须是黑色。根节点颜色要么是红色要么是黑色。红色结点不能连续。也就是如果一个结点是红的其两个子结点都是黑的每条路径下的黑色结点树要一样。叶子结点都是黑色结点这里叶子结点代表NULL结点 可能概念理解起来很抽象我们通过代码一步步来。 首先搭建红黑树的框架。 大致和AVL树一样只不过没有平衡因子换成了颜色。
#include iostream
#include assert.h
using namespace std;enum Color { RED, BLACK };templateclass K, class V
struct RBTreeNode
{struct RBTreeNodeK, V* _left;struct RBTreeNodeK, V* _right;struct RBTreeNodeK, V* _parent;pairK, V _kv;Color _col;RBTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(BLACK){}
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:
private:Node* _root nullptr;
};2.1 红黑树的插入 1、首先如果根是空新建的结点一定是黑色结点。这很好理解。 2、那么如果是后面创建的结点是黑色还是红色呢 2.1 如果是黑色结点那么想象一下给某个路径添加一个黑色结点使得这个路径的黑结点数量和其他路径不同直接导致整个树不满足红黑树条件直接破坏整个红黑树。 2.2 如果是红色结点最差只会出现两个红色结点相连的情况只影响这个子树。 所以综上选择影响最少的选择创建红色结点。 3、插入前面和搜索树一样得先确认插入的位置以及和父节点链接。 4、调整红黑树 除此以外当然还有翻转的另一类情况。 bool insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* cur _root;Node* parent _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;}}cur new Node(kv);cur-_col RED;if (parent-_kv.first cur-_kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}//调整//parent为红代表插入的子节点也为红需要调整。while (parent parent-_col RED){Node* grandparent parent-_parent;//首先是第一类父亲结点在祖父结点左边叔叔结点在右边的一类情况。if (parent grandparent-_left){Node* uncle grandparent-_right;if (uncle uncle-_col RED){//第一种情况 叔叔结点存在且为红色parent-_col BLACK;uncle-_col BLACK;grandparent-_col RED;//向上调整根节点的情况可以跑完整个调整再设置_root-_col BLACK;cur grandparent;parent cur-_parent;}else{//这一类是叔叔结点不存在以及存在为黑色//因为处理方法都是一样的所以只要再区分直线型和折线型。if (parent-_right cur){//折线的情况RotateL(parent);RotateR(grandparent);cur-_col BLACK;grandparent-_col RED;}else{//直线的情况RotateR(grandparent);parent-_col BLACK;grandparent-_col RED;}break;}}else{//这一类是上面翻转一样的处理但注意方向Node* uncle grandparent-_left;if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandparent-_col RED;cur grandparent;parent cur-_parent;}else{if (parent-_right cur){RotateL(grandparent);parent-_col BLACK;grandparent-_col RED;}else{RotateR(parent);RotateL(grandparent);cur-_col BLACK;grandparent-_col RED;}break;}}}//最后确保根节点为黑。_root-_col BLACK;return true;}//剩下左右旋转的代码和AVL中的一样。如果记忆红黑树的情况个人方式 首先要记得红黑树的特性根一定是黑结点想清楚为什么插入要插红结点这样能更情况红黑树的特性。 像情况一的推理一样先插入黑色的根节点再插入红结点层序插入直到出现问题此时面对第一个情况叔叔结点存在并且为红色。 然后考虑叔叔结点为黑和不存在的情况因为要旋转再根据AVL树中记忆的两个情况推出除了直线型情况还有折线型情况。 2.2 红黑树的测试 在测试中需要判断的 1. 根要为黑结点。 2.判断父子结点不能都为红 3.确保每条路径的黑结点数相同这里通过先计算一条路径的黑结点数再和每一条路径比对 bool Check(Node* proot, int count, int ref){if (proot nullptr){//检查黑结点if (count ! ref){cout 出现路径黑结点树不同 endl;return false;}return true;}Node* parent proot-_parent;if (parent (parent-_col RED proot-_col RED)){cout 出现了连续的红结点 endl;return false;}if (proot-_col BLACK){count 1;}return Check(proot-_left, count, ref) Check(proot-_right, count, ref);}bool IsRBTree(){if (_root nullptr){return true;}if (RED _root-_col){cout 根节点不能为红色 endl;return false;}int ref 0;Node* checkblack _root;while (checkblack){if (BLACK checkblack-_col){ref;}checkblack checkblack-_left;}return Check(_root, 0, ref);}本节完~
