封装红黑树实现 [set][map]

源码及框架分析由于源码整体来说比较复杂我们截取框架部分// stl_set.h // set 容器有序、唯一、底层由红黑树实现 template class Key, class Compare lessKey, class Alloc alloc class set { public: // 类型重定义set 的 key 和 value 是同一个值 typedef Key key_type; // 键类型 typedef Key value_type; // 值类型set 键值一体 private: // set 底层红黑树定义 // identityvalue_type取出 value 作为 keyset 键值相同 typedef rb_treekey_type, value_type, identityvalue_type, key_compare, Alloc rep_type; rep_type t; // set 底层真正实现红黑树成员变量 }; // stl_map.h // map 容器有序、key 唯一、key-value 结构、底层红黑树 template class Key, class T, class Compare lessKey, class Alloc alloc class map { public: // 类型重定义 typedef Key key_type; // 键类型 typedef T mapped_type; // 值类型map 独立的 value typedef pairconst Key, T value_type; // 节点存储类型pair(不可修改key) private: // map 底层红黑树定义 // select1stvalue_type从 pairKey,T 中提取第一个元素Key作为排序依据 typedef rb_treekey_type, value_type, select1stvalue_type, key_compare, Alloc rep_type; rep_type t; // map 底层真正实现红黑树成员变量 }; // stl_tree.h // 红黑树实现STL set/map 的底层核心 template class Key, class Value, class KeyOfValue, class Compare, class Alloc alloc class rb_tree { protected: typedef void* void_pointer; // 通用指针类型 typedef __rb_tree_node_base* base_ptr; // 红黑树基节点指针 typedef __rb_tree_nodeValue rb_tree_node; // 红黑树具体节点类型 typedef rb_tree_node* link_type; // 节点指针类型 typedef Key key_type; // 键类型 typedef Value value_type; // 节点存储的值类型 public: // 插入唯一值set/map 都不允许重复 key // 参数是 Value节点存储的完整数据 pairiterator, bool insert_unique(const value_type x); // 删除按 key 删除 size_type erase(const key_type x); // 查找按 key 查找 iterator find(const key_type x); protected: size_type node_count; // 记录红黑树节点总数size link_type header; // 红黑树固定头节点用于简化迭代器、根节点管理 }; // 红黑树具体节点结构 template class Value struct __rb_tree_node : public __rb_tree_node_base { typedef __rb_tree_nodeValue* link_type; Value value_field; // 节点存储的数据set:Key / map:pairconst Key,T };通过下图对框架的分析我们可以看到源码中rb_tree用了一个巧妙的泛型思想实现rb_tree是实现key的搜索场景还是key/value的搜索场景不是直接写死的而是由第二个模板参数Value决定_rb_tree_node中存储的数据类型set实例化rb_tree时第二个模板参数给的是keymap实例化rb_tree时第二个模板参数给的是pairconst key, T这样一颗红黑树既可以实现key搜索场景的set也可以实现key/value搜索场景的map。要注意一下源码里面模板参数是用T代表value而内部写的value_type不是我们日常key/value场景中说的value源码中的value_type反而是红黑树结点中存储的真实的数据的类型rb_tree第二个模板参数Value已经控制了红黑树结点中存储的数据类型为什么还要传第一个模板参数Key呢尤其是set两个模板参数是一样的。要注意的是对于map和setfind/erase时的函数参数都是Key所以第一个模板参数是传给find/erase等函数做形参的类型的。对于set而言两个参数是一样的但是对于map而言就完全不一样了map insert的是pair对象但是find和erase的是Key对象吐槽一下这里源码命名风格比较乱set模板参数用的是Key命名map用的是Key和T命名而rb_tree用的又是Key和Value可见大佬有时写代码也不规范乱弹琴。看图看着张图会有很好的理解的模拟实现 [set][map]复用红黑树的框架的实现参考源码框架map和set复用之前我们实现的红黑树【点击跳转】【下面附件会有更新的实现代码】我们这里相比源码调整一下key参数就用Kvalue参数就用V红黑树中的数据类型我们使用T其次因为RBTree是泛型实现无法判断T是单纯的K类型还是pairK, V类型因此在insert内部进行比较时无法直接处理。pair默认会把 key 和 value 一起参与比较而我们任何时候都只需要比较 key。所以我们在map和set上层分别实现MapKeyOfT和SetKeyOfT仿函数传给RBTree的KeyOfT模板参数让RBTree统一通过这个仿函数从T对象中取出 key再进行比较。具体细节参考如下代码实现。在set中SetKeyOfT仿函数的实现#pragma once #include RBTree.hpp template class K class Set { struct SetKeyOfT { // set 只存储 key所以直接返回 key 就行了 const K operator()(const K key) { return key; } }; public: bool Insert(const K key) { return _tree.Insert(key); } private: RBTreeK, K, SetKeyOfT _tree; };在map中MapKeyOfT仿函数的实现#pragma once #include RBTree.hpp template class K, class V class Map { struct MapKeyOfT { // map 存储 key-value 对所以返回 key const K operator()(const std::pairK, V kv) { return kv.first; } }; public: bool Insert(const std::pairK, V kv) { return _tree.Insert(kv); } private: RBTreeK, std::pairK, V, MapKeyOfT _tree; };复用的红黑树泛型化的实现#pragma once #include iostream // 红黑树节点信心判断 - 红黑节点 enum class Color { RED 1, BLACK 2 }; // 树节点信息 template class T // [核心修改处] struct RBTreeNode { T _data; // [核心修改处] RBTreeNodeT * _left; RBTreeNodeT * _right; RBTreeNodeT * _parent; Color _color; RBTreeNode(const T data) : _data(data) , _left(nullptr) , _right(nullptr) , _parent(nullptr) {} }; // 红黑树 templateclass K, class T, class KeyOfT // [核心修改处] class RBTree { using Node RBTreeNodeT; public: // 插入一个节点 bool Insert(const T data) { // 找到对应的位置并进行新增 if(_root nullptr) { _root new Node(data); _root-_color Color::BLACK; return true; } KeyOfT kot; Node* parent nullptr; Node* cur _root; while(cur) { if(kot(data) kot(cur-_data)) { parent cur; cur cur-_right; } else if(kot(data) kot(cur-_data)) { parent cur; cur cur-_left; } else { if(_isRepeat) { cur-_data data; return true; } else { return false; } } } // 找到插入位置 cur new Node(data); cur-_color Color::RED; // 非空就是填入红色 if(kot(parent-_data) kot(data)) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; // 结构调整 //父亲为红的将继续更新(出现了连续的红节点) //注意防止parent为空造成对空指针的访问 while(parent parent-_color Color::RED) { //父亲为红色关键看uncle Node* grandfather parent-_parent; if(grandfather-_left parent) { Node* uncle grandfather-_right; // 情况一: uncle 存在且为红 if(uncle uncle-_color Color::RED) { parent-_color uncle-_color Color::BLACK; grandfather-_color Color::RED; // 更新 cur grandfather; parent cur-_parent; } else { // 剩余情况: uncle 为空或者是黑色 if (cur parent-_left) { //单旋情况 // g // p u //c RotateR(grandfather); parent-_color Color::BLACK; grandfather-_color Color::RED; } else { //双旋情况 // g // p u // c RotateL(parent); RotateR(grandfather); cur-_color Color::BLACK; grandfather-_color Color::RED; } break; } } else { Node* uncle grandfather-_left; // 情况一: uncle 存在且为红 if(uncle uncle-_color Color::RED) { parent-_color uncle-_color Color::BLACK; grandfather-_color Color::RED; // 更新 cur grandfather; parent cur-_parent; } else { // 剩余情况: uncle 为空或者是黑色 if (cur parent-_right) { //单旋情况 // g // u p // c RotateL(grandfather); parent-_color Color::BLACK; grandfather-_color Color::RED; } else { //双旋情况 // g // u p // c RotateR(parent); RotateL(grandfather); cur-_color Color::BLACK; grandfather-_color Color::RED; } break; } } } // 成本低够靠谱结束之后不管任何情况把根变成黑色节点 _root-_color Color::BLACK; return true; } // 查找 Node* Find(const K key) { Node* cur _root; while(cur) { if(kot(cur-_data) key) cur cur-_left; else if(kot(cur-_data) key) cur cur-_right; else return cur; } return nullptr; } // 验证是否是红黑树[满足4条规则即可] bool Check(Node* root, int blackNum, const int refNum) { if (root nullptr) { // 前序遍历走到空时意味着一条路径走完了 if (refNum ! blackNum) { std::cout 存在黑色节点数量不相同的路径 std::endl; return false; } return true; } if (root-_color Color::RED root-_parent ! nullptr root-_parent-_color Color::RED) { std::cout kot(root-_data) 存在连续的红色节点 std::endl; return false; } if (root-_color Color::BLACK) { blackNum; } return Check(root-_left, blackNum, refNum) Check(root-_right, blackNum, refNum); } bool IsBalance() {...} // 辅助测试函数的工具 // 获取根节点 Node* GetRoot() { return _root;} // 获取节点颜色 Color GetColor(Node* node) {...} // 打印节点 key 颜色 void PrintNode(Node* node) {...} // 打印整棵树中序 void InOrder(Node* root) {...} // 打印整棵红黑树 void PrintTree() {...} private: // 右单旋 void RotateR(Node* parent) {...} // 左单旋 void RotateL(Node* parent) {...} private: Node* _root nullptr; bool _isRepeat false; };支持 iterator 的实现iterator核心源代码// 红黑树迭代器基类实现通用的前进/后退逻辑 struct __rb_tree_base_iterator { typedef __rb_tree_node_base::base_ptr base_ptr; base_ptr node; // 迭代器指向的红黑树节点 // 迭代器前进找到中序遍历的下一个节点即后继节点 void increment() { // 情况1当前节点有右子树 → 右子树的最左节点就是后继 if (node-right ! 0) { node node-right; while (node-left ! 0) node node-left; } // 情况2当前节点没有右子树 → 向上找祖先节点 else { base_ptr y node-parent; // 一直往上走直到当前节点不是父节点的右孩子 while (node y-right) { node y; y y-parent; } // 边界处理不是最右节点才更新到父节点 if (node-right ! y) node y; } } // 迭代器后退找到中序遍历的上一个节点即前驱节点 void decrement() { // 特殊情况当前节点是 header整棵树的伪头 // header 的右孩子是整棵树最大节点这里直接跳到最大值 if (node-color __rb_tree_red node-parent-parent node) node node-right; // 情况1当前节点有左子树 → 左子树的最右节点就是前驱 else if (node-left ! 0) { base_ptr y node-left; while (y-right ! 0) y y-right; node y; } // 情况2当前节点没有左子树 → 向上找祖先节点 else { base_ptr y node-parent; // 一直往上走直到当前节点不是父节点的左孩子 while (node y-left) { node y; y y-parent; } node y; } } }; // 红黑树迭代器模板类提供对外使用的迭代器接口 template class Value, class Ref, class Ptr struct __rb_tree_iterator : public __rb_tree_base_iterator { typedef Value value_type; typedef Ref reference; typedef Ptr pointer; typedef __rb_tree_iteratorValue, Value, Value* iterator; // 默认构造 __rb_tree_iterator() {} // 用节点构造迭代器 __rb_tree_iterator(link_type x) { node x; } // 拷贝构造 __rb_tree_iterator(const iterator it) { node it.node; } // 解引用返回节点存储的值的引用 reference operator*() const { return link_type(node)-value_field; } #ifndef __SGI_STL_NO_ARROW_OPERATOR // 箭头运算符返回值的指针支持 - 访问成员 pointer operator-() const { return (operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ // 前置调用基类 increment移动到下一个节点 self operator() { increment(); return *this; } // 前置--调用基类 decrement移动到上一个节点 self operator--() { decrement(); return *this; } // 迭代器相等比较判断指向的节点是否相同 inline bool operator(const __rb_tree_base_iterator x, const __rb_tree_base_iterator y) { return x.node y.node; } // 迭代器不等比较 inline bool operator!(const __rb_tree_base_iterator x, const __rb_tree_base_iterator y) { return x.node ! y.node; } };iterator 实现思路iterator 实现的大框架跟 list 的 iterator 思路是一致的用一个类型封装结点的指针再通过重载运算符实现让迭代器可以像指针一样去访问数据。这里的难点是operator和operator--的实现。之前在使用阶段我们分析过map和set的迭代器遵循中序遍历左子树 - 根结点 - 右子树。因此begin()会返回中序第一个结点的迭代器也就是整棵树最左侧节点的迭代器。迭代器的核心逻辑就是不看全局只看局部只考虑当前节点在中序遍历中的下一个节点。迭代器时如果当前节点的右子树不为空代表当前结点已经访问完成下一个要访问的结点就是右子树的中序第一个节点。而一棵树的中序第一个节点就是最左节点所以直接找到右子树的最左节点即可。迭代器时如果当前节点的右子树为空代表当前结点及其所在子树都已访问完成下一个要访问的结点在祖先节点中因此需要沿着当前节点到根的路径向上查找。如果当前结点是父亲的左孩子根据中序左子树 - 根结点 - 右子树的规则下一个访问的结点就是当前结点的父亲。例如it 指向 2525 右为空25 是 30 的左所以下一个访问的结点就是 30。是左就停止18 | it → 25无右子树 / \ | 25 是 30 的左孩子 → 左孩子 停止 10 30 | 下一个节点 30 / | 规则左停止 25 |如果当前结点是父亲的右孩子根据中序规则当前结点所在子树已访问完成父亲所在的子树也已访问完成那么需要继续向根节点方向向上查找直到找到一个孩子是父亲左孩子的祖先这个祖先就是中序遍历的下一个节点。例如it 指向 1515 右为空15 是 10 的右15 所在子树访问完成10 所在子树也访问完成继续向上找10 是 18 的左那么下一个访问的结点就是 18。是右就继续18 | it → 15无右子树 / \ | 15 是 10 的右孩子 → 右孩子 继续向上 10 30 | 10 是 18 的左孩子 → 左孩子 停止 / \ / | 下一个节点 18 5 15 25 | 规则右继续左停止end()如何表示呢当 it 指向 50 时it50 是 40 的右40 是 30 的右30 是 18 的右一直向上走到根都没有找到符合条件的祖先最终父亲为空这时我们把迭代器中的节点指针置为nullptr用nullptr来表示end()。需要注意的是STL 源码中红黑树增加了一个哨兵位头结点作为end()这个哨兵位与根节点互为父子左指针指向最左节点右指针指向最右节点。相比我们用nullptr作为end()功能上差别不大源码能实现的我们也能实现只需要在--end()时做特殊处理让迭代器指向最右节点即可具体可参考迭代器--的实现。迭代器--的实现思路与完全类似逻辑正好相反因为它的访问顺序可以理解为反向中序右子树 - 根结点 - 左子树具体参考下面代码实现。set的 iterator 不支持修改我们只需要把set的第二个模板参数改为const K即可RBTreeK, const K, SetKeyOfT _t;map的 iterator 不支持修改 key但可以修改 value我们只需要把map的第二个模板参数pair的第一个参数改为const K即可RBTreeK, pairconst K, V, MapKeyOfT _t;要支持完整的迭代器功能还有很多细节需要修改具体参考下面题目的代码。当然还有一种添加哨兵位来实现迭代器的方式这是标准库里面的实现方式通过这种方式的话找到begin()就可以通过header-left直接获取end()就是headerheader的parent指向rootroot的parent指向header。这里header设置为红色这样就可以和根节点进行很好的区分。还有我们自己实现时不按照库里的方式来是因为库里面的实现比较复杂。就拿插入来说我们每插入一个数据就可能需要对header的left和right进行重新维护删除操作同理。而且在一些旋转操作中也需要维护header的parent以及root的parent。但是我们不使用哨兵位方式实现也是存在缺陷的。注意普通的类就是一个完整的类类里面的内嵌类型内部类或者把一个类型typedef取别名都称为内部类。typedef RBTreeIteratorT, T, T* Iterator; // 内嵌类型 typedef RBTreeIteratorT, const T, const T* ConstIterator; // 内嵌类型这里有一个问题如果是类模板直接取它的内嵌类是不行的。因为编译器无法分辨出Iterator到底是一个类型还是一个静态变量。我们通过类域去访问成员时可以访问静态成员变量也可以访问内嵌类型但类模板没有实例化编译器根本不知道你要取的是哪一个因此会报错。所以我们为了能够让编译器顺利编译需要加上一个typename。这相当于告诉编译器这是一个类型不是变量。不然编译器无法识别毕竟我们本来就是要做 typedef 类型定义不可能把变量 typedef 成 iterator。作用就是先让编译通过等 RBTree 实例化之后再进入里面去找真正的内嵌类型typedef typename RBTreeK, K, SetKeyOfT::Iterator iterator;支持 map 的 operator [ ] 的实现map 要支持[]主要需要修改insert的返回值支持修改RBTree中的insert返回值为有了insert的支持[]的实现就很简单了具体参考下面代码实现operator [ ]具体参考本篇内容【点击进入】代码myset.h#pragma once #includeRBTree.h namespace rose { //set传两个K templateclass K class set { struct SetKeyOfT { const K operator()(const K key) { return key; } }; public: typedef typename RBTreeK, const K, SetKeyOfT::Iterator iterator; typedef typename RBTreeK, const K, SetKeyOfT::Const_Iterator const_iterator; iterator begin() { return _t.Begin(); } iterator end() { return _t.End(); } const_iterator begin() const { return _t.Begin(); } const_iterator end() const { return _t.End(); } pairiterator, bool insert(const K key) { return _t.Insert(key); } private: RBTreeK, const K, SetKeyOfT _t; }; }mymap.h#pragma once #includeRBTree.h namespace rose { //map传一个K一个pair templateclass K, class V class map { struct MapKeyOfT { const K operator()(const pairK, V kv) { return kv.first; } }; public: typedef typename RBTreeK, pairconst K, V, MapKeyOfT::Iterator iterator; typedef typename RBTreeK, pairconst K, V, MapKeyOfT::Const_Iterator const_iterator; iterator begin() { return _t.Begin(); } iterator end() { return _t.End(); } const_iterator begin() const { return _t.Begin(); } const_iterator end() const { return _t.End(); } pairiterator, bool insert(const pairK, V kv) { return _t.Insert(kv); } iterator find(const K key) { return _t.Find(key); } V operator[](const K key) { pairiterator, bool ret insert({ key,V() }); return ret.first-second; } private: RBTreeK, pairconst K, V, MapKeyOfT _t; }; }RBTree.h#pragma once #includeiostream #includeassert.h #includetime.h #includevector using namespace std; //枚举值表示颜色 enum Colour { RED, BLACK }; //这里我们默认按照Key-Value结构实现 //红黑树节点结构 templateclass T struct RBTreeNode { RBTreeNode(const T data) :_data(data) , _left(nullptr) , _right(nullptr) , _parent(nullptr) {} //这里更新控制平衡也要加入parent指针 T _data; RBTreeNodeT* _left; RBTreeNodeT* _right; RBTreeNodeT* _parent; Colour _col; }; templateclass T, class Ref, class Ptr struct RBTreeIterator { typedef RBTreeNodeT Node; typedef RBTreeIteratorT, Ref, Ptr Self; Node* _node; Node* _root;//为了实现--end() RBTreeIterator(Node* node, Node* root) :_node(node) , _root(root) {} Self operator() { if (_node-_right) { //右不为空中序下一个访问的节点是右子树的最左(最小)节点 Node* min _node-_right; while (min-_left) { min min-_left; } _node min; } else { //右为空祖先里面孩子是父亲左的那个祖先 Node* cur _node; Node* parent cur-_parent; //注意走到根节点 while (parent cur parent-_right) { cur parent; parent cur-_parent; } _node parent; } return *this; } Self operator--() { if (_node nullptr) // end() { // --end()特殊处理⾛到中序最后⼀个结点整棵树的最右结点 Node* rightMost _root; while (rightMost rightMost-_right) { rightMost rightMost-_right; } _node rightMost; } else if (_node-_left) { // 左⼦树不为空中序左⼦树最后⼀个 Node* rightMost _node-_left; while (rightMost-_right) { rightMost rightMost-_right; } _node rightMost; } else { // 孩⼦是⽗亲右的那个祖先 Node* cur _node; Node* parent cur-_parent; while (parent cur parent-_left) { cur parent; parent cur-_parent; } _node parent; } return *this; }; Ref operator*()//返回节点里面的数据 { return _node-_data; } Ptr operator-()//返回节点里面数据的指针 { return _node-_data; } //迭代器的比较就是比较节点的指针 bool operator!(const Self s)const { return _node ! s._node; } bool operator(const Self s)const { return _node s.node; } }; //红黑树实现 templateclass K, class T, class KeyOfT class RBTree { typedef RBTreeNodeT Node; public: typedef RBTreeIteratorT, T, T* Iterator;//内嵌类型 typedef RBTreeIteratorT, const T, const T* Const_Iterator;//内嵌类型 Iterator Begin() { Node* cur _root;; while (cur cur-_left) { cur cur-_left; } return Iterator(cur, _root); } Iterator End() { return Iterator(nullptr, _root); } Const_Iterator Begin() const { Node* cur _root;; while (cur cur-_left) { cur cur-_left; } return Const_Iterator(cur, _root); } Const_Iterator End() const { return Const_Iterator(nullptr, _root); } RBTree() default; RBTree(const RBTree t) { _root Copy(t._root); } RBTree operator(RBTree t) { swap(_root, t._root); return *this; } ~RBTree() { Destroy(_root); _root nullptr; } pairIterator, bool Insert(const T data) { if (_root nullptr) { _root new Node(data); _root-_col BLACK; //return pairIterator, bool(Iterator(_root, _root), true); //自己走隐式类型转化 return { Iterator(_root,_root), true }; } KeyOfT kot; Node* parent nullptr; Node* cur _root; while (cur) { if (kot(cur-_data) kot(data)) { parent cur; cur cur-_right; } else if (kot(cur-_data) kot(data)) { parent cur; cur cur-_left; } else { //如果数据已经存在对于set·map而言在这就插入失败了充当的是查找的功能 //返回跟key相等的那个值 return { Iterator(cur,_root), false }; } } cur new Node(data); //为了记录先建节点 Node* mark_node cur; cur-_col RED; if (kot(parent-_data) kot(data)) { parent-_right cur; } else { parent-_left cur; } //链接父亲 cur-_parent parent; //父亲为红的将继续更新(出现了连续的红节点) //注意防止parent为空造成对空指针的访问 while (parent parent-_col RED) { //父亲为红色关键看uncle Node* grandfather parent-_parent; if (grandfather-_left parent) { Node* uncle grandfather-_right; //情况一uncle存在且为红 //解决变色 if (uncle uncle-_col RED) { parent-_col uncle-_col BLACK; grandfather-_col RED; //继续往上处理 cur grandfather; parent cur-_parent; } else//剩余情况uncle不存在或者uncle存在且为黑 { if (cur parent-_left) { //单旋情况 // g // p u //c RotateR(grandfather); parent-_col BLACK; grandfather-_col RED; } else { //双旋情况 // g // p u // c RotateL(parent); RotateR(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } else { Node* uncle grandfather-_left; //情况一uncle存在且为红 //解决变色 if (uncle uncle-_col RED) { parent-_col uncle-_col BLACK; grandfather-_col RED; //继续往上处理 cur grandfather; parent cur-_parent; } else//剩余情况uncle不存在或者uncle存在且为黑 { if (cur parent-_right) { //单旋情况 // g // u p // c RotateL(grandfather); parent-_col BLACK; grandfather-_col RED; } else { //双旋情况 // g // u p // c RotateR(parent); RotateL(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } } //成本低够靠谱结束之后不管任何情况把根给变成黑色节点 _root-_col BLACK; //父亲为黑的就直接返回true还有插入的新节点 return { Iterator(mark_node,_root), true }; } //右单旋 void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) { subLR-_parent parent; } //修改parent节点属性之前记录parent的parent Node* pParent parent-_parent; subL-_right parent; parent-_parent subL; if (parent _root) { _root subL; subL-_parent nullptr; } else { if (pParent-_left parent) { pParent-_left subL; } else { pParent-_right subL; } subL-_parent pParent; } } //左单旋 void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) { subRL-_parent parent; } Node* pParent parent-_parent; subR-_left parent; parent-_parent subR; if (pParent nullptr) { _root subR; subR-_parent nullptr; } else { if (pParent-_left parent) { pParent-_left subR; } else { pParent-_right subR; } subR-_parent pParent; } } Node* Find(const K key) { Node* cur _root; while (cur) { if (cur-_kv.first key) { cur cur-_right; } else if (cur-_kv.first key) { cur cur-_left; } else { return cur; } } return nullptr; } int Height() { return _Height(_root); } int Size() { return _Size(_root); } void Destroy(Node* root) { if (root nullptr) return; Destroy(root-_left); Destroy(root-_right); delete root; } Node* Copy(Node* root) { if (root nullptr) return nullptr; Node* newRoot new Node(root-_kv); newRoot-_left Copy(root-_left); newRoot-_right Copy(root-_right); return newRoot; } private: int _Height(Node* root) { if (root nullptr) return 0; int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); return leftHeight rightHeight ? leftHeight 1 : rightHeight 1; } int _Size(Node* root) { if (root nullptr) return 0; return _Size(root-_left) _Size(root-_right) 1; } Node* _root nullptr; };