AVL树的插入删除详细实现，基于AVL树的map和set简单模板编程实现，包括const迭代器
以上，我们就完成了插入操作，与它不同的是，删除操作就算旋转完了也要继续向上维护父节点，直到整棵树的根部，并且我们如果删除了还要旋转，那就要旋转类似红黑树里的那个"uncle"节点，也就是父亲的另一个节点，如果这个节点不存在删除后是不可能引起旋转的，具体原因依旧可以去找视频看，这里只提供代码。如此操作，我们便使得data适配了一个单一类型以及一个pair类型，我们甚至可以通过继续定义T塞入更多的数据
·
完整的AVLtree.h Mymap.h MySet.h内容文章最最后会全部给出，可以先全粘贴到编译器里方便自己看，文章中间的代码大多都是零散的
一.首先来定义一个avl树的节点
template<typename T>
struct AVLNode
{
T _data;
AVLNode* _left;
AVLNode* _right;
AVLNode* _parent;
int _bf;
AVLNode(const T& data) :_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {}
};1._data是我们储存的数据，_parent是父亲节点，是为了后续的旋转操作，int _bf是平衡因子，这里代表右子树比左子树高的高度，平衡时为0，为2或-2时我们需要旋转，初始化为0
2.注意，_data在后面可以是set的单一储存结构，也可以是map的pair<1,2>结构，如何实现后面会提及，我们先来看看整颗AVL树插入与删除的操作。
二.为了顺利旋转AVL树，我们需要用到四个旋转操作，具体的图之类希望大家在其他平台寻找优质的动画，我这里只提供代码复现，大家最好动手画画，一共就四种，细节处一些空指针判断留意一下即可
1.RotateL是左单旋，是一个节点_bf==2时，且这个节点右节点_bf==1（int _bf是平衡因子，这里代表右子树比左子树高的高度）
2.RotateR为右单旋
3.RL 和 LR，是旋转一个“折线”，先旋转下面两个拉到一条直线上，再转上面两个
void RotateL(Node* parent, Node* cur)
{
Node* ppnode = parent->_parent;
parent->_right = cur->_left;
if (cur->_left) cur->_left->_parent = parent;
cur->_left = parent;
parent->_parent = cur;
cur->_parent = ppnode;
if (ppnode)
{
if (ppnode->_left == parent) ppnode->_left = cur;
else ppnode->_right = cur;
}
else _root = cur;
parent->_bf = cur->_bf = 0;
}
void RotateR(Node* parent, Node* cur)
{
Node* ppnode = parent->_parent;
parent->_left = cur->_right;
if (cur->_right) cur->_right->_parent = parent;
cur->_right = parent;
parent->_parent = cur;
cur->_parent = ppnode;
if (ppnode)
{
if (ppnode->_left == parent) ppnode->_left = cur;
else ppnode->_right = cur;
}
else _root = cur;
parent->_bf = cur->_bf = 0;
}
void RotateRL(Node* parent, Node* cur, Node* child)
{
int bf = child->_bf;
RotateR(child, cur);
RotateL(parent, child);
if (bf == 0)
{
child->_bf = 0;
parent->_bf = cur->_bf = 0;
}
else if (bf == 1)
{
cur->_bf = 0;
child->_bf = 0;
parent->_bf = -1;
}
else
{
child->_bf = 0;
cur->_bf = 1;
parent->_bf = 0;
}
}
void RotateLR(Node* parent, Node* cur, Node* child)
{
int bf = child->_bf;
RotateL(cur, child);
RotateR(parent, child);
if (bf == 0)
{
child->_bf = 0;
parent->_bf = cur->_bf = 0;
}
else if (bf == -1)
{
child->_bf = 0;
cur->_bf = 0;
parent->_bf = 1;
}
else
{
child->_bf = 0;
cur->_bf = -1;
parent->_bf = 0;
}
}看完四种旋转，就可以实现insert了，前面和二叉搜索树是一个思路，注意不要忘了从插入的地方开始向上维护_bf
注意：平衡因子可以不在旋转里维护而在外面维护，这里的平衡因子只适用于插入的旋转，后面删除的旋转我们会重新维护，但是其他是不变的
关于KeyofT kot这个参数，等会写map set才会用到，它通过运算符重载operator()(const T& data)来取出set的value或者map的value，我们可以发现只有在比较大小的时候才会用到他，只想看AVL树的朋友把它当成一个大于小于号即可，毕竟这是二叉搜索树的内容
bool insert(const T& data)
{
KeyofT kot;
Node* newnode = new Node(data);
if (!_root)
{
_root = newnode;
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
parent = cur;
if (kot(data) < kot(cur->_data)) cur = cur->_left;
else if (kot(data) > kot(cur->_data)) cur = cur->_right;
else
{
delete newnode;
return false;
}
}
if (kot(data) < kot(parent->_data)) parent->_left = newnode;
else parent->_right = newnode;
newnode->_parent = parent;
cur = newnode;
while (parent)
{
if (cur == parent->_left) parent->_bf--;
else parent->_bf++;
if (parent->_bf == 0) break;
else if (parent->_bf == 2)
{
if (cur->_bf == 1)
{
RotateL(parent, cur);
}
else
{
Node* child = cur->_left;
RotateRL(parent, cur, child);
}
break;
}
else if (parent->_bf == -2)
{
if (cur->_bf == -1)
{
RotateR(parent, cur);
}
else
{
Node* child = cur->_right;
RotateLR(parent, cur, child);
}
break;
}
cur = parent;
parent = parent->_parent;
}
return true;
}以上，我们就完成了插入操作，与它不同的是，删除操作就算旋转完了也要继续向上维护父节点，直到整棵树的根部，并且我们如果删除了还要旋转，那就要旋转类似红黑树里的那个"uncle"节点，也就是父亲的另一个节点，如果这个节点不存在删除后是不可能引起旋转的，具体原因依旧可以去找视频看，这里只提供代码
bool erase(const T& data)
{
KeyofT kot;
Node* cur = find(kot(data));
if (!cur)return false;
if (cur->_left && cur->_right)
{
Node* tmp = cur->_left;
while (tmp->_right)tmp = tmp->_right;
// 使用特化的 CopyValue 函数
CopyValue(cur->_data, tmp->_data);
cur = tmp;
}
Node* parent = cur->_parent;
Node* child = cur->_left ? cur->_left : cur->_right;
if (!parent)
{
_root = child;
if(child) child->_parent = nullptr;
delete cur;
return true;
}
bool isLeft = (cur == parent->_left);
if (isLeft)
{
parent->_left = child;
parent->_bf++;
}
else
{
parent->_right = child;
parent->_bf--;
}
if (child) child->_parent = parent;
delete cur;
while (parent)
{
if (abs(parent->_bf) == 1) break;
if (parent->_bf == 2)
{
Node* R = parent->_right;
if (R->_bf >= 0)
{
RotateL(parent, R);
if (R->_bf == 0)
{
parent->_bf = 1;
R->_bf = -1;
}
}
else
{
Node* RL = R->_left;
int bf = RL->_bf;
RotateRL(parent, R, RL);
if (bf == 1) parent->_bf = -1;
else if (bf == -1) R->_bf = 1;
}
parent = parent->_parent;
}
else if (parent->_bf == -2)
{
Node* L = parent->_left;
if (L->_bf <= 0)
{
RotateR(parent, L);
if (L->_bf == 0)
{
parent->_bf = -1;
L->_bf = 1;
}
}
else
{
Node* LR = L->_right;
int bf = LR->_bf;
RotateLR(parent, L, LR);
if (bf == 1) L->_bf = -1;
else if (bf == -1) parent->_bf = 1;
}
parent = parent->_parent;
}
if (!parent) break;
Node* cur = parent;
parent = parent->_parent;
if (!parent) break;
if (cur == parent->_left)
parent->_bf++;
else
parent->_bf--;
}
return true;
}
Node* find(const K& Key) const
{
Node* cur = _root;
KeyofT kot;
while (cur)
{
if (Key > kot(cur->_data))cur = cur->_right;
else if (Key < kot(cur->_data))cur = cur->_left;
else return cur;
}
return nullptr;
}我们会发现一行特殊的代码
// 使用特化的 CopyValue 函数
CopyValue(cur->_data, tmp->_data);
cur = tmp;不禁要问，为什么要这样写呢?不可以直接写cur._data = tmp._data;吗？如果你只写avl树是可以的，但是对于最后要维护map的pair<const K,T>来说，库里面的pair无法直接用等于号，大家可以试试以下代码在主函数中：
pair<const int, int> p1;
pair<const int, int> p2;
p1 = p2;这里的等于号是禁止的，所以我们使用了模板特化来顺利取出Value,文章最后会详细说
接下来，我们实现AVLTree的迭代器
template<class T,class Ptr,class Ref>
struct __tree_iterator
{
typedef __tree_iterator<T, Ptr, Ref> Self;
typedef AVLNode<T> Node;
Node* _node;
__tree_iterator(Node* node) :_node(node) {}
__tree_iterator() :_node(nullptr) {}
Ref operator*() { return _node->_data; }
Ptr operator->() { return &_node->_data; }
Self& operator++()
{
if (_node->_right)
{
Node* subLeft = _node->_right;
while (subLeft->_left)subLeft = subLeft->_left;
_node = subLeft;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent)
{
if (parent->_left == cur)break;
else
{
cur = cur->_parent;
parent = parent->_parent;
}
}
_node = parent;
}
return *this;
}
bool operator==(const Self& self) const { return _node == self._node; }
bool operator!=(const Self& self) const { return _node != self._node; }
};其中的迭代器类似一个非递归中序遍历，属于基础内容不再赘述，终于准备完最底层的AVL树了，现在可以来写map和set了
1.我们先来研究研究一个data是如何做到既可以是T又可以是pair<const K,T>？
首先来看看这三个东西的模板参数是怎么定义的
template<class K, class T,class KeyofT>
class AVLTree
template<class K,class T>
class map
typedef AVLTree<K, pair<const K, T>, Compare> AVLtree;
template<class K>
class set
typedef AVLTree<K, K, Compare> AVLtree;如此操作，我们便使得data适配了一个单一类型以及一个pair类型，我们甚至可以通过继续定义T塞入更多的数据，这为我们的模板编程开启了一个新的大门，是我认为map中一个很强大的东西
现在，来说说KeyofT参数，他就是刚才提到的KeyofT kot参数，为了取出我们要正确比较大小的参数，比如set的T或者map pair<const K,T>中的K，让我们来看看定义
set
struct Compare
{
const K& operator()(const K& data) const
{
return data;
}
};
map
struct Compare
{
const K& operator()(const pair<K,T>& data)
{
return data.first;
}
};虽然不小心把KeyofT名字写成Compare了，但是无伤大雅，知道我们要取出的是什么东西即可，如果想继续增加一个真正的Compare模板也是非常简单的，修改的地方仍然只有AVL树中insert和find的“二叉搜索树”寻找部分
现在我们已经完成百分之九十的东西了，来看看我在编写代码时遇到的坑，也就是erase中为什么不可以直接用等于号的问题（以pair<const int,int>为例）：先说结论：因为 p1 和 p2 的 first 成员是 const int 类型，而 const 修饰的成员在赋值时不能被修改,pair 的默认赋值运算符会尝试对整个对象（包括 first 和 second）进行赋值，但 const 成员无法被重新赋值，因此编译器会报错，如果需要赋值，可以手动修改 second 成员（如 p1.second = p2.second;），或者避免使用 const 作为 first 的类型
为了成功在erase里把它“一口吃掉”，我们需要使用一个模板特化的知识，或者可以使用编译时判断类型(这是C++14的内容，碍于本人水平就不讲解了，感兴趣粘贴完结尾的代码后问ai怎么做)，这里只给出模板特化的解决方法：
// 主模板：默认情况下直接赋值（用于set）
template<typename T>
void CopyValue(T& dst, const T& src)
{
dst = src;
}
// 特化版本：处理pair类型（用于map）
template<typename K, typename V>
void CopyValue(pair<const K, V>& dst, const pair<const K, V>& src)
{
dst.second = src.second;
}如此，我们不仅解决了这个棘手的问题，又复习了模板特化的内容，可谓是一举两得
最后我们要谈的就是const迭代器的问题，这里先注意一个小坑点：
map
typedef typename AVLTree<K, pair<const K, T>, Compare>::iterator iterator;
typedef typename AVLTree<K, pair<const K, T>, Compare>::const_iterator const_iterator;
set
typedef typename AVLTree<K, K, Compare>::const_iterator iterator;
typedef typename AVLTree<K, K, Compare>::const_iterator const_iterator;我的typedef时后面一定要加个typename，因为typename 在这里的作用是告诉编译器 AVLTree<K, K, Compare>::const_iterator 是一个 类型，而不是静态成员变量或其他名称。因为 const_iterator 依赖于模板参数 K 和 Compare，编译器在解析模板时无法直接确定其性质，必须通过 typename 显式声明这是一个嵌套类型。
并且为了符合库中set无法修改，map只能修改value的特性，我们如上定义了两个容器的迭代器，如果const K不用加const是不会遇到我们刚才必须用模板特化才能解决的那个问题的，通过这些操作，我们就不错的实现了这两个常用容器
结语：感谢大家看到这里，如果文章有不妥之处请多包涵，有不清楚的地方可以和我讨论，下面我按照1.AVLTree 2.MySet 3.Mymap的顺序给出完整代码
1.AVLTree
#pragma once
#include<iostream>
using namespace std;
template<typename T>
struct AVLNode
{
T _data;
AVLNode* _left;
AVLNode* _right;
AVLNode* _parent;
int _bf;
AVLNode(const T& data) :_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {}
};
template<class T,class Ptr,class Ref>
struct __tree_iterator
{
typedef __tree_iterator<T, Ptr, Ref> Self;
typedef AVLNode<T> Node;
Node* _node;
__tree_iterator(Node* node) :_node(node) {}
__tree_iterator() :_node(nullptr) {}
Ref operator*() { return _node->_data; }
Ptr operator->() { return &_node->_data; }
Self& operator++()
{
if (_node->_right)
{
Node* subLeft = _node->_right;
while (subLeft->_left)subLeft = subLeft->_left;
_node = subLeft;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent)
{
if (parent->_left == cur)break;
else
{
cur = cur->_parent;
parent = parent->_parent;
}
}
_node = parent;
}
return *this;
}
bool operator==(const Self& self) const { return _node == self._node; }
bool operator!=(const Self& self) const { return _node != self._node; }
};
// 主模板：默认情况下直接赋值（用于set）
template<typename T>
void CopyValue(T& dst, const T& src)
{
dst = src;
}
// 特化版本：处理pair类型（用于map）
template<typename K, typename V>
void CopyValue(pair<const K, V>& dst, const pair<const K, V>& src)
{
dst.second = src.second;
}
template<class K, class T,class KeyofT>
class AVLTree
{
public:
typedef __tree_iterator<T, T*, T&> iterator;
typedef __tree_iterator<T, const T*, const T&> const_iterator;
iterator begin()
{
Node* cur = _root;
while (cur && cur->_left)cur = cur->_left;
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin() const
{
Node* cur = _root;
while (cur && cur->_left)cur = cur->_left;
return const_iterator(cur);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
public:
typedef AVLNode<T> Node;
AVLTree() : _root(nullptr) {}
bool insert(const T& data)
{
KeyofT kot;
Node* newnode = new Node(data);
if (!_root)
{
_root = newnode;
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
parent = cur;
if (kot(data) < kot(cur->_data)) cur = cur->_left;
else if (kot(data) > kot(cur->_data)) cur = cur->_right;
else
{
delete newnode;
return false;
}
}
if (kot(data) < kot(parent->_data)) parent->_left = newnode;
else parent->_right = newnode;
newnode->_parent = parent;
cur = newnode;
while (parent)
{
if (cur == parent->_left) parent->_bf--;
else parent->_bf++;
if (parent->_bf == 0) break;
else if (parent->_bf == 2)
{
if (cur->_bf == 1)
{
RotateL(parent, cur);
}
else
{
Node* child = cur->_left;
RotateRL(parent, cur, child);
}
break;
}
else if (parent->_bf == -2)
{
if (cur->_bf == -1)
{
RotateR(parent, cur);
}
else
{
Node* child = cur->_right;
RotateLR(parent, cur, child);
}
break;
}
cur = parent;
parent = parent->_parent;
}
return true;
}
bool erase(const T& data)
{
KeyofT kot;
Node* cur = find(kot(data));
if (!cur)return false;
if (cur->_left && cur->_right)
{
Node* tmp = cur->_left;
while (tmp->_right)tmp = tmp->_right;
// 使用特化的 CopyValue 函数
CopyValue(cur->_data, tmp->_data);
cur = tmp;
}
Node* parent = cur->_parent;
Node* child = cur->_left ? cur->_left : cur->_right;
if (!parent)
{
_root = child;
if(child) child->_parent = nullptr;
delete cur;
return true;
}
bool isLeft = (cur == parent->_left);
if (isLeft)
{
parent->_left = child;
parent->_bf++;
}
else
{
parent->_right = child;
parent->_bf--;
}
if (child) child->_parent = parent;
delete cur;
while (parent)
{
if (abs(parent->_bf) == 1) break;
if (parent->_bf == 2)
{
Node* R = parent->_right;
if (R->_bf >= 0)
{
RotateL(parent, R);
if (R->_bf == 0)
{
parent->_bf = 1;
R->_bf = -1;
}
}
else
{
Node* RL = R->_left;
int bf = RL->_bf;
RotateRL(parent, R, RL);
if (bf == 1) parent->_bf = -1;
else if (bf == -1) R->_bf = 1;
}
parent = parent->_parent;
}
else if (parent->_bf == -2)
{
Node* L = parent->_left;
if (L->_bf <= 0)
{
RotateR(parent, L);
if (L->_bf == 0)
{
parent->_bf = -1;
L->_bf = 1;
}
}
else
{
Node* LR = L->_right;
int bf = LR->_bf;
RotateLR(parent, L, LR);
if (bf == 1) L->_bf = -1;
else if (bf == -1) parent->_bf = 1;
}
parent = parent->_parent;
}
if (!parent) break;
Node* cur = parent;
parent = parent->_parent;
if (!parent) break;
if (cur == parent->_left)
parent->_bf++;
else
parent->_bf--;
}
return true;
}
Node* find(const K& Key) const
{
Node* cur = _root;
KeyofT kot;
while (cur)
{
if (Key > kot(cur->_data))cur = cur->_right;
else if (Key < kot(cur->_data))cur = cur->_left;
else return cur;
}
return nullptr;
}
private:
Node* _root;
void RotateL(Node* parent, Node* cur)
{
Node* ppnode = parent->_parent;
parent->_right = cur->_left;
if (cur->_left) cur->_left->_parent = parent;
cur->_left = parent;
parent->_parent = cur;
cur->_parent = ppnode;
if (ppnode)
{
if (ppnode->_left == parent) ppnode->_left = cur;
else ppnode->_right = cur;
}
else _root = cur;
parent->_bf = cur->_bf = 0;
}
void RotateR(Node* parent, Node* cur)
{
Node* ppnode = parent->_parent;
parent->_left = cur->_right;
if (cur->_right) cur->_right->_parent = parent;
cur->_right = parent;
parent->_parent = cur;
cur->_parent = ppnode;
if (ppnode)
{
if (ppnode->_left == parent) ppnode->_left = cur;
else ppnode->_right = cur;
}
else _root = cur;
parent->_bf = cur->_bf = 0;
}
void RotateRL(Node* parent, Node* cur, Node* child)
{
int bf = child->_bf;
RotateR(child, cur);
RotateL(parent, child);
if (bf == 0)
{
child->_bf = 0;
parent->_bf = cur->_bf = 0;
}
else if (bf == 1)
{
cur->_bf = 0;
child->_bf = 0;
parent->_bf = -1;
}
else
{
child->_bf = 0;
cur->_bf = 1;
parent->_bf = 0;
}
}
void RotateLR(Node* parent, Node* cur, Node* child)
{
int bf = child->_bf;
RotateL(cur, child);
RotateR(parent, child);
if (bf == 0)
{
child->_bf = 0;
parent->_bf = cur->_bf = 0;
}
else if (bf == -1)
{
child->_bf = 0;
cur->_bf = 0;
parent->_bf = 1;
}
else
{
child->_bf = 0;
cur->_bf = -1;
parent->_bf = 0;
}
}
};
2.MySet
namespace tongshen
{
template<class K>
class set
{
public:
struct Compare
{
const K& operator()(const K& data) const
{
return data;
}
};
typedef AVLTree<K, K, Compare> AVLtree;
bool insert(const K& data)
{
return _tree.insert(data);
}
bool erase(const K& data)
{
return _tree.erase(data);
}
public:
typedef typename AVLTree<K, K, Compare>::const_iterator iterator;
typedef typename AVLTree<K, K, Compare>::const_iterator const_iterator;
iterator begin() const { return _tree.begin(); }
iterator end() const { return _tree.end(); }
protected:
AVLtree _tree;
};
}3.MyMap
namespace tongshen
{
template<class K,class T>
class map
{
public:
struct Compare
{
const K& operator()(const pair<K,T>& data)
{
return data.first;
}
};
typedef AVLTree<K, pair<const K, T>, Compare> AVLtree;
typedef typename AVLtree::Node Node;
public:
typedef typename AVLTree<K, pair<const K, T>, Compare>::iterator iterator;
typedef typename AVLTree<K, pair<const K, T>, Compare>::const_iterator const_iterator;
iterator begin() { return _tree.begin(); }
iterator end() { return _tree.end(); }
const_iterator begin() const { return _tree.begin(); }
const_iterator end() const { return _tree.end(); }
pair<iterator,bool> insert(const pair<K, T>& data)
{
if (_tree.insert(data))
return make_pair(find(data.first), true);
return make_pair(find(data.first), false);
}
bool erase(const K& Key)
{
Node* node = _tree.find(Key);
if (node == nullptr)
return false;
return _tree.erase(node->_data);
}
iterator find(const K& Key)
{
return iterator(_tree.find(Key));
}
T& operator[](const K& Key)
{
return (*(insert(make_pair(Key, T())).first)).second;
}
protected:
AVLtree _tree;
};
}
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
21
0- 0
已为社区贡献1条内容
所有评论(0)