AVL树
概念
加上了平衡条件的二叉搜索树，要求任何节点的左右子树高度差最多是1，可以降低树的高度，从而减少平均搜索长度
一颗AVL树或者空树，具有以下性质
它的左右子树都是AVL树
左右子树的高度差的绝对值不超多1（-1/0/1）
操作
节点定义
template<class K,class V> struct AVLTreenode { pair<K, V> _kv; AVLTreenode<K, V>* _left; AVLTreenode<K, V>* _right; AVLTreenode<K, V>* _parent; int _bf;//平衡因子 AVLTreenode(const pair<K, V>& kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) {} };
这里引进了一个新的概念平衡因子，简单来说就是：右子树的高度减去左子树的高度得到的结果就是该节点的平衡因子
插入
AVL树在插入元素方面与二叉搜索树大致相同，除了需要对平衡因子进行处理之外；所以插入的过程分为两步：1.按照二叉搜索树的方式插入新节点；2.调节平衡因子
插入新节点
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 (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if(cur->_kv.first > kv.first) { parent = cur; cur = cur->left; } else { return false; } } cur = new node(kv); if (parent->_kv.first > kv.first) { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } //更新平衡因子 }
更新平衡因子
插入节点在右，parent->_bf++
插入节点在左，parent->_bf--
if (cur == parent->_left) { parent->_bf--; } else { parent->_bf++; }
父节点的平衡因子更新过后，是否需要继续向上更新的依据是：子树的高度是否发生变化
parent->_bf==0，说明插入之前父节点就空缺了左右节点其中一个parent->_bf==-1/parent->_bf==1，而插入之后刚好补全了空缺；也就是说子树并没有发生变化，不需要继续向上更新
if (parent->_bf == 0) { break; }
parent->_bf==1/parent->_bf==-1，说明插入之前左右子树的高度一样，插入之后其中一边变得更高；由于子树的高度发生了变化，所以需要向上更新
else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = parent->_parent; }
parent->_bf==2/parent->_bf==-2，说明插入之前左右子树就已经一边高一边低；插入之后平衡已经被破坏，需要就地处理->旋转
旋转
旋转的核心思想：
使这颗子树的高度差不超过1；旋转过程中继续保持它是二叉搜索树；更新子节点的平衡因子；使子树的高度与插入之前保持一致
根据父节点的平衡因子和插入节点的平衡因子旋转的情景大志分为4种：
parent->_bf==2&&cur->_bf==1
旋转的具体操作：将节点6的左节点调整到节点5的右节点上；节点5变成节点6的左节点；节点6作为根指向ppnode
//左旋 void RotateL(node* parent) { node* subR = parent->_right; node* subRL = subR->_left; parent->_right = subRL; if (subRL) { subRL->_parent = parent; } node* ppnode = parent->_parent; subR->_left = parent; parent->_parent = subR; if (ppnode == nullptr) { _root = subR; _root->_parent = nullptr; } else { if (ppnode->_left = parent) { ppnode->_left = subR; } else { ppnode->_right = subR; } subR->_parent = ppnode; } parent->_bf = subR->_bf = 0; }
parent->_bf == -2 && cur->_bf == -1
旋转具体操作：将节点3的右节点调整到节点6的左节点上；节点6变成节点3的右节点；节点3作为根节点指向ppnode
//右旋 void RotateR(node* parent) { node* subL = parent->_left; node* subLR = subL->_right; parent->_left = subLR; if (subLR) { subLR->parent = parent; } node* ppnode = parent->_parent; subL->_right = parent; parent->_parent = subL; if (ppnode == nullptr) { _root = subL; _root->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subL; } else { ppnode->_right = subL; } subL->_parent = ppnode; } subL->_bf = parent->_bf = 0; }
parent->_bf == -2 && cur->_bf == 1
旋转操作：以节点3为轴点，进行左单旋，将节点6的左节点调整到节点3的右节点上；节点3变成节点6的左节点，节点6变成节点9的左节点；以节点9为轴点，进行右单旋，将节点6的右节点调整到节点9的左节点上；节点9变成节点6的右节点；节点6变成根节点指向ppnode
//左右双旋 void RotateLR(node* parent) { node* subL = parent->_left; node* subLR = subL->_right; int bf = subLR->_bf; RotateL(parent->_left); RotateR(parent); //subLR左子树新增节点 if (bf == -1) { subL->_bf = 0; parent->_bf = 1; subLR->_bf = 0; }//subLR右子树新增节点 else if (bf == 1) { parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; }//subLR自己是新增节点 else if (bf == 0) { parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } else { assert(false); } }
parent->_bf == 2 && cur->_bf == -1
旋转操作：以节点9为轴点，进行右单旋，将节点6的右节点调整到节点9的左节点上；节点9变成节点6的右节点，节点6变成节点3的右节点；以节点3为轴点进行左单旋，将节点6的左节点调整为节点3的右节点；节点3变成节点6的左节点，节点6变成根节点指向ppnode
//右左双旋 void RotateRL(node* parent) { node* subR = parent->_right; node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); //subRL右子树新增节点 if (bf == 1) { subR->_bf = 0; subRL->_bf = 0; parent->_bf = -1; } //subRL右子树新增节点 else if (bf == -1) { subR->_bf = 1; subRL->_bf = 0; parent->_bf = 0; } //subRL本身就是新增节点 else if (bf == 0) { subR->_bf = 0; subRL->_bf = 0; parent->_bf = 0; } else { assert(false); } }
红黑树（RBTree）
概念
AVL树之外，另一个颇具历史被广泛运用的平衡二叉树就是红黑树RBTree，所谓红黑树，不仅是一个二叉搜索树，而且必须满足以下规则
每个节点不是红色就是黑色
根节点为黑色
如果节点为红，其子节点必须为黑（注意，这里并不没有说明不可以是连续的黑色）
任意节点至树尾端的路劲，所含有的黑节点数必须相同
最长路径不超过最短路径的二倍
最长路径：黑红相间的路径
最短路径：全为黑色
根据规则4，新增节点必须是红色
节点的设计
红黑树有红黑两种颜色，并且拥有左右子节点，节点的设计如下
enum Color { RED, BLACK, }; template<class K,class V> struct RBTreenode { pair<K, V> _kv; RBTreenode<K, V>* _left; RBTreenode<K, V>* _right; RBTreenode<K, V>* _parent; Color _col; RBTreenode(const pair<K, V>& kv) :_kv(kv) ,_col(RED) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) {} };
