二叉搜索树 & 平衡树（c嘎嘎版）

定义：

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

1. 空树是二叉搜索树。

2. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。

3. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。

4. 二叉搜索树的左右子树均为二叉搜索树。

二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 N个结点的二叉搜索树中，这些操作的最优时间复杂度为O(logn) ，最坏为O(n) 。随机构造这样一棵二叉搜索树的期望高度为O(logn)  。

二叉搜索树节点的定义:

struct TreeNode{
	int key;
	TreeNode*left;
	TreeNode*right;
	//维护其他信息，如高度，节点数量。
	int size;//当前节点为根的子树大小
	int count;// 当前节点的重复数量
	TreeNode(int value)
      : key(value), size(1), count(1), left(nullptr), right(nullptr) {} 
};

遍历二叉搜索树

由二叉搜索树的递归定义可得，二叉搜索树的中序遍历权值的序列为非降的序列。时间复杂度为O(n)

void inOrderTraversal(TreeNode * root) 
{
    // 1. 如果当前节点为空，直接返回
    if (root == nullptr) {
        return;
    }

    // 2. 递归遍历左子树
    inOrderTraversal(root->left);

    // 3. 访问当前节点
    cout << root->key << ' ';

    // 4. 递归遍历右子树
    inOrderTraversal(root->right);    
}

查找最小/最大值

由二叉搜索树的性质可得，二叉搜索树上的最小值为二叉搜索树左链的顶点，最大值为二叉搜索树右链的顶点。时间复杂度为O(h)。

int findMin(TreeNode * root)
{
	if(root == nullptr) return -1;
	while(root ->left != nullptr) root = root ->left;
	
	return root ->key;
}
int findMax(TreeNode* root) {
  if (root == nullptr) {
    return -1;
  }
  while (root->right !&