电商网站方案建设,石家庄商城网站搭建多少钱,深圳 福田网站建设,移动端优秀网站绪论 “生命有如铁砧#xff0c;愈被敲打#xff0c;愈能发出火花。——伽利略”#xff1b;本章主要是数据结构 二叉树的进阶知识#xff0c;若之前没学过二叉树建议看看这篇文章一篇掌握二叉树#xff0c;本章的知识从浅到深的对搜索二叉树的使用进行了介绍和对其底层… 绪论 “生命有如铁砧愈被敲打愈能发出火花。——伽利略”本章主要是数据结构 二叉树的进阶知识若之前没学过二叉树建议看看这篇文章一篇掌握二叉树本章的知识从浅到深的对搜索二叉树的使用进行了介绍和对其底层逻辑的实现进行了讲解希望能对你有所帮助。话不多说安全带系好发车啦建议电脑观看。 1.二叉搜索树
1.1二叉搜索树的概念: 二叉搜索树又称二叉排序树/二叉查找树**它或者是一棵空树。二叉搜索树还有二叉树的性质不同的是其性质有 1. 大于子树根节点的值存在根节点的右子树 2. 小于子树根节点的值存在根节点的左子树 3. 左右子树都是二叉搜索树 换种说法若它的左子树不为空则左子树上所有节点的值都小于根节点的值、若它的右子树不为空则右子树上所有节点的值都大于根节点的值。 1.2二叉树搜索树一些常用功能基本功能
1.2.1 插入数据 有了前面的二叉搜索树的性质后能很好的想到其插入的实现只不过其中会有一些小的细节需要注意 主要是判断当前子树根节点的值和传进来的值进行比较然后当走到为空时表示就是为要插入的位置 注意细节 当根节点为空时修改根节点即可。我们需要记录父节点然后链接父子节点。 具体见下面代码
bool Insert(const K key, const V val)
{if (_root nullptr){_root new Node(key);return true;}Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){return false;//不插入相同的值}else if (cur-_key key){parent cur;cur cur-_left;}else{parent cur;cur cur-_right;}}//当循环结束表示已经到了所要插入节点的位置cur new Node(key);if (parent-_key key){parent-_left cur;}else{parent-_right cur;}return true;
}1.2.2 删除数据 对于删除数据来说有几个不同的情况 当删除节点没有左右节点时我们直接将其节点删除即可 当删除节点只有左节点/右节点时 将这个左节点/右节点链接到删除节点的父节点当删除节点用同时有两个节点 使用替换删除法找到删除节点左子树的最右节点最大节点/删除节点右子树的最左节点最小节点后替换到删除的节点后删除不过删除的时候要注意链接2 注意假如交换的节点有子树那么需要注意将其链接到交换节点的父节点 此处可以把1和2情况并到一起写即当有左为空/右为空时不管右/左为不为空都连接到其父节点 具体代码实现
bool Erase(const K key)
{Node* parent nullptr, * child nullptr;//删除节点的父亲Node* cur _root;//所要删除的节点while (cur){if (cur-_key key) //找到删除节点{//可以把左右为空和 左或右不为空写在一起if (cur-_left nullptr)//当其左边为空时{if (cur _root){_root cur-_right;}else{//即当有左为空时不管删除节点的右为不为空都直接连接到其父节点if (parent-_left cur)//判断在父节点的左边还是右边{parent-_left cur-_right;}else// if (parent-_right cur){parent-_right cur-_right;}}delete cur;}else if (cur-_right nullptr)//当其右边为空时{if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur;}else// if (parent-_right cur){parent-_right cur;}}delete cur;}else//当左右同时不为空时{//找到删除节点左子树的最大值/右子树的最小值、与删除节点交换//找到左子树的最右节点Node* tmp cur-_left;//最右节点Node* p cur;//最右节点的父节点while (tmp-_right){p tmp;tmp tmp-_right;}//父节点链接 最右节点的左节点if (p-_right tmp) {p-_right tmp-_left;}else {p-_left tmp-_left;}swap(tmp-_key, cur-_key);//交换后删除即可delete tmp;}return true;}else if (cur-_key key)//找不到继续循环{parent cur;cur cur-_left;}else{parent cur;cur cur-_right;}}return false;
}1.2.3查找数据 直接利用二叉搜索树的性质即可很好的写出查找 通过大的在右小的在左的性质就能最多树的层数次就能找到 若找不到则就会找到空的位置处 Node* Find(const K key)
{Node* cur _root;while (cur){if (cur-_key key){return cur;//找到返回该节点}else if (cur-_key key){cur cur-_left;}else{cur cur-_right;}}return nullptr;//找不到则返回nullptr
}1.3二叉树搜索树基本功能用递归式实现
从代码直接分析若有啥问题可以评论提出喔
1.3.1插入
bool _InsertR(Node* root, const K key)//递归式插入 Recursion
{if (root nullptr){//此处为引用也就是别名当修改root就其实就是修改到了树就不用链接了root new Node(key);return true;}if (root-_key key)//若相等则表示已经插入过了那么返回错误{return false;}else if (root-_key key)//当root值大于key时往左走{return _InsertR(root-_left, key);}else//当root值小于key时往右走{return _InsertR(root-_right, key);}
}1.3.2删除
bool _EraseR(Node* root, const K key)
{//同样当左右无节点时直接删除//当只有左或者只有右时链接其右或左到祖先即可//当同时有左右子树时交换删除if (root nullptr) {//为空表示不存在返回空return false;}if (root-_key key)//当root值大于key时往左走{return _EraseR(root-_left, key);}else if (root-_key key)//当root值小于key时往右走{return _EraseR(root-_right, key);}else//找到后{if (root-_left nullptr){Node* tmp root;root root-_right;//因为root是引用所以当修改root后会影响到整棵树delete tmp;//再将原本的root给释放了return true;}else if (root-_right nullptr){Node* tmp root;root root-_left;//因为root是引用所以当修改root后会影响到整棵树delete tmp;//再将原本的root给释放了return true;}else{Node* tmp root-_left;//找到左子树的最大值最右值while (tmp-_right){tmp tmp-_right;}swap(tmp-_key, root-_key);//交换return _EraseR(root-_left, key);//通过递归删除把key删除里面就包含了链接}}
}1.3.3查找
此处如果你已经理解了上面的那么这里就非常简单了就不过诉了
Node* _FindR(Node* root, const K key)
{if (root nullptr){return nullptr;}if (root-_key key){return _FindR(root-_right, key);}else if (root-_key key){return _FindR(root-_left, key);}else{return root;}
}1.4二叉搜索树的源码
如果是要学习的话建议一定要将整体的结构框架理清楚了下面是二叉搜索树的整体代码包括了构造函数、析构函数、以及一些还没交代的函数。
templateclass K
struct BSTreeNode
{BSTreeNode(const K key):_key(key), _left(nullptr), _right(nullptr){}K _key;BSTreeNodeK* _left;BSTreeNodeK* _right;
};templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public:BSTree() default;~BSTree(){_Destory(_root);}//BSTree(const BSTreeK t)//{// _Copy(t._root);//}BSTree(const BSTreeK t){_root _Copy(t._root);}BSTreeK operator(BSTreeK t){//_Destory(_root);//_Copy(t._root);swap(_root, t._root);//现代写法return *this;}void InOrder(){_InOrder(_root);}bool Insert(const K key){if (_root nullptr){_root new Node(key);return true;}Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){return false;//不插入相同的值}else if (cur-_key key){parent cur;cur cur-_left;}else{parent cur;cur cur-_right;}}//当循环结束表示已经到了所要插入节点的位置cur new Node(key);if (parent-_key key){parent-_left cur;}else{parent-_right cur;}return true;}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_key key){return cur;//不插入相同的值}else if (cur-_key key){cur cur-_left;}else{cur cur-_right;}}return nullptr;}//替换法 删除//找到删除节点的左子树的最大值(最左子树的右节点)/右子树的最小值(右子树的最左节点)后与删除的位置进行交换bool Erase(const K key){Node* parent nullptr, * child nullptr;//删除节点的父亲Node* cur _root;//所要删除的节点while (cur){if (cur-_key key){//if (cur-_left nullptr // cur-_right nullptr)//{// delete cur;//}//else if (del-_left del-_right)//{// //MaxNode(del-_left);//左子树的最大值// Node* min MinNode(del-_right); //右子树的最小值// swap(del, min);// delete del;//}//可以把左右为空和 左或右不为空写在一起if (cur-_left nullptr){if (cur _root){_root cur-_right;}else{if (parent-_left cur){parent-_left cur-_right;}else// if (parent-_right cur){parent-_right cur-_right;}}delete cur;}else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur;}else// if (parent-_right cur){parent-_right cur;}}delete cur;}else{//找到删除节点左子树的最大值/右子树的最小值、与删除节点交换//交换后删除即可Node* tmp cur-_left;Node* p cur;while (tmp-_right){p tmp;tmp tmp-_right;}if (p-_right tmp) {p-_right tmp-_left;}else {p-_left tmp-_left;}swap(tmp-_key, cur-_key);delete tmp;}return true;}else if (cur-_key key){parent cur;cur cur-_left;}else{parent cur;cur cur-_right;}}return false;}bool InsertR(const K key)//递归式插入 Recursion{return _InsertR(_root, key);}Node* FindR(const K key){return _FindR(_root, key);}bool EraseR(const K key){return _EraseR(_root, key);}private:void _Destory(Node* root){if (root nullptr) return;_Destory(root-_left);_Destory(root-_right);delete root;}//void _Copy(Node* root)//{// if (root nullptr) return;// _InsertR(_root, root-_key);// _Copy(root-_left);// _Copy(root-_right);//}Node* _Copy(Node* root){if (root nullptr)return nullptr;Node* newRoot new Node(root-_key);newRoot-_left _Copy(root-_left);newRoot-_right _Copy(root-_right);return newRoot;}void _InOrder(Node* root){if (root nullptr) return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}//判断root-_key 与 keybool _InsertR(Node* root, const K key)//递归式插入 Recursion{if (root nullptr){root new Node(key);//此处为引用也就是别名当修改root就其实就是修改到了树return true;}if (root-_key key){return false;}else if (root-_key key){return _InsertR(root-_left, key);}else{return _InsertR(root-_right, key);}}Node* _FindR(Node* root, const K key){if (root nullptr){return nullptr;}if (root-_key key){return _FindR(root-_right, key);}else if (root-_key key){return _FindR(root-_left, key);}else{return root;}}bool _EraseR(Node* root, const K key){//同样当左右无节点时直接删除//当只有左或者只有右时链接其右或左到祖先即可//当同时有左右子树时交换删除if (root nullptr) {return false;}if (root-_key key){return _EraseR(root-_left, key);}else if (root-_key key){return _EraseR(root-_right, key);}else{if (root-_left nullptr){Node* tmp root;root root-_right;//因为root是引用所以当修改root后会影响到整棵树delete tmp;//再将原本的root给释放了return true;}else if (root-_right nullptr){Node* tmp root;root root-_left;//因为root是引用所以当修改root后会影响到整棵树delete tmp;//再将原本的root给释放了return true;}else{Node* tmp root-_left;//找到左子树的最大值最右值while (tmp-_right){tmp tmp-_right;}swap(tmp-_key, root-_key);//交换return _EraseR(root-_left, key);//通过递归删除把key删除里面就包含了链接}}}Node* _root;
};1.5二叉搜索树的应用 k模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。如:给一个单词word判断该单词是否拼写正确。KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见英汉词典就是英文与中文对应关系Englishmeaning、或者统计个数对应的就是元素和个数的关系ele,count。 在上面我们写的是就是k模型下面我们将其修改为kv模型(对于k模型来说大概的都不需要修改只有一部分需要简单修改) 具体代码为
templateclass K, class V
struct BSTreeNode
{BSTreeNode(const K key, const V val):_key(key), _val(val), _left(nullptr), _right(nullptr){}K _key;V _val;BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;
};templateclass K, class V
class BSTree
{typedef BSTreeNodeK, V Node;
public:BSTree():_root(nullptr){}void InOrder(){_InOrder(_root);}bool Insert(const K key, const V val){//1. 当根节点为空时修改根节点即可。if (_root nullptr){_root new Node(key, val);return true;}//2. 我们需要记录父节点然后链接父子节点。Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){return false;//不插入相同的值}else if (cur-_key key){parent cur;cur cur-_left;}else{parent cur;cur cur-_right;}}//当循环结束表示已经到了所要插入节点的位置cur new Node(key, val);if (parent-_key key){parent-_left cur;}else{parent-_right cur;}return true;}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_key key){return cur;//不插入相同的值}else if (cur-_key key){cur cur-_left;}else{cur cur-_right;}}return nullptr;}//替换法 删除//找到删除节点的左子树的最大值(最左子树的右节点)/右子树的最小值(右子树的最左节点)后与删除的位置进行交换bool Erase(const K key){Node* parent nullptr, * child nullptr;//删除节点的父亲Node* cur _root;//所要删除的节点while (cur){if (cur-_key key) //找到删除节点{if (cur-_left nullptr)//当其左边为空时{if (cur _root){_root cur-_right;}else{//即当有左为空时不管删除节点的右为不为空都直接连接到其父节点if (parent-_left cur)//判断在父节点的左边还是右边{parent-_left cur-_right;}else// if (parent-_right cur){parent-_right cur-_right;}}delete cur;}else if (cur-_right nullptr)//当其右边为空时{if (cur _root){_root cur-_left;}else{if (parent-_left cur){parent-_left cur;}else// if (parent-_right cur){parent-_right cur;}}delete cur;}else//当左右同时不为空时{//找到删除节点左子树的最大值/右子树的最小值、与删除节点交换//找到左子树的最右节点Node* tmp cur-_left;//最右节点Node* p cur;//最右节点的父节点while (tmp-_right){p tmp;tmp tmp-_right;}//父节点链接 最右节点的左节点if (p-_right tmp) {p-_right tmp-_left;}else {p-_left tmp-_left;}swap(tmp-_key, cur-_key);//交换后删除即可delete tmp;}return true;}else if (cur-_key key){parent cur;cur cur-_left;}else{parent cur;cur cur-_right;}}return false;}private:void _InOrder(Node* root){if (root nullptr) return;_InOrder(root-_left);cout root-_key - root-_val ;_InOrder(root-_right);}Node* _root nullptr;
};英汉词典实现
int main()
{kv::BSTreestring, string dict;//插入单词dict.Insert(sort, 种类);dict.Insert(left, 左边);dict.Insert(right, 右边);dict.Insert(insert, 插入);dict.Insert(key, 钥匙);string str;while (cinstr)//输入所要查找的单词{kv::BSTreeNodestring, string* ret dict.Find(str);if (ret){cout ret-_val endl;}else{cout 不存在 endl;}}return 0;
}计数实现
int main()
{string arr[] { 苹果, 苹果,梨子, 香蕉, 苹果, 桃子, 哈密瓜, 梨子, 苹果, 西瓜, 哈密瓜, 苹果, 桃子 };kv::BSTreestring, int countTree;for (auto e : arr){kv::BSTreeNodestring, int* ret countTree.Find(e);if (ret nullptr){countTree.Insert(e, 1);}else{ret-_val;}}countTree.InOrder();return 0;
}2.键值对、关联式容器、序列式容器 在初阶阶段我们已经接触过STL中的部分容器比如vector、list、deque、forward_list(C11)等这些容器统称为序列式容器。因为其底层为线性序列的数据结构里面存储的是元素本身。关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高。 键值对用来表示具有一 一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。 键值对可以用一个新的变量 pairK,V 表示 其结构可以看成 template class T1, class T2
struct pair
{T1 first;T2 second;pair(): first(T1()), second(T2()){}pair(const T1 a, const T2 b): first(a), second(b){}
};有了上面这个类我们可以定义一个变量为 pairint,int _kv 这样就能调用其内部的元素_kv.first代表第一个元素K、_kv.second表示第二个元素 或者为pairint,int* _kv,_kv-first同样代表第一个元素、_kv-second表示第二个元素
3.AVL树
3.1AVL树的概念 当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。 一棵AVL树或者是空树或者是具有以下性质的二叉搜索树 它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1-1/0/1 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2n)搜索时间复杂度O( l o g 2 n log_2 n log2n)。 3.2AVL树的构造 AVL树是一个三叉树他的节点有三个指针分别指向左孩子、右孩子、父节点还有一个值这个值是kv模型的和一个平衡因子。 具体如下
templateclass K, class V
struct AVLTreeNode
{AVLTreeNode(const pairK,V kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}AVLTreeNodeK,V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf; // 节点的平衡因子 balance factor
};3.3AVL树的基本功能
3.3.1平衡因子 在某个根上其左右子树的高度差左子树的高度- 右子树的高度 例子直接通过下面的图来理解
上图中在原图上的左子树的子叶增加元素可增加该左子树的左边或者右边 一开始可以看到所有的根的平衡因子都为0因为左右子树的高度一样。
当在最左边加上一个节点后其平衡被打破为-1根的左子树增加一个(所以根的右子树-左子树 -1)对于该左子树来说也是其左子树增加所以同样的平衡变成 -1当在左子树的最右加上一个节点后对于根来说仍然是左子树有变高所以还是-1而对于该左子树来说那就是其右子树增加了那么右子树-左子树1
在上面插入新节点的例子中仍然满足平衡二叉树的平衡条件左右孩子的高度差不超过1如果出现平衡因子出现问题的话那就需要去旋转具体请继续往下看
3.3.2插入以及插入中的左旋、右旋、左右双旋、右左双旋的问题
AVL树的插入本质上还是搜索二叉树的插入但因为加入了平衡因子的所就可能出现一下问题当插入一个节点后其平衡因子只可能变成 10-1-22 那么这几个平衡因子产生的情况又能分为几种情况 附下面的例子中的长方框表示着子树而小框就表示新增的节点 当平衡因子变成了0 那么表示新增节点后使平衡那么其实是不用做什么的因为该子树的层数并没有增加仅仅只需把该子树的平衡因子改成0即可。 当平衡因子变成了1/-1那么表示该子树的层数发生了改变那么连锁的也会导致上方的祖先的平衡因子发生改变。 如何向上调整改变cur和parent的关系即可cur parentparent parent-parent 当平衡因子变成-2/2此时表示在原本高的一方又加了一个节点那么此时因为平衡因子的错误那么需要去旋转来解决这个问题。 旋转又分为多种情况 附在下面多以cur和parent的关系为一棵子树来看。 1.右旋当在左子树的左边新增元素左左此时因为原本为-1的p再在左边加元素后就变成了-2此时就需要对cur进行右旋方法为将把cur的右子树链接成parent再把parent的左子树换成cur的右子树此时就断开了链接具体如下图 旋转后cur p 0 代码
void RotateR(Node* parent)
{Node* SubL parent-_left;//此处就为 curNode* SubLR SubL-_right;//parent的左换成cur的右parent-_left SubLR;//把cur的右孩子换成parentSubL-_right parent;//注意还要修改其父指针Node* Ppnode parent-_parent;parent-_parent SubL;if (SubLR)//cur的右边可能为空SubLR-_parent parent;if (_root parent)//如果parent为根节点则需要把subR改变成根节点并且其父亲为nullptr{_root SubL;SubL-_parent nullptr;}else{//同时还要考虑父亲 是祖先的左或右if (Ppnode-_left parent){Ppnode-_left SubL;}else{Ppnode-_right SubL;}SubL-_parent Ppnode;}SubL-_bf 0;parent-_bf 0;
}2.左旋当在右子树的右边新增节点右右同样的就是 p就将变成2此时要用对cur左旋方法为将cur的左子树断开链接为p再把p的右子树断开链接成cur的左子树 旋转后cur p 0 代码
void RotateL(Node* parent)
{Node* SubR parent-_right;//此处就为 curNode* SubRL SubR-_left;//parent的右换成cur的左parent-_right SubRL;//把cur的左孩子换成parentSubR-_left parent;Node* Ppnode parent-_parent;//注意 还要修改其父指针parent-_parent SubR;if (SubRL)//右边可能为空SubRL-_parent parent;if (_root parent)//如果parent为根节点则需要把subR改变成根节点并且其父亲为nullptr{_root SubR;SubR-_parent nullptr;}else{//同时还要考虑父亲 是祖先的左或右if (Ppnode-_left parent){Ppnode-_left SubR;}else{Ppnode-_right SubR;}SubR-_parent Ppnode;}SubR-_bf 0;parent-_bf 0;
}3.左右双旋此处我们先定义pparent、subLparent的左子树、subLRsubL的右子树当在左子树的右边新增节点左右此时我们先对 subL和subLR 组成的子树进行左旋后再对p和subLR组成的子树进行右旋。其中有两种可能当插入到subLR的左边/subLR的右边时他们对平衡因子的影响是不一样的我们需要分开讨论具体见下图 旋转后当在subLR的左边插入的话 subLR subL 0 p 1若在subLR的右边插入的话则subLR p 0 subL -1 代码
void RotateLR(Node* parent)
{Node* subL parent-_left;//此处就为 curNode* subLR subL-_right;int bf subLR-_bf; //先对cur 进行左旋 再对 parent进行右旋RotateL(subL);RotateR(parent);if (bf 0)//自己为新增{parent-_bf subL-_bf subLR-_bf 0;}else if (bf -1){// subRL的左子树新增parent-_bf 1;subLR-_bf 0;subL-_bf 0;}else if (bf 1){// subRL的右子树新增parent-_bf 0;subLR-_bf 0;subL-_bf -1;}else{assert(false);}
}4.右左双旋此处我们先定义pparent、subRparent的右子树、subRLsubR的左子树当在右子树的左边新增节点右左此时我们先对 subR和subRL 组成的子树进行右旋后再对p和subRL组成的子树进行左旋。其中有两种可能当插入到subRL的左边/subRL的右边时他们只是对平衡因子的影响是不一样的我们需要分开讨论具体见下图 旋转后当在subLR的左边插入的话 subRL p 0 subR 1若在subLR的右边插入的话则subRL subR 0 p 1 代码
void RotateRL(Node* parent)
{Node* subR parent-_right;//此处就为 curNode* subRL subR-_left;int bf subRL-_bf;//先对cur 进行左旋 再对 parent进行右旋RotateR(subR);RotateL(parent);if (bf 0)//自己为新增{parent-_bf subR-_bf subRL-_bf 0;}else if (bf -1){// subRL的左子树新增subR-_bf 1;subRL-_bf 0;parent-_bf 0;}else if (bf 1){// subRL的右子树新增subR-_bf 0;subRL-_bf 0;parent-_bf -1;}else{assert(false);}
}对于插入函数代码
bool Insert(const pairK,V kv)
{//平衡二叉树 左子树的值都小于根的值 、 右子树的值都大于根的值Node* cur _root;Node* parent nullptr;if (!_root) {_root new Node(kv);return true;}//1.找到所要插入的位置while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else//若已经存在则返回插入失败{return false;}}//2. 确立位置后 new出新节点在cur处然后在建立 链接关系//关系// cur 没有左右为null// 主要是改变其_parent 和 父亲的left/right, 而要去判断cur 在 _parent的左还是右 通过比较kv.first 和 父亲的kv.first的值//此处parent 为其 父亲cur new Node(kv);if (parent-_kv.first kv.first){parent-_left cur;//注意此处也要改变 cur 的 _parentcur-_parent parent;}else{parent-_right cur;cur-_parent parent;}while (parent){//建立链接后因为有了新插入的节点 故需要 先修改平衡因子//某个根节点的平衡因子为 右孩子的_bf平衡因子 - 左孩子的_bf//插入后 父亲可能的情况为//-2: 左边高插到了左//-1: 平衡到 插左边 //0 : 1 / -1 - 插到左或右 // //1 : 平衡插右边//2 : 右 右if (cur parent-_left){parent-_bf--;}else if (cur parent-_right){parent-_bf;}//分析不同的情况对应的修改平衡因子if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf -1)//当父亲的平衡因子为1表示该子树的层数有了增加但任然是满足AVL树的条件{ //因为子树层数的增加则对应的会影响到祖先故需要向上修改祖先的平衡因子cur parent;parent parent-_parent;}else if(parent-_bf 2 || parent-_bf -2)//当父亲的bf 为 2/-2 时则已经影响到了AVL树的平衡故需要去通过旋转来保证AVL树{if (parent-_bf -2 cur-_bf -1)//左左{//进行对父节点的右旋RotateR(parent);}if (parent-_bf -2 cur-_bf 1)//左右{//先右旋再左旋RotateLR(parent);}if (parent-_bf 2 cur-_bf 1)//右右{//左旋RotateL(parent);}if (parent-_bf 2 cur-_bf -1)//右左{//先左旋再右旋RotateRL(parent);}//注意此处当旋转完后就直接break跳出循环了因为其在内部已经将平衡因子调整好了不用再考虑祖先平衡因子问题// 1、旋转让这颗子树平衡了// 2、旋转降低了这颗子树的高度恢复到跟插入前一样的高度所以对上一层没有影响不用继续更新break;}else {assert(0);}}return true;
}3.4AVL树的源码
在其中还包括了一些扩展功能
求树的高度_Height。判断而AVL的每个节点是否满足平衡条件IsBalance这个函数是用来测试该AVL树是否满足条件的实现原理为遍历整个二叉树并且在过程中判断其左右子树的差是否满足平衡条件。
#pragma once
#includeiostream
#includeassert.h
using namespace std;templateclass K, class V
struct AVLTreeNode
{AVLTreeNode(const pairK,V kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}AVLTreeNodeK,V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf; // 节点的平衡因子 balance factor
};// AVL: 二叉搜索树 平衡因子的限制
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK,V Node;//通过模板将node确定类型
public:AVLTree():_root(nullptr){}// 在AVL树中插入值为data的节点bool Insert(const pairK,V kv){//平衡二叉树 左子树的值都小于根的值 、 右子树的值都大于根的值Node* cur _root;Node* parent nullptr;if (!_root) {_root new Node(kv);return true;}//1.找到所要插入的位置while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else//若已经存在则返回插入失败{return false;}}//2. 确立位置后 new出新节点在cur处然后在建立 链接关系//关系// cur 没有左右为null// 主要是改变其_parent 和 父亲的left/right, 而要去判断cur 在 _parent的左还是右 通过比较kv.first 和 父亲的kv.first的值//此处parent 为其 父亲cur new Node(kv);if (parent-_kv.first kv.first){parent-_left cur;//注意此处也要改变 cur 的 _parentcur-_parent parent;}else{parent-_right cur;cur-_parent parent;}while (parent){//建立链接后因为有了新插入的节点 故需要 先修改平衡因子//某个根节点的平衡因子为 右孩子的_bf平衡因子 - 左孩子的_bf//插入后 父亲可能的情况为//-2: 左边高插到了左//-1: 平衡到 插左边 //0 : 1 / -1 - 插到左或右 // //1 : 平衡插右边//2 : 右 右if (cur parent-_left){parent-_bf--;}else if (cur parent-_right){parent-_bf;}//分析不同的情况对应的修改平衡因子if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf -1)//当父亲的平衡因子为1表示该子树的层数有了增加但任然是满足AVL树的条件{ //因为子树层数的增加则对应的会影响到祖先故需要向上修改祖先的平衡因子cur parent;parent parent-_parent;}else if(parent-_bf 2 || parent-_bf -2)//当父亲的bf 为 2/-2 时则已经影响到了AVL树的平衡故需要去通过旋转来保证AVL树{if (parent-_bf -2 cur-_bf -1)//左左{//进行对父节点的右旋RotateR(parent);}if (parent-_bf -2 cur-_bf 1)//左右{//先右旋再左旋RotateLR(parent);}if (parent-_bf 2 cur-_bf 1)//右右{//左旋RotateL(parent);}if (parent-_bf 2 cur-_bf -1)//右左{//先左旋再右旋RotateRL(parent);}//注意此处当旋转完后就直接break跳出循环了因为其在内部已经将平衡因子调整好了不用再考虑祖先平衡因子问题// 1、旋转让这颗子树平衡了// 2、旋转降低了这颗子树的高度恢复到跟插入前一样的高度所以对上一层没有影响不用继续更新break;}else {assert(0);}}return true;}// AVL树的验证bool IsBalance(){return _IsBalance(_root);}private:// 根据AVL树的概念验证pRoot是否为有效的AVL树bool _IsBalance(Node* root){//主要是平衡因子的判断//此处不同用bf 此处应该用height来确定bf是否正确if (!root) return true;int leftbf _Height(root-_left);int rightbf _Height(root-_right);if (rightbf - leftbf ! root-_bf) {cout 平衡因子出问题 endl;}if (abs(rightbf - leftbf) 1)return false;return _IsBalance(root-_left) _IsBalance(root-_right);}size_t _Height(Node* root){if (!root) return 0;int LeftchildTreeHeight _Height(root-_left);int RightchildTreeHeight _Height(root-_right);return LeftchildTreeHeight RightchildTreeHeight ? LeftchildTreeHeight 1 : RightchildTreeHeight 1;}// 右单旋// 把cur的右孩子换成parentparent的左换成cur的右void RotateR(Node* parent){Node* SubL parent-_left;//此处就为 curNode* SubLR SubL-_right;//parent的左换成cur的右parent-_left SubLR;//把cur的右孩子换成parentSubL-_right parent;//注意还要修改其父指针Node* Ppnode parent-_parent;parent-_parent SubL;if (SubLR)//cur的右边可能为空SubLR-_parent parent;if (_root parent)//如果parent为根节点则需要把subR改变成根节点并且其父亲为nullptr{_root SubL;SubL-_parent nullptr;}else{//同时还要考虑父亲 是祖先的左或右if (Ppnode-_left parent){Ppnode-_left SubL;}else{Ppnode-_right SubL;}SubL-_parent Ppnode;}SubL-_bf 0;parent-_bf 0;}// 左单旋// 同理void RotateL(Node* parent){Node* SubR parent-_right;//此处就为 curNode* SubRL SubR-_left;//parent的右换成cur的左parent-_right SubRL;//把cur的左孩子换成parentSubR-_left parent;Node* Ppnode parent-_parent;//注意 还要修改其父指针parent-_parent SubR;if (SubRL)//右边可能为空SubRL-_parent parent;if (_root parent)//如果parent为根节点则需要把subR改变成根节点并且其父亲为nullptr{_root SubR;SubR-_parent nullptr;}else{//同时还要考虑父亲 是祖先的左或右if (Ppnode-_left parent){Ppnode-_left SubR;}else{Ppnode-_right SubR;}SubR-_parent Ppnode;}SubR-_bf 0;parent-_bf 0;}// 右左双旋void RotateRL(Node* parent){Node* subR parent-_right;//此处就为 curNode* subRL subR-_left;int bf subRL-_bf;//先对cur 进行左旋 再对 parent进行右旋RotateR(subR);RotateL(parent);if (bf 0)//自己为新增{parent-_bf subR-_bf subRL-_bf 0;}else if (bf -1){// subRL的左子树新增subR-_bf 1;subRL-_bf 0;parent-_bf 0;}else if (bf 1){// subRL的右子树新增subR-_bf 0;subRL-_bf 0;parent-_bf -1;}else{assert(false);}}// 对于在 左子树的 右边加元素的情况 用左右双旋void RotateLR(Node* parent){Node* subL parent-_left;//此处就为 curNode* subLR subL-_right;int bf subLR-_bf; //先对cur 进行左旋 再对 parent进行右旋RotateL(subL);RotateR(parent);if (bf 0)//自己为新增{parent-_bf subL-_bf subLR-_bf 0;}else if (bf -1){// subRL的左子树新增parent-_bf 1;subLR-_bf 0;subL-_bf 0;}else if (bf 1){// subRL的右子树新增parent-_bf 0;subLR-_bf 0;subL-_bf -1;}else{assert(false);}}
private:Node* _root;
};4.红黑树
4.1红黑树的概念 红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 4.2红黑树的性质
红黑树有的性质
每个节点不是黑色就是红色树的根节点必须是黑色如果根节点为红色那么其左右子树必须为黑色节点不能出现连续的红色节点每条路径的黑色节点个数是一样的
注意其中路径要包括到null节点处的路径 红黑树确保没有一条路径会比其他路径长出俩倍 最短路径是一条全黑节点的路径 最长路径是在有相同个黑色节点的前提下穿插着红色节点 具体如下图
4.3红黑树结构的定义 结构是由三叉链包括了左右父链接、pairK,V值颜色组成。 enum Color
{BLACK,RED
};templateclass K , class V
struct RBTreeNode {RBTreeNodeK,V* _left nullptr;RBTreeNodeK,V* _right nullptr;RBTreeNodeK,V* _parent nullptr;pairK, V _kv;Color _col RED;//默认生成的节点颜色是红色RBTreeNode(const pairK,V kv):_kv(kv){}
};4.3红黑树结构的基本功能
4.3.1插入数据 插入数据此处的红黑树是在cur、parent、grandfather、uncle中来看后面在这个颗树中主要分为三种情况 在g的左边插入其中默认插入的节点是红色节点、旋转和AVL树是一样的时 当p为红g、u为黑时插入节点cur。此时把p、u改成黑色将g改成红色再向上调整把cur g p g-p 当p为红g为黑、u存在且为黑时插入新节点。 当在左边插入时就先对局部左边进行变色情况一变色后向上调整c、p、g、u再进行右旋在向上调整后的树上后再变色将p变成黑、g变成黑。 当在右边插入时同样先变色情况一后向上调整再进行先左旋和右旋后再进行变色将g变成红色、c变成黑色。 3. 当g为黑p、c也为红、u为空时 此时先左旋变色p变成黑色、g变成红色 在g的右边插入时是一样的就不过诉了 下面通过代码来看
// 在红黑树中插入值为data的节点插入成功返回true否则返回false
// 注意为了简单起见本次实现红黑树不存储重复性元素
bool Insert(const pairK,V kv)
{//此处和AVL平衡二叉树的性质一样找到所要插入节点的位置 大的在右 、 小的在左Node* parent nullptr;Node* cur _root;if (cur nullptr){_root new Node(kv);_root-_col BLACK;return true;}//找到插入的位置while (cur)//当为null时表示此处就是要插入的位置{if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else {return false;}}//找到位置后插入cur new Node(kv);//建立新节点//建立链接if (parent-_kv.first kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//插入时要判断插入后是否会导致不平衡对于红黑树来说主要问题有//1. 不能出现连续的红节点//2. 最长路径不超过最短路径的两倍//判断是否需要变色/旋转// //1.当父亲节点为黑色时当新增了一个红色节点时就结束插入了// //2.当父为红时// 情况一(仅变色即可)当parent为红 grandfather为黑 uncle存在且为黑 插入一个新节点// //while (parent parent-_col RED){Node* g parent-_parent;//grandfatherif (g-_left parent){Node* u g-_right;//uncleif (u u-_col RED)//u存在且为红{//变色即可u-_col parent-_col BLACK;g-_col RED;//向上调整cur g;parent g-_parent;//当g 的 父亲为黑时或者为null时停止调整}else //u不存在或者为黑{if (cur parent-_left)//此处u不存在和当插入节点在左边时的情况一样直接右旋加变色即可{//旋转加变色RotateR(g);parent-_col BLACK;g-_col RED;}else{//旋转加变色RotateL(parent);RotateR(g);cur-_col BLACK;g-_col RED;}}}else{Node* u g-_left;//uncleif (u u-_col RED)//u存在且为红{//变色即可u-_col parent-_col BLACK;g-_col RED;//向上调整cur g;parent g-_parent;//当g 的 父亲为黑时或者为null时停止调整}else //u不存在或者为黑{if (cur parent-_right)//此处u不存在和当插入节点在左边时的情况一样直接右旋加变色即可{RotateL(g);parent-_col BLACK;g-_col RED;}else{RotateR(parent);RotateL(g);cur-_col BLACK;g-_col RED;}}}}_root-_col BLACK;return true;
}4.3.判断红黑树的正确性 判断红黑树的正确性主要还是在于其性质是否满足 主要判断下 根节点是否为黑是否出现连续的红色节点最长路径有没有超过最短路径的两倍每条路径的黑色节点是否一样 有了这些目标后设计代码通过注释来解释
bool IsValidRBTRee()
{if (_root nullptr) return true;//此时无节点为真if (_root-_col RED) return false;//根节点只能为黑若为红返回假Node* cur _root;int blackCount 0;//记录一条路径的黑色节点个数while (cur){if (cur-_col BLACK){blackCount;}cur cur-_left;}return _IsValidRBTRee(_root,blackCount,0);
}bool _IsValidRBTRee(Node* root, size_t blackCount, size_t pathBlack)
{if (root nullptr){if (blackCount ! pathBlack)//当为null时表示该路径已经结束那么判断改路径的黑色节点pathblack 和其他路径的黑色节点blacCount是否相同{return false;}return true;}if (root-_col RED){if (root-_left root-_right (root-_left-_col RED || root-_right-_col RED)){cout 有连续的红色节点 endl;return false;}}if (root-_col BLACK){pathBlack;//某条路径的黑节点个数}//前序遍历return _IsValidRBTRee(root-_left, blackCount, pathBlack) _IsValidRBTRee(root-_right, blackCount, pathBlack);
}4.4红黑树的源码
#pragma once
#includeiostream
using namespace std;
// 请模拟实现红黑树的插入--注意为了后序封装map和set本文在实现时给红黑树多增加了一个头结点enum Color
{BLACK,RED
};templateclass K , class V
struct RBTreeNode {RBTreeNodeK,V* _left nullptr;RBTreeNodeK,V* _right nullptr;RBTreeNodeK,V* _parent nullptr;pairK, V _kv;Color _col RED;//默认生成的节点颜色是红色RBTreeNode(const pairK,V kv):_kv(kv){}
};templateclass K,class V
class RBTree
{typedef typename RBTreeNodeK,V Node;
public:// 在红黑树中插入值为data的节点插入成功返回true否则返回false// 注意为了简单起见本次实现红黑树不存储重复性元素bool Insert(const pairK,V kv){//此处和AVL平衡二叉树的性质一样找到所要插入节点的位置 大的在右 、 小的在左Node* parent nullptr;Node* cur _root;if (cur nullptr){_root new Node(kv);_root-_col BLACK;return true;}//找到插入的位置while (cur)//当为null时表示此处就是要插入的位置{if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else {return false;}}//找到位置后插入cur new Node(kv);//建立新节点//建立链接if (parent-_kv.first kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//插入时要判断插入后是否会导致不平衡对于红黑树来说主要问题有//1. 不能出现连续的红节点//2. 最长路径不超过最短路径的两倍//判断是否需要变色/旋转// //1.当父亲节点为黑色时当新增了一个红色节点时就结束插入了// //2.当父为红时// 情况一(仅变色即可)当parent为红 grandfather为黑 uncle存在且为黑 插入一个新节点// //while (parent parent-_col RED){Node* g parent-_parent;//grandfatherif (g-_left parent){Node* u g-_right;//uncleif (u u-_col RED)//u存在且为红{//变色即可u-_col parent-_col BLACK;g-_col RED;//向上调整cur g;parent g-_parent;//当g 的 父亲为黑时或者为null时停止调整}else //u不存在或者为黑{if (cur parent-_left)//此处u不存在和当插入节点在左边时的情况一样直接右旋加变色即可{//旋转加变色RotateR(g);parent-_col BLACK;g-_col RED;}else{//旋转加变色RotateL(parent);RotateR(g);cur-_col BLACK;g-_col RED;}}}else{Node* u g-_left;//uncleif (u u-_col RED)//u存在且为红{//变色即可u-_col parent-_col BLACK;g-_col RED;//向上调整cur g;parent g-_parent;//当g 的 父亲为黑时或者为null时停止调整}else //u不存在或者为黑{if (cur parent-_right)//此处u不存在和当插入节点在左边时的情况一样直接右旋加变色即可{RotateL(g);parent-_col BLACK;g-_col RED;}else{RotateR(parent);RotateL(g);cur-_col BLACK;g-_col RED;}}}}_root-_col BLACK;return true;}void Inorder(){_Inorder(_root);cout endl;}//
// // 获取红黑树最左侧节点Node* LeftMost(){Node* cur _root;while (cur){if(cur-_left nullptr){return cur;}cur cur-_left;}return nullptr;}
//
// // 获取红黑树最右侧节点Node* RightMost(){Node* cur _root;while (cur){if (cur-_right nullptr){return cur;}cur cur-_right;}return nullptr;}
//
// // 检测红黑树是否为有效的红黑树注意其内部主要依靠_IsValidRBTRee函数检测// 1.每条路径中的黑色节点个数是否一样// 2.最长路径不超过最短路径的两倍// 3.不能出现连续的红色节点// 4.根节点为黑色//bool IsValidRBTRee(){if (_root nullptr) return true;//此时无节点为真if (_root-_col RED) return false;//根节点只能为黑若为红返回假Node* cur _root;int blackCount 0;//记录一条路径的黑色节点个数while (cur){if (cur-_col BLACK){blackCount;}cur cur-_left;}return _IsValidRBTRee(_root,blackCount,0);}int Height(){if (_root nullptr) return 0;return _Height(_root);}int Size(){if (_root nullptr) return 0;return _Size(_root);}//检测红黑树中是否存在值为data的节点存在返回该节点的地址否则返回nullptrNode* Find(const K val){Node* cur _root;while (cur){if (cur-_kv.first val){return cur;}else if (cur-_kv.first val){cur cur-_left;}else {cur cur-_right;}}return nullptr;}private:int _Size(Node* root){if (root nullptr)return 0;return _Size(root-_left) _Size(root-_right) 1;}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;}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first ;_Inorder(root-_right);}bool _IsValidRBTRee(Node* root, size_t blackCount, size_t pathBlack){if (root nullptr){if (blackCount ! pathBlack)//当为null时表示该路径已经结束那么判断改路径的黑色节点pathblack 和其他路径的黑色节点blacCount是否相同{return false;}return true;}if (root-_col RED){if (root-_left root-_right (root-_left-_col RED || root-_right-_col RED)){cout 有连续的红色节点 endl;return false;}}if (root-_col BLACK){pathBlack;//某条路径的黑节点个数}//前序遍历return _IsValidRBTRee(root-_left, blackCount, pathBlack) _IsValidRBTRee(root-_right, blackCount, pathBlack);}// // 为了操作树简单起见获取根节点//Node* GetRoot();void RotateR(Node* parent){Node* SubL parent-_left;//此处就为 curNode* SubLR SubL-_right;//parent的左换成cur的右parent-_left SubLR;//把cur的右孩子换成parentSubL-_right parent;//注意还要修改其父指针Node* Ppnode parent-_parent;parent-_parent SubL;if (SubLR)//cur的右边可能为空SubLR-_parent parent;if (_root parent)//如果parent为根节点则需要把subR改变成根节点并且其父亲为nullptr{_root SubL;SubL-_parent nullptr;}else{//同时还要考虑父亲 是祖先的左或右if (Ppnode-_left parent){Ppnode-_left SubL;}else{Ppnode-_right SubL;}SubL-_parent Ppnode;}}// 左单旋// 同理void RotateL(Node* parent){Node* SubR parent-_right;//此处就为 curNode* SubRL SubR-_left;//parent的右换成cur的左parent-_right SubRL;//把cur的左孩子换成parentSubR-_left parent;Node* Ppnode parent-_parent;//注意 还要修改其父指针parent-_parent SubR;if (SubRL)//右边可能为空SubRL-_parent parent;if (_root parent)//如果parent为根节点则需要把subR改变成根节点并且其父亲为nullptr{_root SubR;SubR-_parent nullptr;}else{//同时还要考虑父亲 是祖先的左或右if (Ppnode-_left parent){Ppnode-_left SubR;}else{Ppnode-_right SubR;}SubR-_parent Ppnode;}}private:Node* _root nullptr;
};本章完。预知后事如何暂听下回分解。
如果有任何问题欢迎讨论哈
如果觉得这篇文章对你有所帮助的话点点赞吧
持续更新大量C细致内容早关注不迷路。
