一、引入：二叉搜索树
平衡树实际为一种二叉搜索树（BST）。
对于一棵BST满足如下定义：
- 空树为一棵BST。
- 若根左子树非空，则左子树键值均小于根节点。
- 若根右子树非空，则右子树键值均大于根节点。
- 根左子树与右子树均为BST。
1. 插入操作
从根节点出发，让插入元素与当前节点键值进行比较，小于则向左递归，大于则向右递归，重复如此操作，直到找到合适的位置。
但若插入元素与某一节点键值相等该如何处理？对于严格BST，我们禁止出现重复键值，但我们可以进行处理：
- 若元素大于等于则向右递归（或小于等于向左），但当出现大量重复元素会导致树的平衡性出现问题。
- 我们可以给每个节点添加一个计数，当递归到重复键值节点，则当前节点计数加一（下文均以此方式进行插入，不做过多赘述）。
2. 删除操作
设删除节点计数为cnt，若cnt==0，则并不存在此节点，若cnt>1，则cnt--即可。
否则
- 若为叶子节点，直接删除。
- 若为只有一个儿子的链节点，用儿子顶替。
- 若有两个儿子，用左子树最大键值节点（或右子树最小键值节点）\(u\)的键值替换删除节点，易得\(u\)至多有一个子节点，即为链节点或叶子结点，对\(u\)进行删除操作即可。