自学内容网 自学内容网
自学内容网 > 正文

STL之map&set|AVL树

🕗 发布于 2024-11-16 17:37 stl  c++  开发语言  

STL之map&set|AVL树

set&map

前言：stl库中set和map的底层都是红黑树，一种平衡搜索二叉树，是我下一篇博客的内容。map和set的模拟实现见我的下一篇博客红黑树。

vector/list/deque…之前学的容器称为序列式容器，数据线性存储
map/set…称为关联式容器，数据之间强关联。

搜索二叉树

无论AVL树，还是红黑树，它们都属于搜索二叉树。那么它们都遵守搜索二叉树的规则：左孩子的值比父亲的小/大，右孩子的值比父亲的大/小，注意对应。通过/前面的规则，可以得出一些结论，比如左子树的max比父亲的值小，右子树的min比父亲的大。

实现代码

namespace key
{
template<class K>
struct BSTreeNode
{
BSTreeNode* _left = nullptr;
BSTreeNode* _right = nullptr;
K _key;
BSTreeNode(K key) :_key(key) {}
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> node;
public:
BSTree() = default;//强制生成默认构造
BSTree(const BSTree<K>& t)
{
Copy(_root, t._root);
}
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
bool Insert(const K& key)//参数缺省值不能给_root，一方面缺省值得是全局变量或常量；这里也不能用this指针
{
if (!_root)
{
_root = new node(key);
return true;
}
node* parent = _root;
node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
node* newnode = new node(key);
if (key > parent->_key)
{
parent->_right = newnode;
}
else
{
parent->_left = newnode;
}
}
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool Find(const K& key)
{
node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
cur = cur->_right;
}
else if (key < cur->_key)
{
cur = cur->_left;
}
else return true;
}
return false;
}
bool FindR(const K& key)
{
return _FindR(_root, key);
}
bool Erase(const K& key)
{
node* parent = _root;
node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else
{//单子/null，托孤
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
return true;
}
if (cur == parent->_left)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
return true;
}
if (cur == parent->_left)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
delete cur;
}
else//双子，请保姆->左子树最右/右子树最左
{
/*node* pmaxLeft = cur;
node* maxLeft = cur->_left;
while (maxLeft->_right)
{
pmaxLeft = maxLeft;
maxLeft = maxLeft->_right;
}
if (pmaxLeft != cur)
pmaxLeft->_right = maxLeft->_left;
else
cur->_left = maxLeft->_left;
cur->_key = maxLeft->_key;
delete maxLeft;*/

node* pminRight = cur;
node* minRight = cur->_right;
while (minRight->_left)
{
pminRight = minRight;
minRight = minRight->_left;
}
if (pminRight != cur)
pminRight->_left = minRight->_right;
else
cur->_right = minRight->_right;
cur->_key = minRight->_key;
delete minRight;
}
return true;
}
}
return false;
}
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
~BSTree()
{
Destroy(_root);
}
protected:
void Copy(node*& myroot, const node* root)
{
if (root == nullptr)return;
myroot = new node(root->_key);
Copy(myroot->_left, root->_left);
Copy(myroot->_right, root->_right);
}
void _InOrder(node* root)
{
if (!root)return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
bool _FindR(node* root, const K& key)
{
if (root == nullptr)return false;
if (root->_key == key)return true;
if (key > root->_key)_FindR(root->_right, key);
else _FindR(root->_left, key);
}
bool _InsertR(node*& root, const K& key)//引用の妙用，这里的root就是根节点或父亲的left/right，直接就链接上了
{
if (root == nullptr)
{
root = new node(key);
}
if (root->_key == key)return false;
if (key > root->_key)_InsertR(root->_right, key);
else _InsertR(root->_left, key);
}
bool _EraseR(node*& root, const K& key)
{
if (root == nullptr)return false;
if (key > root->_key)return _EraseR(root->_right, key);
else if (key < root->_key)return _EraseR(root->_left, key);
else
{
if (!root->_left)
{
node* tmp = root;
root = root->_right;
delete tmp;
}
else if (!root->_right)
{
node* tmp = root;
root = root->_left;
delete tmp;
}
else
{
node* maxLeft = root->_left;
while (maxLeft->_right)
{
maxLeft = maxLeft->_right;
}
swap(root->_key, maxLeft->_key);
return _EraseR(root->_left, key);
}
return true;
}
}
void Destroy(node*& root)
{
if (root == nullptr)return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
root = nullptr;
}
node* _root = nullptr;
};
}
namespace key_value
{
template<class K, class V>
struct BSTreeNode
{
BSTreeNode* _left = nullptr;
BSTreeNode* _right = nullptr;
K _key;
V _val;
BSTreeNode(const K& key, const V& val) :_key(key), _val(val) {}
};
template<class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> node;
public:
BSTree() = default;//强制生成默认构造
bool Insert(const K& key, const V& val)//参数缺省值不能给_root，一方面缺省值得是全局变量或常量；这里也不能用this指针
{
if (!_root)
{
_root = new node(key, val);
return true;
}
node* parent = _root;
node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
node* newnode = new node(key, val);
if (key > parent->_key)
{
parent->_right = newnode;
}
else
{
parent->_left = newnode;
}
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
node* Find(const K& key)
{
node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
cur = cur->_right;
}
else if (key < cur->_key)
{
cur = cur->_left;
}
else return cur;
}
return nullptr;
}
bool Erase(const K& key)
{
node* parent = _root;
node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else
{//单子/null，托孤
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
return true;
}
if (cur == parent->_left)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
return true;
}
if (cur == parent->_left)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
delete cur;
}
else//双子，请保姆->左子树最右/右子树最左
{
/*node* pmaxLeft = cur;
node* maxLeft = cur->_left;
while (maxLeft->_right)
{
pmaxLeft = maxLeft;
maxLeft = maxLeft->_right;
}
if (pmaxLeft != cur)
pmaxLeft->_right = maxLeft->_left;
else
cur->_left = maxLeft->_left;
cur->_key = maxLeft->_key;
delete maxLeft;*/

node* pminRight = cur;
node* minRight = cur->_right;
while (minRight->_left)
{
pminRight = minRight;
minRight = minRight->_left;
}
if (pminRight != cur)
pminRight->_left = minRight->_right;
else
cur->_right = minRight->_right;
cur->_key = minRight->_key;
delete minRight;
}
return true;
}
}
return false;
}
protected:
void _InOrder(node* root)
{
if (!root)return;
_InOrder(root->_left);
cout << root->_key << ":" << root->_val << endl;
_InOrder(root->_right);
}
node* _root = nullptr;
};
}
int main()
{
key::BSTree<int>b;
int a[] = { 8,3,1,10,6,4,7,14,13 };
for (auto& x : a)
{
b.InsertR(x);
}
b.InOrder();

key::BSTree<int>bb(b);
bb.InOrder();

b.EraseR(4);
b.InOrder();
b.EraseR(14);
b.InOrder();
b.EraseR(3);
b.InOrder();
b.EraseR(8);
b.InOrder();
for (auto& x : a)
{
b.InOrder();
b.EraseR(x);
}
/*key_value::BSTree<string, int>dict;
string arr[] = { "a","a","b","c","d","d","d" };
for (auto& s : arr)
{
auto ret = dict.Find(s);
if (!ret)
dict.Insert(s, 1);
else
ret->_val++;
}
dict.InOrder();*/
}

但是由于搜索二叉树在数据接近有序的情况下，会退化成单支树，时间复杂度也降级为O(N)。所以库中map/set底层使用红黑树，一种自动平衡的搜索二叉树。

set的使用

set作为key模型，插入同样的key会失败，所以其主要用途有去重+排序。

  • insert最常用的是第一个。
    在这里插入图片描述

pair是标准库里的一个类，用来封装两个变量。经常使用make_pair函数来创造pair。在这里插入图片描述

  • find返回迭代器，end表示失败。返回的迭代器不允许修改key，否则会破坏搜索二叉树的规则。find
  • count找到返回1，失败返回0。set的count显得鸡肋，但是multiset中的count可就有用了。后者的count成功返回key的个数。
    count

multiset是可以存多个相同key的set，即允许键值冗余。在存入多个相同key时，第二个key会在第一个key的下面插入。在find时，返回的是中序的第一个key的迭代器。其余接口与set基本类似，不再赘述。

map的使用

map作为key-value模型，主要用途是。

  • insert常用第一个，要插入的value_type是pair<const Key, T>,我们常用make_pair插入。返回值pair的第一个是封装了value_type的迭代器可供外界修改，第二个bool用来判断是否插入成功。在这里插入图片描述
  • 最强大的功能当属[ ]重载了。如果传入的key不存在，就插入并采用默认值初始化；如果存在就返回对应value的引用，允许外界修改它。几乎可以平替insert和find了。实现代码比较精简，return (insert(make_pair(k,V())->first)->value。可见，[ ]支持修改，支持插入，支持插入+修改，支持查找。在这里插入图片描述
  • map自然也有multimap版本，但后者没有重载[ ]。

另外，map和set有迭代器，那就支持范围for遍历，无需多言。

set&map的模拟实现（见红黑树篇）

set&map的模拟实现，等我发布了红黑树篇就过来贴链接奥。

AVL树

AVL树，名字是取它的发明者–两个俄罗斯数学家的名字首字母而来。它通过增加平衡因子+旋转来控制每个结点的左右子树高度差的绝对值不超过1。本文中平衡因子balance factor采用右子树高度-左子树高度。

AVL树的模拟实现

下图是旋转的详细解析图，插入和删除都会用到。
旋转的目的，一是保持二叉树搜索规则，二是保持平衡，降低高度。
旋转

代码：

template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left = nullptr;
AVLTreeNode<K, V>* _right = nullptr;
AVLTreeNode<K, V>* _parent = nullptr;//方便起见，采取三叉链
pair<K, V>_kv;
int _bf = 0;//平衡因子，此处定义为右子树高-左子树高
AVLTreeNode(const pair<K, V>& kv) :_kv(kv) {}
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> node;
public:
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new node(kv);
return true;
}
node* parent = nullptr;
node* cur = _root;
while (cur)
{
if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else return false;
}
cur = new node(kv);
cur->_parent = parent;
if (parent->_kv.first > kv.first)
parent->_left = cur;
else
parent->_right = cur;
while (parent)//更新平衡因子，如果大于1，需要旋转
{
if (cur == parent->_left)
parent->_bf--;
else
parent->_bf++;
if (parent->_bf == 0)break;//插入前1/-1，插入后0，说明该子树平衡/高度不变，不必向上
else if (parent->_bf == -1 || parent->_bf == 1)//插入前0，插入后1/-1，左/右多出的节点必然影响祖先的bf，须迭代
{
cur = parent;
parent = cur->_parent;
}
else if (parent->_bf == -2 || parent->_bf == 2)//旋转，解析请看jpg
{
if (parent->_bf == 2)
{
if (cur->_bf == 1)//左单旋
{
RotateL(parent);
//parent->_right = cur->_left;
//cur->_left = parent;
//cur->_left->_parent = parent;
//cur->_parent = parent->_parent;
//if (parent->_parent)
//{
//if (parent->_parent->_left == parent)
//parent->_parent->_left = cur;
//else
//parent->_parent->_right = cur;
//}
//else _root = cur;
//parent->_parent = cur;
break;//break很关键，因为旋转完parent都变了，不能再循环了。
}
else if (cur->_bf == -1)
{
RotateRL(parent);
break;//没写break，改bug改了半天。。。
}
else assert(false);
}
else
{
if (cur->_bf == -1)//右单旋
{
RotateR(parent);
break;
}
else if (cur->_bf == 1)
{
RotateLR(parent);
break;
}
else assert(false);
}
}
else assert(false);//防bug
}
return true;
}
bool isAVLTree()
{
return _isAVLTree(_root);
}
void Inorder()
{
_Inorder(_root);
}
private:
int _Height(node* root)
{
if (!root)return 0;
int LeftH = _Height(root->_left) + 1;
int RightH = _Height(root->_right) + 1;
return LeftH > RightH ? LeftH : RightH;
}
bool _isAVLTree(node* root)
{
if (!root)return true;
if (root->_bf > 1 || root->_bf < -1)
{
cout << root->_kv.first << ":" << root->_bf << endl;
return false;
}
int leftH = _Height(root->_left);
int rightH = _Height(root->_right);
if (rightH - leftH != root->_bf)
{
cout << root->_kv.first << ":" << root->_bf << " true:" << rightH - leftH << endl;
return false;
}
return _isAVLTree(root->_left) && _isAVLTree(root->_right);
}
void _Inorder(node* root)
{
if (!root)return;
_Inorder(root->_left);
cout << root->_kv.first << " ";
_Inorder(root->_right);
}
void RotateL(node* parent)
{
node* subR = parent->_right;
node* subRL = subR->_left;
node* pparent = parent->_parent;

parent->_right = subRL;
subR->_left = parent;

subR->_parent = pparent;
if (subRL)
subRL->_parent = parent;
parent->_parent = subR;
if (pparent)
{
if (pparent->_left == parent)
pparent->_left = subR;
else pparent->_right = subR;
}
else _root = subR;
subR->_bf = parent->_bf = 0;
}
void RotateR(node* parent)
{
node* subL = parent->_left;
node* subLR = subL->_right;
node* pparent = parent->_parent;

parent->_left = subLR;
subL->_right = parent;

subL->_parent = pparent;
if (subLR)
subLR->_parent = parent;
parent->_parent = subL;
if (pparent)
{
if (parent == pparent->_left)
pparent->_left = subL;
else pparent->_right = subL;
}
else _root = subL;
subL->_bf = parent->_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的左新增
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)//subLR的右新增
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == 0)//subLR本身即新增
{
parent->_bf = subL->_bf = 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)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = subR->_bf = subRL->_bf = 0;
}
else assert(false);
}
private:
node* _root = nullptr;
};
int main()
{
//AVLTree<int, int>t;
//int arr[] = { 4,2,6,1,3,5,15,7,16,14 };
//for (int i = 0; i < 9; i++)
//{
//t.Insert(make_pair(arr[i], i));
////cout << "第" << i << ":";//调试
//t.isAVLTree();
////cout << endl;
//}
//t.Inorder();
srand(time(0));
const size_t N = 1000000;
AVLTree<int, int>t;
for (size_t i = 0; i < N; i++)
{
size_t x = rand();
t.Insert(make_pair(x, x));
}
cout << t.isAVLTree() << endl;
}

代码中只实现了插入。删除在原理上类似，删节点后更新平衡因子。
综上可见，AVL树查找效率近似O(log2N)，因为它近似平衡二叉树。但是由于种种原因，现实中（库中）更常用的是红黑树，我下一篇博客的主题。而现实工作中，也不需要手撕这些高级二叉树，因为你写的大概不会有库中实现的完美。用现成的就好，但原理也要懂。

总结时刻，两天肝出此博客，累，但手撕AVL树的插入之后的成就感是无与伦比的。话不多说，铁子们，红黑树见~😘


原文地址：https://blog.csdn.net/Steve__evetS/article/details/143751528

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024