相信很多朋友知道二叉查找树不是严格的O(logN)，导致了在真实场景中没有用武之地，谁也不愿意有O(N)的情况发生，作为一名码农，肯定会希望能把“范围查找”做到地球人都不能优化的地步。当有很多数据灌到我的树中时，我肯定会希望最好是以“完全二叉树”的形式展现，这样我才能做到“查找”是严格的O(logN)，比如把这种”树“调正到如下结构。
这里就涉及到了“树节点”的旋转，也是我们今天要聊到的内容。
一：平衡二叉树（AVL）1：定义父节点的左子树和右子树的高度之差不能大于1，也就是说不能高过1层，否则该树就失衡了，此时就要旋转节点，在编码时，我们可以记录当前节点的高度，比如空节点是-1，叶子节点是0，非叶子节点的height往根节点递增，比如在下图中我们认为树的高度为h=2。
/// <summary>
/// 平衡二叉树节点
/// </summary>
/// <typeparam name="K"></typeparam>
/// <typeparam name="V"></typeparam>
public class AVLNode<K, V>
{
/// <summary>
/// 节点元素
/// </summary>
public K key;
/// <summary>
/// 增加一个高度信息
/// </summary>
public int height;
/// <summary>
/// 节点中的附加值
/// </summary>
public HashSet<V> attach = new HashSet<V>();
/// <summary>
/// 左节点
/// </summary>
public AVLNode<K, V> left;
/// <summary>
/// 右节点
/// </summary>
public AVLNode<K, V> right;
public AVLNode() { }
public AVLNode(K key, V value, AVLNode<K, V> left, AVLNode<K, V> right)
{
//KV键值对
this.key = key;
this.attach.Add(value);
this.left = left;
this.right = right;
}
}
节点再怎么失衡都逃不过4种情况，下面我们一一来看一下。
- 左左情况（左子树的左边节点）
我们看到，在向树中追加“节点1”的时候，根据定义我们知道这样会导致了“节点3"失衡，满足“左左情况“，可以这样想，把这棵树比作齿轮，我们在“节点5”处把齿轮往下拉一个位置，也就变成了后面这样“平衡”的形式，如果用动画解释就最好理解了。
/// <summary>
/// 第一种：左左旋转（单旋转）
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
public AVLNode<K, V> RotateLL(AVLNode<K, V> node)
{
//top：需要作为顶级节点的元素
var top = node.left;
//先截断当前节点的左孩子
node.left = top.right;
//将当前节点作为temp的右孩子
top.right = node;
//计算当前两个节点的高度
node.height = Math.Max(Height(node.left), Height(node.right)) + 1;
top.height = Math.Max(Height(top.left), Height(top.right)) + 1;
return top;
}
- 右右情况（右子树的右边节点）
同样，”节点5“满足”右右情况“，其实我们也看到，这两种情况是一种镜像，当然操作方式也大同小异，我们在”节点1“的地方将树往下拉一位，最后也就形成了我们希望的平衡效果。
/// <summary>
/// 第二种：右右旋转（单旋转）
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
public AVLNode<K, V> RotateRR(AVLNode<K, V> node)
{
//top：需要作为顶级节点的元素
var top = node.right;
//先截断当前节点的右孩子
node.right = top.left;
//将当前节点作为temp的右孩子
top.left = node;
//计算当前两个节点的高度
node.height = Math.Max(Height(node.left), Height(node.right)) + 1;
top.height = Math.Max(Height(top.left), Height(top.right)) + 1;
return top;
}
- 左右情况（左子树的右边节点）
从图中我们可以看到，当我们插入”节点3“时，“节点5”处失衡，注意，找到”失衡点“是非常重要的，当面对”左右情况“时，我们将失衡点的左子树进行"右右情况旋转"，然后进行”左左情况旋转“，经过这样两次的旋转就OK了，很有意思，对吧。
#region 第三种：左右旋转（双旋转）
/// <summary>
/// 第三种：左右旋转（双旋转）
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
public AVLNode<K, V> RotateLR(AVLNode<K, V> node)
{
//先进行RR旋转
node.left = RotateRR(node.left);
//再进行LL旋转
return RotateLL(node);
}
#endregion
- 右左情况(右子树的左边节点）
这种情况和“情景3”也是一种镜像关系，很简单，我们找到了”节点15“是失衡点，然后我们将”节点15“的右子树进行”左左情况旋转“，然后进行”右右情况旋转“，最终得到了我们满意的平衡。
#region 第四种：右左旋转（双旋转）
/// <summary>
/// 第四种：右左旋转（双旋转）
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
public AVLNode<K, V> RotateRL(AVLNode<K, V> node)
{
//执行左左旋转
node.right = RotateLL(node.right);
//再执行右右旋转
return RotateRR(node);
}
#endregion
如果我们理解了上面的这几种旋转，那么添加方法简直是轻而易举，出现了哪一种情况调用哪一种方法而已。
#region 添加操作
/// <summary>
/// 添加操作
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
/// <param name="tree"></param>
/// <returns></returns>
public AVLNode<K, V> Add(K key, V value, AVLNode<K, V> tree)
{
if (tree == null)
tree = new AVLNode<K, V>(key, value, null, null);
//左子树
if (key.CompareTo(tree.key) < 0)
{
tree.left = Add(key, value, tree.left);
//如果说相差等于2就说明这棵树需要旋转了
if (Height(tree.left) - Height(tree.right) == 2)
{
//说明此时是左左旋转
if (key.CompareTo(tree.left.key) < 0)
{
tree = RotateLL(tree);
}
else
{
//属于左右旋转
tree = RotateLR(tree);
}
}
}
//右子树
if (key.CompareTo(tree.key) > 0)
{
tree.right = Add(key, value, tree.right);
if ((Height(tree.right) - Height(tree.left) == 2))
{
//此时是右右旋转
if (key.CompareTo(tree.right.key) > 0)
{
tree = RotateRR(tree);
}
else
{
//属于右左旋转
tree = RotateRL(tree);
}
}
}
//将value追加到附加值中（也可对应重复元素）
if (key.CompareTo(tree.key) == 0)
tree.attach.Add(value);
//计算高度
tree.height = Math.Max(Height(tree.left), Height(tree.right)) + 1;
return tree;
}
#endregion
删除方法跟添加方法也类似，当删除一个结点的时候，可能会引起祖先结点的失衡，所以在每次”结点“回退的时候计算结点高度。
#region 删除当前树中的节点
/// <summary>
/// 删除当前树中的节点
/// </summary>
/// <param name="key"></param>
/// <param name="tree"></param>
/// <returns></returns>
public AVLNode<K, V> Remove(K key, V value, AVLNode<K, V> tree)
{
if (tree == null)
return null;
//左子树
if (key.CompareTo(tree.key) < 0)
{
tree.left = Remove(key, value, tree.left);
//如果说相差等于2就说明这棵树需要旋转了
if (Height(tree.left) - Height(tree.right) == 2)
{
//说明此时是左左旋转
if (key.CompareTo(tree.left.key) < 0)
{
tree = RotateLL(tree);
}
else
{
//属于左右旋转
tree = RotateLR(tree);
}
}
}
//右子树
if (key.CompareTo(tree.key) > 0)
{
tree.right = Remove(key, value, tree.right);
if ((Height(tree.right) - Height(tree.left) == 2))
{
//此时是右右旋转
if (key.CompareTo(tree.right.key) > 0)
{
tree = RotateRR(tree);
}
else
{
//属于右左旋转
tree = RotateRL(tree);
}
}
}
/*相等的情况*/
if (key.CompareTo(tree.key) == 0)
{
//判断里面的HashSet是否有多值
if (tree.attach.Count > 1)
{
//实现惰性删除
tree.attach.Remove(value);
}
else
{
//有两个孩子的情况
if (tree.left != null && tree.right != null)
{
//根据平衡二叉树的中顺遍历，需要找到”有子树“的最小节点
tree.key = FindMin(tree.right).key;
//删除右子树的指定元素
tree.right = Remove(tree.key, value, tree.right);
}
else
{
//自减高度
tree = tree.left == null ? tree.right : tree.left;
//如果删除的是叶子节点直接返回
if (tree == null)
return null;
}
}
}
//统计高度
tree.height = Math.Max(Height(tree.left), Height(tree.right)) + 1;
return tree;
}
#endregion
平衡二叉树已经有了，来一个范围检索, 查找 2012-7-30 4:00:00 到 2012-7-30 5:00:00 的登陆用户的ID，数据量在500w，看看平衡二叉树是如何秒杀对手。
class Program
{
static void Main(string[] args)
{
AVLTree<int, int> avl = new AVLTree<int, int>();
Dictionary<DateTime, int> dic = new Dictionary<DateTime, int>();
AVLTree<DateTime, int> tree = new AVLTree<DateTime, int>();
//500w
for (int i = 1; i < 5000000; i++)
{
dic.Add(DateTime.Now.AddMinutes(i), i);
tree.Add(DateTime.Now.AddMinutes(i), i);
}
//检索2012-7-30 4:00:00 到 2012-7-30 5:00:00的登陆人数
var min = Convert.ToDateTime("2012/7/30 4:00:00");
var max = Convert.ToDateTime("2012/7/30 5:00:00");
var watch = Stopwatch.StartNew();
var result1 = dic.Keys.Where(i => i >= min && i <= max).Select(i => dic[i]).ToList();
watch.Stop();
Console.WriteLine("字典查找耗费时间:{0}ms", watch.ElapsedMilliseconds);
watch = Stopwatch.StartNew();
var result2 = tree.SearchRange(min, max);
watch.Stop();
Console.WriteLine("平衡二叉树查找耗费时间:{0}ms", watch.ElapsedMilliseconds);
}
}
#region 平衡二叉树节点
/// <summary>
/// 平衡二叉树节点
/// </summary>
/// <typeparam name="K"></typeparam>
/// <typeparam name="V"></typeparam>
public class AVLNode<K, V>
{
/// <summary>
/// 节点元素
/// </summary>
public K key;
/// <summary>
/// 增加一个高度信息
/// </summary>
public int height;
/// <summary>
/// 节点中的附加值
/// </summary>
public HashSet<V> attach = new HashSet<V>();
/// <summary>
/// 左节点
/// </summary>
public AVLNode<K, V> left;
/// <summary>
/// 右节点
/// </summary>
public AVLNode<K, V> right;
public AVLNode() { }
public AVLNode(K key, V value, AVLNode<K, V> left, AVLNode<K, V> right)
{
//KV键值对
this.key = key;
this.attach.Add(value);
this.left = left;
this.right = right;
}
}
#endregion
public class AVLTree<K, V> where K : IComparable
{
public AVLNode<K, V> node = null;
#region 添加操作
/// <summary>
/// 添加操作
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
public void Add(K key, V value)
{
node = Add(key, value, node);
}
#endregion
#region 添加操作
/// <summary>
/// 添加操作
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
/// <param name="tree"></param>
/// <returns></returns>
public AVLNode<K, V> Add(K key, V value, AVLNode<K, V> tree)
{
if (tree == null)
tree = new AVLNode<K, V>(key, value, null, null);
//左子树
if (key.CompareTo(tree.key) < 0)
{
tree.left = Add(key, value, tree.left);
//如果说相差等于2就说明这棵树需要旋转了
if (Height(tree.left) - Height(tree.right) == 2)
{
//说明此时是左左旋转
if (key.CompareTo(tree.left.key) < 0)
{
tree = RotateLL(tree);
}
else
{
//属于左右旋转
tree = RotateLR(tree);
}
}
}
//右子树
if (key.CompareTo(tree.key) > 0)
{
tree.right = Add(key, value, tree.right);
if ((Height(tree.right) - Height(tree.left) == 2))
{
//此时是右右旋转
if (key.CompareTo(tree.right.key) > 0)
{
tree = RotateRR(tree);
}
else
{
//属于右左旋转
tree = RotateRL(tree);
}
}
}
//将value追加到附加值中（也可对应重复元素）
if (key.CompareTo(tree.key) == 0)
tree.attach.Add(value);
//计算高度
tree.height = Math.Max(Height(tree.left), Height(tree.right)) + 1;
return tree;
}
#endregion
#region 计算当前节点的高度
/// <summary>
/// 计算当前节点的高度
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
public int Height(AVLNode<K, V> node)
{
return node == null ? -1 : node.height;
}
#endregion
#region 第一种：左左旋转（单旋转）
/// <summary>
/// 第一种：左左旋转（单旋转）
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
public AVLNode<K, V> RotateLL(AVLNode<K, V> node)
{
//top：需要作为顶级节点的元素
var top = node.left;
//先截断当前节点的左孩子
node.left = top.right;
//将当前节点作为temp的右孩子
top.right = node;
//计算当前两个节点的高度
node.height = Math.Max(Height(node.left), Height(node.right)) + 1;
top.height = Math.Max(Height(top.left), Height(top.right)) + 1;
return top;
}
#endregion
#region 第二种：右右旋转（单旋转）
/// <summary>
/// 第二种：右右旋转（单旋转）
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
public AVLNode<K, V> RotateRR(AVLNode<K, V> node)
{
//top：需要作为顶级节点的元素
var top = node.right;
//先截断当前节点的右孩子
node.right = top.left;
//将当前节点作为temp的右孩子
top.left = node;
//计算当前两个节点的高度
node.height = Math.Max(Height(node.left), Height(node.right)) + 1;
top.height = Math.Max(Height(top.left), Height(top.right)) + 1;
return top;
}
#endregion
#region 第三种：左右旋转（双旋转）
/// <summary>
/// 第三种：左右旋转（双旋转）
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
public AVLNode<K, V> RotateLR(AVLNode<K, V> node)
{
//先进行RR旋转
node.left = RotateRR(node.left);
//再进行LL旋转
return RotateLL(node);
}
#endregion
#region 第四种：右左旋转（双旋转）
/// <summary>
/// 第四种：右左旋转（双旋转）
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
public AVLNode<K, V> RotateRL(AVLNode<K, V> node)
{
//执行左左旋转
node.right = RotateLL(node.right);
//再执行右右旋转
return RotateRR(node);
}
#endregion
#region 是否包含指定元素
/// <summary>
/// 是否包含指定元素
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public bool Contain(K key)
{
return Contain(key, node);
}
#endregion
#region 是否包含指定元素
/// <summary>
/// 是否包含指定元素
/// </summary>
/// <param name="key"></param>
/// <param name="tree"></param>
/// <returns></returns>
public bool Contain(K key, AVLNode<K, V> tree)
{
if (tree == null)
return false;
//左子树
if (key.CompareTo(tree.key) < 0)
return Contain(key, tree.left);
//右子树
if (key.CompareTo(tree.key) > 0)
return Contain(key, tree.right);
return true;
}
#endregion
#region 树的指定范围查找
/// <summary>
/// 树的指定范围查找
/// </summary>
/// <param name="min"></param>
/// <param name="max"></param>
/// <returns></returns>
public HashSet<V> SearchRange(K min, K max)
{
HashSet<V> hashSet = new HashSet<V>();
hashSet = SearchRange(min, max, hashSet, node);
return hashSet;
}
#endregion
#region 树的指定范围查找
/// <summary>
/// 树的指定范围查找
/// </summary>
/// <param name="range1"></param>
/// <param name="range2"></param>
/// <param name="tree"></param>
/// <returns></returns>
public HashSet<V> SearchRange(K min, K max, HashSet<V> hashSet, AVLNode<K, V> tree)
{
if (tree == null)
return hashSet;
//遍历左子树（寻找下界）
if (min.CompareTo(tree.key) < 0)
SearchRange(min, max, hashSet, tree.left);
//当前节点是否在选定范围内
if (min.CompareTo(tree.key) <= 0 && max.CompareTo(tree.key) >= 0)
{
//等于这种情况
foreach (var item in tree.attach)
hashSet.Add(item);
}
//遍历右子树（两种情况：①:找min的下限 ②：必须在Max范围之内）
if (min.CompareTo(tree.key) > 0 || max.CompareTo(tree.key) > 0)
SearchRange(min, max, hashSet, tree.right);
return hashSet;
}
#endregion
#region 找到当前树的最小节点
/// <summary>
/// 找到当前树的最小节点
/// </summary>
/// <returns></returns>
public AVLNode<K, V> FindMin()
{
return FindMin(node);
}
#endregion
#region 找到当前树的最小节点
/// <summary>
/// 找到当前树的最小节点
/// </summary>
/// <param name="tree"></param>
/// <returns></returns>
public AVLNode<K, V> FindMin(AVLNode<K, V> tree)
{
if (tree == null)
return null;
if (tree.left == null)
return tree;
return FindMin(tree.left);
}
#endregion
#region 找到当前树的最大节点
/// <summary>
/// 找到当前树的最大节点
/// </summary>
/// <returns></returns>
public AVLNode<K, V> FindMax()
{
return FindMin(node);
}
#endregion
#region 找到当前树的最大节点
/// <summary>
/// 找到当前树的最大节点
/// </summary>
/// <param name="tree"></param>
/// <returns></returns>
public AVLNode<K, V> FindMax(AVLNode<K, V> tree)
{
if (tree == null)
return null;
if (tree.right == null)
return tree;
return FindMax(tree.right);
}
#endregion
#region 删除当前树中的节点
/// <summary>
/// 删除当前树中的节点
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public void Remove(K key, V value)
{
node = Remove(key, value, node);
}
#endregion
#region 删除当前树中的节点
/// <summary>
/// 删除当前树中的节点
/// </summary>
/// <param name="key"></param>
/// <param name="tree"></param>
/// <returns></returns>
public AVLNode<K, V> Remove(K key, V value, AVLNode<K, V> tree)
{
if (tree == null)
return null;
//左子树
if (key.CompareTo(tree.key) < 0)
{
tree.left = Remove(key, value, tree.left);
//如果说相差等于2就说明这棵树需要旋转了
if (Height(tree.left) - Height(tree.right) == 2)
{
//说明此时是左左旋转
if (key.CompareTo(tree.left.key) < 0)
{
tree = RotateLL(tree);
}
else
{
//属于左右旋转
tree = RotateLR(tree);
}
}
}
//右子树
if (key.CompareTo(tree.key) > 0)
{
tree.right = Remove(key, value, tree.right);
if ((Height(tree.right) - Height(tree.left) == 2))
{
//此时是右右旋转
if (key.CompareTo(tree.right.key) > 0)
{
tree = RotateRR(tree);
}
else
{
//属于右左旋转
tree = RotateRL(tree);
}
}
}
/*相等的情况*/
if (key.CompareTo(tree.key) == 0)
{
//判断里面的HashSet是否有多值
if (tree.attach.Count > 1)
{
//实现惰性删除
tree.attach.Remove(value);
}
else
{
//有两个孩子的情况
if (tree.left != null && tree.right != null)
{
//根据平衡二叉树的中顺遍历，需要找到”有子树“的最小节点
tree.key = FindMin(tree.right).key;
//删除右子树的指定元素
tree.right = Remove(tree.key, value, tree.right);
}
else
{
//自减高度
tree = tree.left == null ? tree.right : tree.left;
//如果删除的是叶子节点直接返回
if (tree == null)
return null;
}
}
}
//统计高度
tree.height = Math.Max(Height(tree.left), Height(tree.right)) + 1;
return tree;
}
#endregion
}
wow,相差98倍，这可不是一个级别啊...AVL神器。