AVL Tree is a binary search tree that height balanced. for each node, the heights of the left and right subtrees of x differ by at most 1
(.在中，
AVL树是最先发明的。在AVL树中任何节点的两个的高度最大差别为一，所以它也被称为。查找、插入和删除在平均和最坏情况下都是（log
n）。增加和删除可能需要通过一次或多次来重新平衡这个树。AVL树得名于它的发明者和，他们在1962年的论文《An algorithm for the organization of information》中发表了它。)多用wikipedia。
——————————————————————————————————————————————－
证明n的节点的AVL树高度为O(lg n). 引入渐进标记
数学符号O 的定义 O (g (n )) = { f (n ) : there exist positive constants c and n0 such that
0 ≤ f (n ) ≤ cg (n ) for all n ≥ n0 } .
We use O -notation to give an upper bound on a function, to within a constant
factor.
证明：暗示：利用归纳假设，和Fibonacci 数列.*/
____________________________________________________________________________________
左旋和右旋以及Blance()见伪代码。
效率：
1、插入构建AVL树用时为O(lg n). 因为树高为O(lg n),在各个调整节点时旋转中没有循环所以为O(1).
__________________________________________________________________________________
RB树和AVL树（RB树属于AVL树)是在Binary-Search-Tree上的进一步优化。
Red-Black Tree
A red-black tree is a binary search tree with one extra bit of storage per node: its
color, which can be either RED or BLACK. By constraining the way nodes can be
colored on any path from the root to a leaf, red-black trees ensure that no such path
is more than twice as long as any other, so that the tree is approximately balanced.
Each node of the tree now contains the fields color , key, left , right , and p. If
a child or the parent of a node does not exist, the corresponding pointer field of
the node contains the value NIL. We shall regard these NIL’s as being pointers to
external nodes (leaves) of the binary search tree and the normal, key-bearing nodes
as being internal nodes of the tree.
A binary search tree is a red-black tree if it satisfies the following red-black
properties:
1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all paths from the node to descendant leaves contain the same
number of black nodes.
红黑树是在二叉查找树上多了一个存储颜色的节点，颜色只能是红或者黑。根据遍历树时对颜色遍历来确保每个路径长不能超过其他路径长的2倍，几乎是平衡的。
每个节点有几个域，color, key, left, right , p. 如果child 或者 parent 节点不存在，那么相关节点就是NUL。可以将这些NUL节点看作BST的leaves，储存值在key中。
BST具有一下属性就是RB树。
1：每一个node不是黑就是红。
2：根结点是黑色
3：NIL(leaves)是黑色的
4: 如果节点颜色是红色的，那么孩子都是黑色的
5：对于任何一个节点，所有路径都包含相同数目的黑色节点。
对于红黑树的算法分析：自己分析
_________________________________________________________________________________
红黑树
并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
红黑树能够以O(log2 n)
的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构
能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。
当然，红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，例如，做一个哈希表，性能可能会更好一些。
在实际的系统中，例如，需要使用动态规则的防火墙系统，使用红黑树而不是散列表被实践证明具有更好的伸缩性。
______________________________
AVL树:
性质:
1>一棵n个结点的AVL树的其高度保持在0(log2(n)),不会超过3/2log2(n+1) /*这个我一直没有证明接下来我会试着证明下*/
2>一棵n个结点的AVL树的平均搜索长度保持在0(log2(n)).
3>一棵n个结点的AVL树删除一个结点做平衡化旋转所需要的时间为0(log2(n)).
从
1这点来看红黑树是牺牲了严格的高度平衡的优越条件为代价红黑树能够以O(log2
n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构
能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高.
看看人家怎么评价的:
AVL
trees are actually easier to implement than RB trees because there are
fewer cases. And AVL trees require O(1) rotations on an insertion,
whereas red-black trees require O(lg n).
In practice, the speed of
AVL trees versus red-black trees will depend on the data that you're
inserting. If your data is well distributed, so that an unbalanced
binary tree would generally be acceptable (i.e. roughly in random
order), but you want to handle bad cases anyway, then red-black trees
will be faster because they do less unnecessary rebalancing of already
acceptable data.On the other hand, if a pathological insertion order
(e.g. increasing order of key) is common, then AVL trees will be faster,
because the stricter balancing rule will reduce the tree's height.
Splay
trees might be even faster than either RB or AVL trees,depending on
your data access distribution. And if you can use a hash instead of a
tree, then that'll be fastest of all.
由于AVL树种类较少所以比红黑树实际上更容易实现.而且ALV树在旋转插入所需要的复杂度为0(1),而红
黑树则需要的复杂度为0(lgn).
实
际上插入AVL树和红黑树的速度取决于你所插入的数据.如果你的数据分布较好,则比较宜于采用AVL树(例如随机产生系列数),但是如果你想处理比较杂乱
的情况,则红黑树是比较快的,因为红黑树对已经处理好的数据重新平衡减少了不心要的操作.另外一方面,如果是一种非寻常的插入系列比较常见(比如,插入密钥系列),则AVL树比较快,因为它的严格的平衡规则将会减少树的高度.
Splay树可能比红黑树和AVL树还要快这也取决于你所访问的数据分布,如果你用哈希表来代替一棵树,则
将所以的树还要快.
Splay树是什么树,我不是很清楚,我没有详细的查阅.
感受一下带来的变革
/*
* 翻一下老皇历(2.4)
*/
struct vm_area_struct* find_vma(struct mm_struct* mm,unsigned long addr)
{
struct vm_area_struct* vma = NULL;
if(mm)
{
/*
* check the cache first.
*/
/*
* (Check hit rate is typically around 35%.)
*/
/*
* 首先查找一下最近一次访问的虚地址空间是不否是 CACHE中
*/
vma = mm->mmap_cache;
if(!(vma && vma->vm_end > addr && vma->vm_start
{
/*
* miss hit 未命中,继续查找线性表或者是AVL树
*/
if(!mm->mmap_val)
{
/*
* go though the liner list
*/
vma = mm->mmap;
while(vma && vma->vm_end <= addr)
{
vma = vam->vma_next;
}
}
else
{
/*
* Then go though the AVL tree quickly
*/
struct vm_area_struct* tree = mm->mmap_avl;
vam = NULL;
for(;;)
{
if(tree == vm_avl_empty)
{
/*
* 结点为空,失败
*/
break;
}
if(tree->vm_end > addr)
{
vma = tree;
if(tree->vm_start <= addr)
{
/*
* 找到,快速退出循环
*/
break;
}
tree = tree->vm_avl_left;
}
else
{
tree = tree->vm_avl_right;
}
}
}
if(vma)
{
/*
* 查找成功,记在CACHE中
*/
mm->mmap_cache = vma;
}
}
}
return vma;
}
//<--
/*
* 再贴新年历(2.6)
*/
//-->
struct vm_area_struct * find_vma(struct mm_struct * mm, unsigned long addr)
{
struct vm_area_struct *vma = NULL;
if (mm) {
/* Check the cache first. */
/* (Cache hit rate is typically around 35%.) */
/*
*
*/
vma = mm->mmap_cache;
if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) {
struct rb_node * rb_node;
/*
* miss hit 未命中,直接查找red-black tree
*/
rb_node = mm->mm_rb.rb_node;
vma = NULL;
while (rb_node) {
struct vm_area_struct * vma_tmp;
vma_tmp = rb_entry(rb_node,
struct vm_area_struct, vm_rb);
if (vma_tmp->vm_end > addr) {
vma = vma_tmp;
if (vma_tmp->vm_start <= addr)
break;
rb_node = rb_node->rb_left;
} else
rb_node = rb_node->rb_right;
}
/*
* 查找成功,记在CACHE中
*/
if (vma)
mm->mmap_cache = vma;
}
}
return vma;
}
/*最后的证明：
一棵n个结点的AVL树的其高度保持在0(log2(n)),不会超过3/2log2(n+1);
没有想出来。慢慢想。
