数据结构

Posted on

平衡二叉树

递归就是把只考虑一层，然后考虑边界条件，就像数学归纳法一样。注意的是不要每回合都算一遍。

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isBalanced(TreeNode root){
    return dfs(root)!=-1;
    
}
public int dfs(TreeNode root){
    if(root==null)return 0;
    int leftHeight=dfs(root.left);
    if(leftHeight==-1)return -1;
    int rightHeight=dfs(root.right);
    if(rightHeight==-1)return -1;
    if(Math.abs(leftHeight-rightHeight)>1)return -1;
    return Math.max(leftHeight,rightHeight)+1;
}

二叉查找树

左小右大，算法第四版

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
public class BST{
	private Node root;
    private class Node{
        //<k,value>用了int简化
        private int key;
        private int value;
        private Node left,right;
        private int size;
        public Node(int value;int N){
            this.value=value;
            size=N;
        }
    }
    
    //大小
    public int size(){
        return size(root);
    }
    private int size(Node n){
        if(n==null)return 0;
        else return n.size;
    }
    
    //查找
    public int get(int key){
		return get(root,key);
    }
    private int get(Node n,int key){
        if(n=null)return -1;
        if(key>n.key) return get(n.right,key);
        else if(key<n.key)return get(n.left,key);
        else return n.value;
    }
    
    //更新或者插入
    public int put(int key,int value){
        return put（root,key,value);
    }
    private Node put(Node n,int key,int value){
        if(n==null)reutrn new Node(key,value,1);//表示插入新节点
        if（key>n.key) n.right=put(n.right,key,value);
        else if(key<n.key)n.left=put(n.left,key,value);
        else x.value=value;
        return x;
    }
    pblic int min(){
        return min(root).key;
    }
    private Node min(Node n){
        if(n.left==null)return n;
        else return min(n.left);
    }
    //删除  只要改变树的节点，返回的类型都用Node ，这样在上一层种直接指向下一层种修改过的树节点。
    public void deleteMin(){
        root=deleteMin(root);
    }
    private Node deleteMin(Node x){
        if(x.left==null)return x.right;
        x.left=deleteMin(x.left);
        x.size=size(x.left)+size(x.right)+1;
        return x;
    }
    
    public void delete(int key){
        root=delete(root,key);
    }
    private Node delete(Node x,int key){
		if(x==null)return null;
        if(key<x.key)x.left=delete(x.left,key);
        else if(key>x.key)x.right=delete(x.right,key);
        else{
            if(x.right==null)return x.left;
            if(x.left==null)return x.right;
            Node t=x;
            x=min(t.right);
            x.right=deleteMin(t.right);
            x.left=t.left;
        }
        x.size=size(x.left)+size(x.right)+1;
        return x;
    }
    
}

（左倾）红黑树

非平衡二叉树，不平衡的节点的左连接改成红色的，叶节点一定是黑色的，

2-3树（和B树有点相似）中的3节点改为左斜的红色连接。

插入新节点的情况：

  • 插入到2节点的尾部：旋转即可
  • 3节点分种情况：
    • 最大：不用旋转，变色
    • 最小：一次旋转，变色
    • 中间：先左旋，再右旋，变色
  • 变色：左右变黑，头变红

删除：删除的是红色节点，不影响，可以直接删除。如果是黑色，就要进行变换，因此在向下的过程中，需要

  • 2-节点。左右子节点都是黑色

  • 3-节点。左右有一个为红色。

  • 4-节点。左右均为红色。

    2-3树变为红黑树，3-节点左倾右倾都一样，通过旋转可以互相转化。

删除最小值的时候：

在向下的过程中，如果为3-节点，及左节点为红色，直接递归一次，如果为2-节点，即h.left.left为黑色，先变色，在判断兄弟节点，如果为2-节点，即h.right.left为黑色（判断兄弟节点，都是left，红黑树是平衡的，h的左节点为2-节点，右节点高度必然大于等于左节点，不会出现空指针异常)。直接变色即可

2-节点

如果兄弟节点为3-节点，借点，

3-节点

删除最小值的时候：

向下的过程中，h为3-节点时（h.left为红色)首先右旋，因为最大值在右边，而树是左倾的。然后继续向下。

碰到右侧为2-节点时，左侧也是2-节点时，h.left.left为黑色，变色即可。

h.left.left为红色时，同样借个节点。

3-节点

删除任意节点时：

如果节点在底部，直接删除即可。

如果节点在中间，与其右子树的最小节点，或者左子树的最大节点与其替换，然后把替换的删除掉就行了。每一步都与删除最值的情况相同，只不过多了判断在左右子树的一步。

  • key <h.key 2-节点就根据兄弟节点情况，借点或者变色。3-节点继续递归。
  • 与删除最大值的情况相同，
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
public class RedBlack<Key extends Comparable<key>,Value>{
    private Node root;
    private static final boolean RED=true;
    private static final boolean BLACK=false;
    private class Node{
    	Key key;
        Value val;
        Node left,right;
        int N;
        boolean color;
    
        Node(Key key,Value val,int N,boolean color){
            this.key=key;
            this.val=val;
            this.N=N;
            this.color=color;
        }
    }
    private boolean isRed(Node x){
        if(x==null)return false;
        return x.color==RED;
    }
 	
    //没有判断是否为空？？？，如果左旋，节点一定要有右儿子，反之同理
    public Node rotateLeft(Node h){
		Node x=h.right;
        h.right=x.left;
        x.left=h;
        x.color=h.color;
        x.N=h.N;
        h.N=size(h.left)+size(h.right)+1;
        return x;
    }
    public Node rotateRight(Node h){
        Node x=h.left;
        h.left=x.right;
        x.right=h;
        x.color=h.color;
        x.N=h.N;
        h.N=size(h.left)+size（h.right)+1;
    }
        
    //变色
    private void flipColors(Node h){
        h.color=RED;
  		h.left.color=BLACK;
        h.right.color=BLACK;
    }
    //插入
    public void put(Key key,Value,value){
        root=put(root,key,val);
        root.color=BLACK;
    }
    private Node put(Node h,Key key, Value val){
        if(h==null){
            return new Node(key,val,1,RED);
        }
        int cmp=key.compareTo(h.key);
        if(cmp>0)h.right=put(h.right,key,val);
        else if(cmp<0)h.left=put(h.left,key,val);
        else h.val=val;
        //概括了所有情况
        if(isRed(h.right)&&!isRed(h.left))h=roteteLeft(h);
        if(isRed(h.left)&&isRed(h.left.left)) h=rotateRight(h);
        if(isRed(h.left)&&isRed(h.right))flipColors(h);
        //
        h.N=size(h.left)+size(h.right)+1;
        return h;
    }
 
    //把左边的2-节点变为红，从右侧兄弟节点借节点，其实是父结点变为左侧，右侧的一个节点变为父节点
    private Node removeRedLeft(Node h){
        flipColors(h);
        if(isRed(h.right.left)){
            h.right=rotateRight(h.right);
            h=rotateLeft(h);
            flipColors(h);
        }
        return h;
    }
    //删除之后修复
    private Node balance(Node h){
        if(isRed(h.right))h=rotateLeft(h);
      
        if(isRed(h.left)&&isRed(h.left.left))h=rotateRight(h);
        if(isRed(h.left)&&isRed(h.right))flipColors(h);
        h.N=size(h.left)+size(h.right)+1;
        return h;
    }
    //删除最小节点
    public void deleteMin(){
        if(isEmpty()) throw new NOSuchElementException();
        if(!isRed(root.left)&&!isRed(root.right))
            root.color=RED;
        root=deleteMin(root);
        if(!isEmpty())root.color=BLACK;
    }
    private Node deleteMin(Node h){
        if(h.left==null)
            return null;
        if(!isRed(h.left)&&!isRed(h.left.left))//是2-节点
            h=moveRedLeft(h);
        f.left=deleteMin(h.left);
        return balance(h);
    }
    //删除之后修复
    
    //删除最大节点
    private Node moveRedRight(Node h){
        flipColors(h);  //将h变黑，两个子节点变红
          if (isRed(h.left.left)) { 
            h = rotateRight(h);
            flipColors(h);
        }
        return h;
    }
    public void deleteMax(){
        if(!isRed(root.left)&&!isRed(root.right))
            root.color=RED;
        root=deleteMax(root);
        if(!isEmpty())root.color=BLACK;
    }
    private Node deleteMax(Node h){
        if(isRed(h.left))//左倾，只可能左边红。非红色，可能是左右均空，左右均黑
            h=rotateRight(h);
        if(h.right==null)//右边为空，左边只可能为空或者红，上一步已经判断红，可以直接返回空
            return null;
        if(!isRed(h.right))&&!isRed(h.right.left))//此时可能为左右均黑，第一步右旋的红，
            h=moveRedRight(h);                 //均为黑色是2-节点，转为3-节点。
        h.right=deleteMax(h.right);
        return balance(h);
    }
    
    //删除某个节点
    public void delete(Key key){
        if(!contains(key))return;
        if(!isRed(root.left)&&!isRed(root.right)){
            root.color=RED;
        }
        root=delete(root,key);
        if(!isEmpty())root.color=BLACK;
    }
    private Node delete(Node h,Key key){
        if(key.compareTo(h.key)<0){
            if(!isRed(h.left)&&!isRed(h.left.left))
                h=moveRedLeft(h);
            h.left=delete(h.left,key);
        }
        else{
            if(isRed(h.left))
                h=rotateRight(h);
            if(key.compareTo(h.key)==0&&(h.right)==null)
                return null;
            if(!isRed(h.right)&&!isRed(h.right.left))
                h=moveRedRight(h);
            if(key.compareTo(h.key)==0){
                Node x=min(h.right);
                h.key=x.key;
                h.val=x.val;
                h.right=deleteMin(h.right);
            }
            else h.right=delete(h.right,key);
        }
        return balance(h);
    }
    
}