树

AVL

AVL（Adelson-Velsky and Landis）树是一种自平衡二叉搜索树
对于树中的每一个节点，左、右子树的高度最多只能相差1

简介

搜索树上的大多数原始操作在O(h)时间内在高度为h树上运行,树的高度在一棵AVL树中，是O(lgN)

一棵AVL树是左右子树高度最大相差1的树(其中空树的高度定义为-1)
在高度为h的AVL树中，最少节点数S(h) = S(h-1) + S(h-2) + 1 ;h=0,S(h)=1;h=1,S(h)=2

AVL的平衡，旋转

AVL是特殊化的二叉树，想要保证AVL的平衡，我们可以用到一种称为平衡的做法。是否进行平衡的问题由树之间的高度决定

AVL的基础定义与高度计算

这里先给出AVL的基本定义以及高度计算 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//%AVL定义

private static class AvlNode<AnyType>
{
    AnyType elemenet ; 
    AvlNode<AnyType> left ; 
    AvlNode<AnyType> right ; 
    int height ;

    AvlNode(AnyType theElement){
        this(theElement,null,null);
    }

    AvlNode(AnyType theElement , AvlNode<AnyType> lt , AvlNode<AnyType> rt){
        elemenet = theElement ; 
        left = lt ; 
        right = rt ; 
    } 
}

高度计算: 

1
2
3
4
5
//%AVL高度计算
private int theHeight(AvlNode<AnyType> t){
    //返回高度，若满则-1
    return t == null ? -1:t.height ; 
}

旋转

实质上，我们设这里有a这个节点，在插入后只有以下四种情况：
1.对a左儿子的左子树进行插入(左、左，同向)
2.对a左儿子的右子树进行插入(左、右，异向)
3.对a右儿子的右子树进行插入(右、右，同向)
4.对a右儿子的左子树进行插入(右、左，异向)

具体理论和原理比较长，见书P86-P91,总之：
同向的情况用单旋转，异向的情况用双旋转
代码实现如下：

单旋转平衡(代码实现)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//% 单旋转
private Node rotateWithLeftChild(AvlNode<AnyType> k2){
    AvlNode<AnyType> k1 = k2.left ; 
    k2.left = k1.right ;
    k1.right = k2 ; 

    k2.height = Math.max(height(k2.left), height(k2.right)) + 1 ;
    k1.height = Math.max(height(k1.left), k2.height) + 1 ;

    return k1 ; 
}

private AvlNode<AnyType> rotateWithRightChild(AvlNode<AnyType> k2){
    AvlNode<AnyType> k1 = k2.right ; 
    k2.right = k1.left ; 
    k1.left = k2 ; 

    k2.height = Math.max(height(k2.left), height(k2.right)) + 1 ;
    k1.height = Math.max(height(k1.right),k2.height) + 1 ;
    return k1 ; 
}
双旋转平衡(代码实现)
1
2
3
4
5
6
7
8
9
10
11
12
//% 双旋转
private AvlNode<AnyType> doubleWithLeftChild(AvlNode<AnyType> k3){
    k3.left = rotateWithRightChild(k3.left) ; 

    return rotateWithLeftChild(k3) ; 
}

private AvlNode<AnyType> doubleWithRightChild(AvlNode<AnyType> k3){
    k3.left = rotateWithLeftChild(k3.left) ; 

    return rotateWithRightChild(k3) ; 
}

AVL的插入和平衡

AVL的核心就在于在插入之后会进行一次对树的平衡，具体做法已经在上一部分说过了，这里直接给出对应代码

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//% 插入
public AvlNode<AnyType> insert (AnyType x , AvlNode<AnyType> t)
{
    if(t == null){
        return new AvlNode<>(x,null,null) ; 
        //没有root的话，插入的第一个就是root
    }

    //查找位置，下面部分同正常的二叉树
    int compareResult = x.compareTo(t.elemenet) ; 
    if(compareResult < 0 ){
        t.left = insert(x,t.left);
    }else if(compareResult > 0 ){
        t.right = insert(x,t.right);
    }else{
        //
    }

    return blance(t) ; //返回的值是要重新平衡之后的树，平衡的方法见下面
}

//% 平衡
private static final int ALLOWED_IMBAKANCE = 1 ; //平衡高度差，就是1

private AvlNode<AnyType> balance(AvlNode<AnyType> t){
    if(t == null){
        return t ; 
    }

    //下面根据情况判断做单旋转还是双旋转，旋转的方法在blance方法后写出

    if(height(t.left) - height(t.right) > ALLOWED_IMBAKANCE){
        if(height(t.left.left) >= height(t.left.right)){
            //这里的“等于”是为了保证在对称情景（图4-33）的类似情景下，我们使用的是单旋转
            t = rotateWithLeftChild(t);
        }else{
            t = doubleWithLeftChild(t); 
        }
    }else{
        if(height(t.right)  - height(t.left) > ALLOWED_IMBAKANCE){
            if(height(t.right.right) >= height(t.right.left)){
            //这里的“等于”是为了保证在对称情景（图4-33）的类似情景下，我们使用的是单旋转
                t = rotateWithRightChild(t) ; 
            }else{
                t = doubleWithRightChild(t) ; 
            }
        }
    }

    //更新
    t.height = Math.max(height(t.left) , height(t.right)) + 1 ;
    return t  ;
}

AVL的删除

同前文，就是把插入改为删除，或者说“在二叉树原方法的基础上，最后加入平衡的步骤”
依旧是“寻值->操作/删除->再平衡->更新”

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//% 删除
//删除与插入是十分类似的
private AvlNode<AnyType> remove(AnyType x , AvlNode<AnyType> t){
    if(t == null){
        return ; //找不到就不进行操作
    }

    //这部分实质上就是在尝试寻找我们的x
    int compareResult = x.compareTo(t.elemenet);

    if(compareResult < 0){
        t.left = remove(x,t.left) ; 
    }else if(compareResult > 0 ){
        t.right = remove(x,t.right) ; 

    //不大不小，而且不是null，那就是找到了。下面根据情况做删除处理  
    }else if(t.left != null && t.right != null){
        //这里的处理同正常二叉树
        t.elemenet = findMin(t.right).elemenet ; 
        t.right = remove(t.elemenet , t.right);
    }else{
        t = (t.left != null) ? t.left : t.right ; 
    }

    //操作结束后平衡该树
    return balance(t) ; //返回平衡后的结果
}

小结

1.在AVL树中，对于树中的每个节点，左右子树的高度最多可以相差一个，即高度平衡。平衡是AVL的核心，毕竟是自平衡树
2.要删除的节点可以标记为已删除，因此不需要重新平衡
3.在平均情况和最坏情况下，搜索、插入和删除都需要 O(log_2 N) 时间
4.在某些情况下，AVL 树可能会偏重，导致性能相对较差

高级树简介

下面写的树多归“高级数据结构”内容了，这里只作简介/应试要求

红黑树

红黑树是 AVL 树的替代品，红黑树也是一种自平衡二叉搜索树
红背树的操作最坏情况下需要𝑂(lg𝑁)时间，红黑树的高度最多为2lg(𝑁+1)
红背树中的每个节点都需要一个额外的位来存储节点的颜色，可以是红色或黑色

红黑树确保从根到叶的路径不超过任何其他路径的两倍，因此树是近似平衡的

基本性质与基本介绍

1.每个节点都是红色或黑色
2.根root是黑色的
3.如果一个节点是红色的，它的两个子节点都将被涂成黑色
4.对于每个节点，从节点到后代叶子的所有简单路径都包含相同数量的黑色节点

插入

插入的基本规则是：
1.只能定为红或黑，其中根和null节点必须是黑
2.红节点的子节点必须是黑节点（这条结合步骤理解）
3.相同数量的黑色节点

步骤：
1.按照二叉搜索树中使用的插入规则插入节点
2.将新插入的节点涂成红色
3.如果违反规则，则从上到下修复颜色

小结

•红黑树是自平衡二叉搜索树
•每个节点需要一个额外的位来存储节点的颜色
•节点只能被着色为红色或黑色
•红黑树的开销相对较低插入
•在实践中，与 AVL 树相比，旋转发生的频率相对较低
•使用红黑树可以避免侧超权子树（普通的AVL是很容易发生偏移的）

伸展树SplayTrees

splay树保证从空树开始的任意M个连续树操作最多花费O（MlgN）时间
Splay树基于这样一个事实，即BST每次操作的O（N）最坏情况时间并不坏，只要它发生的频率相对较低,就是说不去把重点放在考虑处理最坏情况上，而是优化最坏情况发生的频率
splay树的基本思想是在一个节点被访问后，通过一系列的AVL树旋转将该节点推到根，在展开树中，如果一个节点很深，那么路径上有很多节点也比较深，通过展开我们可以使所有这些节点上的未来访问更快

基本性质

1.展开深度为 d 的节点 x 需要 𝜽(𝒅) 时间，即与访问 x 的时间成正比的时间

2.展开不仅将 x 移动到根，而且将访问路径上每个节点的深度大致减半

插入和删除节点需要 𝑶(𝐥𝐠𝑵) 摊销时间
在分析中，节点的电位可以是任意值，但是固定的

B树

渐近分析假设整个数据结构在计算机的主存中，当数据大小大于主存容量时，部分数据结构必须存储在磁盘上。如果发生这种情况，算法的渐进效率将变得毫无意义，因为磁盘访问比访问存储在内存中的数据慢得多。

B-tree 及其变体，如 B+-trees 和 B*-trees，是为了提高树操作的效率而开发的

基本性质

M 阶 B 树是 M 叉树
1.数据项存储在外部节点，每个内部节点最多存储 M-1 个密钥来指导搜索
2.密钥以非递减顺序存储
3.根要么是叶子，要么有 2 到 M 个子节点
4.所有内部节点（根节点除外）都有 M/2 和 M 个子节点
5.所有外部节点都处于相同深度，并且具有 L/2 和 L 之间的数据项

请注意，B 树有许多变体，每种变体的属性都略有不同。上述属性适用于 B-tree 的一种流行变体，称为 B+-tree

# 这是啥
整合了书和MIEC的内容

使用方式

同MIEC原笔记