算法
AVL, 树, 算法

平衡二叉树

平衡二叉树是一种特殊的二叉排序树，每个节点左子树和右子树高度差至多等于1。

将二叉树上节点左子树深度减去右子树深度的值称为平衡因子BF，平衡二叉树上所有节点的平衡因子只可能是1，-1，0。

距离插入节点最近且平衡因子绝对值大于1的节点为根的子树，称为最小不平衡子树。

构建平衡二叉树时，每插入一个节点时，先检查是否因插入而破坏树的平衡性，若是则找出最小不平衡树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各个节点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。

  • 右旋：最小不平衡子树的BF和它的子树BF符号相同且最小不平衡子树的BF大于0
  • 左旋：最小不平衡子树的BF和它的子树BF符号相同且最小不平衡子树的BF小于零
  • 左右旋：最小不平衡子树的BF与它的子树的BF符号相反时且最小不平衡子树的BF大于0时，需要对节点先进行一次向左旋使得符号相同后，在向右旋转一次完成平衡操作。
  • 右左旋：最小不平衡子树的BF与它的子树的BF符号相反时且最小不平衡子树的BF小于0时，需要对节点先进行一次向右旋转使得符号相同时，在向左旋转一次完成平衡操作。

左旋LL

LL旋转

1
2
3
4
5
6
public TreeNode leftLeftRotation(TreeNode root) {
    TreeNode left = root.left;
    root.left = left.right;
    left.right = root;
    return left;
}

右旋RR

RR旋转

1
2
3
4
5
6
public TreeNode rightRightRotation(TreeNode root) {
    TreeNode right = root.right;
    root.right = right.left;
    right.left = root;
    return right;
}

左右旋LR

LR旋转

1
2
3
4
public TreeNode leftRightRotation(TreeNode root) {
    root.left = rightRightRotation(root.left);
    return leftLeftRotation(root);
}

右左旋RL

RL旋转

1
2
3
4
public TreeNode rightLeftRotation(TreeNode root) {
    root.right = leftLeftRotation(root.right);
    return rightRightRotation(root);
}

插入节点

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
public TreeNode insertAvl(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }
    if (val == root.val) {
        throw new RuntimeException("不允许添加相同的节点");
    }
    if (val < root.val) {
        root.left = insertAvl(root.left, val);
        // 插入节点后，若AVL树失去平衡，则进行相应的调节
        if (maxDepth(root.left) - maxDepth(root.right) == 2) {
            if (val < root.left.val) {
                return leftLeftRotation(root);
            } else {
                return leftRightRotation(root);
            }
        }
    } else {
        root.right = insertAvl(root.right, val);
        // 插入节点后，若AVL树失去平衡，则进行相应的调节
        if (maxDepth(root.right) - maxDepth(root.left) == 2) {
            if (val > root.right.val) {
                return rightRightRotation(root);
            } else {
                return rightLeftRotation(root);
            }
        }
    }
    return root;
}

删除节点

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 TreeNode remove(TreeNode root, int val) {
    if (root == null) {
        return null;
    }
    if (val < root.val) {
        root.left = remove(root.left, val);
        if (maxDepth(root.right) - maxDepth(root.left) == 2) {
            if (maxDepth(root.right.left) > maxDepth(root.right.right)) {
                return rightLeftRotation(root);
            } else {
                return rightRightRotation(root);
            }
        }
    } else if (val > root.val) {
        root.right = remove(root.right, val);
        if (maxDepth(root.left) - maxDepth(root.right) == 2) {
            if (maxDepth(root.left.right) > maxDepth(root.left.left)) {
                return leftRightRotation(root);
            } else {
                return leftLeftRotation(root);
            }
        }
    } else {
        if (root.left != null && root.right != null) {
            if (maxDepth(root.left) > maxDepth(root.right)) {
                int maxVal = findMax(root.left);
                root.val = maxVal;
                root.left = remove(root.left, maxVal);
            } else {
                int minVal = findMin(root.right);
                root.val = minVal;
                root.right = remove(root.right, minVal);
            }
        } else {
            return root.left != null ? root.left : root.right;
        }
    }
    return root;
}

public int findMax(TreeNode root) {
    if (root.left == null || root.right == null) {
        return root.val;
    }
    return findMax(root.right);
}

public int findMin(TreeNode root) {
    if (root.right == null || root.left == null) {
        return root.val;
    }
    return findMin(root.left);
}

有序数组转换成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
public TreeNode sortedArrayToBST(int[] nums) {
    return toBstTraversalLeft(nums, 0, nums.length - 1);
}

// 总是选择中间位置左边的数字作为根节点
public TreeNode toBstTraversalLeft(int[] nums, int left, int right) {
    if (left > right) {
        return null;
    }
    int mid = (left + right) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = toBstTraversalLeft(nums, left, mid - 1);
    root.right = toBstTraversalLeft(nums, mid + 1, right);
    return root;
}

// 总是选择中间位置右边的数字作为根节点
public TreeNode toBstTraversalRight(int[] nums, int left, int right) {
    if (left > right) {
        return null;
    }
    int mid = (left + right + 1) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = toBstTraversalRight(nums, left, mid - 1);
    root.right = toBstTraversalRight(nums, mid + 1, right);
    return root;
}

// 选择任意一个中间位置数字作为根节点
public TreeNode toBstTraversalRandom(int[] nums, int left, int right) {
    if (left > right) {
        return null;
    }
    int mid = (left + right + new Random().nextInt(2)) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = toBstTraversalRandom(nums, left, mid - 1);
    root.right = toBstTraversalRandom(nums, mid + 1, right);
    return root;
}

平衡二叉树判定

对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则 直接向上返回：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isBalanced(TreeNode treeNode) {
    return recur(treeNode) != -1;
}

public int recur(TreeNode treeNode) {
    if (treeNode == null) {
        return 0;
    }
    int leftDepth = recur(treeNode.leftNode);
    if (leftDepth == -1) {
        return -1;
    }
    int rightDepth = recur(treeNode.rightNode);
    if (rightDepth == -1) {
        return -1;
    }
    return Math.abs(leftDepth - rightDepth) < 2 ? Math.max(leftDepth, rightDepth) + 1 : -1;
}

B树

B树属于多叉树又名平衡多路查找树，数据库索引技术里大量使用者B树和B+树的数据结构。

红黑树

红黑树是一种含有红黑结点并能自平衡的二叉查找树。主要用于存储有序数据，查找时间复杂度为O(logn)，插入近似O(nlogn)，删除近似O(logn)。一棵含有n个节点的红黑树的高度至多为2log(n+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
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
public class RedBlackTree {
    private final int Red = 0; // 红色
    private final int Black = 1; // 黑色
    private class Node {
        int key = -1;       // 数据
        int color = Black;  // 颜色
        Node left = nil;    // nil表示的是叶子结点
        Node right = nil;   // 右节点
        Node parent = nil;  // 父节点
        Node(int key) {
            this.key = key;
        }
        @Override
        public String toString() {
            return "Node [key=" + key + ", color=" + color + ", left=" + left.key + ", right=" + right.key + ", p=" + parent.key + "]" + "\r\n";
        }
    }
    private final Node nil = new Node(-1);
    private Node root = nil;
    public void printTree(Node node) {
        if (node == nil) {
            return;
        }
        printTree(node.left);
        System.out.print(node.toString());
        printTree(node.right);
    }
    /**
     * 向红黑树插入节点
     */
    private void insert(Node node) {
        Node temp = root;
        if (root == nil) { // 若为根节点
            root = node;
            node.color = Black; // 将根节点设置为黑色
            node.parent = nil;  // 根节点父节点为null
        } else { // 不是根节点
            node.color = Red; // 将节点颜色设置为红色
            while (true) { // 完成节点插入
                if (node.key < temp.key) { // 插入节点位于左边
                    if (temp.left == nil) {
                        temp.left = node;
                        node.parent = temp;
                        break;
                    } else {
                        temp = temp.left;
                    }
                } else { // 插入节点位于右边
                    if (temp.right == nil) {
                        temp.right = node;
                        node.parent = temp;
                        break;
                    } else {
                        temp = temp.right;
                    }
                }
            }
            fixTree(node); // 平衡红黑树
        }
    }
    private void fixTree(Node node) {
        while (node.parent.color == Red) { // 若父节点为红色
            Node uncleNode = nil; // 当前节点的叔叔节点
            if (node.parent == node.parent.parent.left) { // 若插入节点的父节点为祖父节点的左节点
                uncleNode = node.parent.parent.right;
                if (uncleNode != nil && uncleNode.color == Red) { // 若叔叔节点存在且也为红色
                    node.parent.color = Black;  // 将父节点置为黑色
                    uncleNode.color = Black;            // 将叔叔节点置为黑色
                    node.parent.parent.color = Red; // 将祖父节点置为红色
                    node = node.parent.parent;  // 将当前节点置为祖父节点
                    continue;   // 重新进入循环
                }
                if (node == node.parent.right) { // 若当前节点是父节点的右节点
                    node = node.parent; // 将当前节点指向父节点
                    rotateLeft(node);   // 将当前节点左旋
                }
                node.parent.color = Black;      // 将当前节点父节点设置为黑色
                node.parent.parent.color = Red; // 将当前节点祖父节点设置为红色
                rotateRight(node.parent.parent);   // 将祖父节点右旋
            } else {
                uncleNode = node.parent.parent.left;
                if (uncleNode != nil && uncleNode.color == Red) {
                    node.parent.color = Black;
                    uncleNode.color = Black;
                    node.parent.parent.color = Red;
                    node = node.parent.parent;
                    continue;
                }
                if (node == node.parent.left) {
                    node = node.parent;
                    rotateRight(node);
                }
                node.parent.color = Black;
                node.parent.parent.color = Red;
                rotateLeft(node.parent.parent);
            }
        }
        root.color = Black;
    }
    void rotateLeft(Node node) {
        if (node.parent != nil) { // 若当前节点父节点不为null
            if (node == node.parent.left) { // 若当前节点是父节点的左节点
                node.parent.left = node.right; // 将当前节点父节点的左节点设置为当前节点的右节点
            } else { // 若当前节点是父节点的右节点
                node.parent.right = node.right; // 将当前节点父节点的右节点设置为当前节点的右节点
            }
            node.right.parent = node.parent;    // 将当前节点的右节点的父节点设置为当前节点父节点
            node.parent = node.right;           // 将当前节点的父节点设置为当前节点的右节点
            if (node.right.left != nil) {       // 当前节点原来的右节点的左节点不为null
                node.right.left.parent = node;  // 将当前节点的原来的右节点的左节点的父节点设置为当前节点
            }
            node.right = node.right.left;       // 将当前节点的右节点设置为，原来右节点的左节点
            node.parent.left = node;            // 将当前节点设置为其原来的右节点的左节点
        } else {    // 若当前节点父节点为null
            Node right = root.right;
            root.right = right.left;
            right.left.parent = root;
            root.parent = right;
            right.left = root;
            right.parent = nil;
            root = right;
        }
    }
    void rotateRight(Node node) {
        if (node.parent != nil) {
            if (node == node.parent.left) {
                node.parent.left = node.left;
            } else {
                node.parent.right = node.left;
            }
            node.left.parent = node.parent;
            node.parent = node.left;
            if (node.left.right != nil) {
                node.left.right.parent = node;
            }
            node.left = node.left.right;
            node.parent.right = node;
        } else {
            Node left = root.left;
            root.left = root.left.right;
            left.right.parent = root;
            root.parent = left;
            left.right = root;
            left.parent = nil;
            root = left;
        }
    }
    public void creatTree() {
        int[] data = new int[]{23, 32, 15, 221, 3};
        Node node;
        System.out.println(Arrays.toString(data));
        for (int i = 0; i < data.length; i++) {
            node = new Node(data[i]);
            insert(node);
        }
        printTree(root);
    }
    public static void main(String[] args) {
        RedBlackTree bst = new RedBlackTree();
        bst.creatTree();
    }
}