二叉树详解（进阶）

1. 二叉搜索树

1.1 基本概念

1.2 基本操作

1.3 性能分析

1.4 键值对

2. AVL树和红黑树

2.1 AVL树

2.2 红黑树

3. 红黑树模拟实现STL中的map与set

1. 二叉搜索树

1.1 基本概念

二叉搜索树（BST，Binary Search Tree）：一颗二叉树，可以为空；如果不为空，满足以下性质：

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也都为二叉搜索树

如下示例：

中序遍历为升序。

由上性质：二叉搜索树也称二叉排序树或二叉查找树。

1.2 基本操作

示例结构：

template<class T>
class BSTreeNode
{typedef BSTreeNode<T> Node;
public:BSTreeNode(const T& data):_pleft(nullptr),_pright(nullptr),_data(data){}Node* _pleft;Node* _pright;T _data;
};template<class T>
class BSTree
{typedef BSTreeNode<T> Node;
public://增删查改//......
private:Node* _root = nullptr;
};

查找和插入：

从根开始比较，比根大则往右边走查找，比根小则往左边走查找；

最多查找高度次，走到空，还没找到，这个值不存在；

如果这个值不存在，就可以进行插入了。

示例代码:

//-----------------循环
//查找
bool find(const T& data)
{Node* cur = _root;while (cur){if (data < cur->_data)				cur = cur->_pleft;else if (data > cur->_data)		cur = cur->_pright;else return true;}return false;
}//插入
bool insert(const T& data)
{if (_root == nullptr){_root = new Node(data);return true;}Node* cur = _root, *parent = nullptr;while (cur){parent = cur;if (data > cur->_data)		cur = cur->_pright;else if (data < cur->_key)		cur = cur->_pleft;else return false;}Node* r = new Node(data);if (parent->_data > data)	parent->_pleft = r;else	parent->_pright = r;return true;
}//-----------------递归
bool findR(const T& data)
{return _findR(_root, data);
}bool insertR(const T& data)
{return _insertR(_root, data);
}
private:bool _findR(Node* root, const T& data){if (root == nullptr)		return false;if (root->_data == data)		return true;else if (root->_data > data)	return _findR(root->_pleft, data);else return _findR(root->_pright, data);}bool _insertR(Node*& root, const T& data){if (root == nullptr){root = new Node(data);return true;}if (data < root->_data){return _insertR(root->_pleft, data);}else if (data > root->_data){return _insertR(root->_pright, data);}else{return false;}}

删除：

情况一：没有孩子或只有一个孩子；删除该节点后，剩下的一个孩子（可为空）直接顶替已删除节点的逻辑位置。

情况二：有两个孩子；替换法：左子树的最大节点（最右值）或右子树的最小节点（最左值）与要删除节点 值交换，再删除（按情况一）。

示例代码：

//删除
bool erease(const T& data)
{Node* cur = _root, *parent = nullptr;while (cur){if (data < cur->_data){parent = cur;cur = cur->_pleft;}else if (data > cur->_data){parent = cur;cur = cur->_pright;}else{//找到了//情况1：没有孩子或只有一个孩子if (cur->_pleft == nullptr){if (parent == nullptr){_root = cur->_pright;}else{if (parent->_pleft == cur)	parent->_pleft = cur->_pright;else	parent->_pright = cur->_pright;}delete cur;}else if (cur->_pright == nullptr){if (parent == nullptr){_root = cur->_pleft;}else{if (parent->_pleft == cur)	parent->_pleft = cur->_pleft;else	parent->_pright = cur->_pleft;}delete cur;}//情况2：有两个孩子else{Node* right_min = cur->_pright, * right_min_parent = cur;while (right_min->_pleft){right_min = right_min->_pleft;}swap(cur->_data, right_min->_data);if (right_min_parent->_pleft == right_min)right_min_parent->_pleft = right_min->_pright;elseright_min_parent->_pright = right_min->_pright;delete right_min;}return true;}}return false;
}//-------------------递归
bool ereaseR(const T& data)
{return _ereaseR(_root, data);
}bool _ereaseR(Node*& root, const T& data)
{if (root == nullptr){return false;}if (data < root->_data){return _ereaseR(root->_pleft, data);}else if (data > root->_data){return _ereaseR(root->_pright, data);}else{Node* tmp = root;//情况1:if (root->_pleft == nullptr){root = root->_pright;delete tmp;}else if (root->_pright == nullptr){root = root->_pleft;delete tmp;}else{//情况2：Node* right_min = root->_pright;while (right_min->_pleft){right_min = right_min->_pleft;}std::swap(root->_data, right_min->_data);//递归可以控制删除的起点_ereaseR(root->_pright, data);}}return true;
}

1.3 性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有N个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个集合，如果各值插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树，图1)，其比较次数的时间复杂度为logN以2为底。

最差情况下，二叉搜索树退化为单支树(或者类似单支，图2)，其比较次数的时间复杂度为N。

如果退化成单支树，二叉搜索树的性能就没有了，那如何改进可以避免这种情况呢？别急，我们接着往下看。

1.4 键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息，即KV模型；

比如：商场停车场的收费系统，每次进入车辆都是一个新节点，这个节点中有两个重要变量，其中一个变量可用车牌号的唯一性标识每一辆车，即做key值；另一个变量，即对应的value，可填入入场时间；当车辆出停车场时，系统可根据车牌号key值，找到对应的value，和当前时间做差得到总停留时间，进而结合收费规则进行费用收取。

如果，key值不设对应的value，就叫K模型；

比如：进出小区的门卫系统，只有在该系统中找到进出者的信息，才能合规开闭门禁。

现实生活中，类似的例子还有很多，就不一一列举了，这里的重点是：提高抽象现实生活为模型化，即面向对象编程的能力。

现在，到你试着把上述参考代码修改为KV模型，并进行一些简单测试（比如：设计本汉译英的词典，字数统计等）。做完这个，接着往下看。

2. AVL树和红黑树

2.1 AVL树

在上面1.4所列举的例子中，系统如何对数据节点进行管理？—— 数据结构，如vector, list等，都可以；

所以，选哪个呢，或者说选择的标准是什么，也可以说管理的目的是什么？—— 数据结构只是管理的手段，目的是为用户提供稳定，可靠，高效的使用体验，这才是选择的标准；拿着标准去衡量手段，就可以做出合理的选择和取舍了。

在1.4的例子中，查找效率决定整个系统的效率，而在目前大家清晰的数据结构中，二叉搜索树应该是最合适的了，但是依旧可能出现1.3中的单支树或近似单支树的问题；因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法：

当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差（平衡因子）的绝对值不超过1（需要对树中的结点进行调整），即可降低树的高度，从而减少平均搜索长度。这样的二叉搜索树就叫做AVL树。

如下示例：（本文出现的平衡因子均= 右树高度 - 左树高度）

AVL树节点的定义在二叉搜索树节点定义的基础上增加了两个变量，一是节点指针变量_pparent指向父节点，另一个是整数平衡因子_bf。

重点操作：AVL树的插入

规则：

左树增加节点，p的_bf--，右树增加节点，p的_bf++；
如果插入节点后，p的_bf == 0，说明没有影响p的整棵树的高度，也就没有影响p祖先节点的平衡因子，所以不需要往上进行调节；
如果插入节点后，p的_bf == 1或-1，说明影响了p这棵树的高度，进而可能影响其祖先，此时循环往上调节平衡因子；
当p的_bf == 2或-2时，需要旋转。

（p表示插入节点的父节点/祖先节点）

旋转有四种情况，如下图： (h表示树的高度，红色表示插入位置，绿色表示平衡因子，蓝色表示旋转基点；选用哪种旋转的依据是：平衡因子的正负组合情况)

1. 新节点插入较高左子树的左侧：右单旋

2. 新节点插入较高右子树的右侧：左单旋

3. 新节点插入较高右子树的左侧：右左双旋（先右单旋，再左单旋）

4. 新节点插入较高左子树的右侧：左右双旋（先左单旋，再右单旋）

原理同上述点3，不再赘述。

至于删除操作，也一样按照二叉搜索树的方式将节点删除，然后再更新平衡因子，旋转调整，与插入不同的是，最差情况要一直调整到根节点，较为复杂，留给大家自行思考吧！

还有如何验证一颗树是不是AVL树等操作，上述一系列的完整参考代码可点击 AVLTree.h 前往我的Gitee仓库查看。

2.2 红黑树

在介绍红黑树之前，我们先对AVL树的性能做简单分析：AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即log_2 (N)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

因此，红黑树诞生，它较AVL树，不追求绝对的平衡，其只需保证最长路径不超过最短路径的2倍，在经常进行增删的结构中有效减少了旋转调整的次数，提升了效率，结构更稳定。

红黑树也是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black，只要满足以下规则：

1.根节点是黑色
2. 红节点的左右孩子为黑色——>红节点不连续
3. 每个节点到其叶子节点（这里指空节点）的黑色节点数目相等（空节点算黑色节点）

就使：从根节点开始到叶子节点的最长路径节点个数 <= 最短路径节点个数 * 2

如下图例：

和AVL树一样，这里也只深入探讨插入操作的调整旋转逻辑和参考实现代码，内容较多，请点击前往我的Gitee仓库查阅：调整旋转情况分类图示RBTree.jpg

参考代码RBTree.h

AVL树和RB树对比测试代码main.cpp

3. 红黑树模拟实现STL中的map与set

到这，请先熟悉STL中map与set的常见操作（点击直达查阅网页）；接着强烈建议您试着自己实现几个常见操作，如插入（insert），查找（find），重载【】等；涉及到模板的使用和常见问题的解决，正向迭代器的实现，如何利用适配器的模式实现反向迭代器，仿函数的运用等一系列知识模块，是一次不可或缺的综合性测试！

需要注意的是：STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪？能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行 -- 操作，必须要能找最后一个元素，此处就不行，因此最好的方式是增加头节点并将end()放在头结点的位置，也是为了反向迭代器的实现（如下图例）。