STL之map&set|AVL树
- set&map
- 搜索二叉树
- 实现代码
- set的使用
- map的使用
- set&map的模拟实现(见红黑树篇)
- AVL树
- 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;elseparent->_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;elseparent->_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;elsecur->_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;elsecur->_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;elseparent->_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;elseparent->_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;elsecur->_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;elsecur->_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);elseret->_val++;}dict.InOrder();*/
}
但是由于搜索二叉树在数据接近有序的情况下,会退化成单支树,时间复杂度也降级为O(N)。所以库中map/set底层使用红黑树,一种自动平衡的搜索二叉树。
set的使用
set作为key模型,插入同样的key会失败,所以其主要用途有去重+排序。
- insert最常用的是第一个。
pair是标准库里的一个类,用来封装两个变量。经常使用make_pair函数来创造pair。
- find返回迭代器,end表示失败。返回的迭代器不允许修改key,否则会破坏搜索二叉树的规则。
- count找到返回1,失败返回0。set的count显得鸡肋,但是multiset中的count可就有用了。后者的count成功返回key的个数。
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;elseparent->_right = cur;while (parent)//更新平衡因子,如果大于1,需要旋转{if (cur == parent->_left)parent->_bf--;elseparent->_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树的插入之后的成就感是无与伦比的。话不多说,铁子们,红黑树见~😘