27.红黑树（上）

从根节点走到空算一条路径，这个有9条路径。最短最长不一定存在。

插入相同节点，avl高度更低，左右很均衡，红黑树不那么均衡，但效率不差，最短路径把他切开，就是满二叉树

avl树比红黑树更接近logN，红黑树比logN多一点，CPU很快没什么差别

h不为0，旋转加变色

变色+继续往上处理，变色要让这棵树之前是一个节点现在还是一个节点，向上处理就是爷爷节点变成红的红的，如果父亲也是红的，连续的红节点，继续处理。

#pragma once enum Colour { RED, BLACK }; template<class K, class V> struct RBTreeNode { // 这里更新控制平衡也要加入parent指针 pair<K, V> _kv; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; Colour _col; RBTreeNode(const pair<K, V>& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) {} }; template<class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; public: bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; 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); cur->_col = RED; if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } // 链接父亲 cur->_parent = parent; // 父亲是红色，出现连续的红色节点，需要处理 while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; if (parent == grandfather->_left) { // g // p u Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) { // 变色 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; // 继续往上处理 cur = grandfather; parent = cur->_parent; } } else { // g // u p Node* uncle = grandfather->_left; // 叔叔存在且为红，-》变色即可 } } _root->_col = BLACK; return true; }