AVL树的插入和删除

一、AVL 树

  在计算机科学中,AVL树是最早被发明的自平衡二叉查找树。在AVL树中,任一节点对应的两棵子树的最大高度差为 1,因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(log(n))。插入和删除元素的操作则可能需要借由一次或多次树旋转,以实现树的重新平衡。

  节点的平衡因子是它的左子树的高度减去它的右子树的高度(有时相反)。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的,并需要重新平衡这个树。平衡因子可以直接存储在每个节点中,或从可能存储在节点中的子树高度计算出来。

  大多数 BST 操作(例如,搜索,最大,最小,插入,删除等)花费 O(h) 时间,其中 h 是 BST 的高度。对于偏斜的二叉树,这些操作的成本可能变为 O(n)。如果确保每次插入和删除后树的高度都保持 O(log2n),则可以保证所有这些操作的 O(log2n)上限。AVL树的高度始终为 O(log2n),其中 n 是树中的节点数。

二、AVL 树的旋转

  AVL 树在普通的插入和删除节点时都会使得树失去平衡,这时我们需要一些操作来把树恢复平衡,这些操作叫做AVL树的旋转,分为左旋右旋

  T1,T2 和 T3 是树 y(左边) 或 x(右边) 的子树:

     y                                 x
    / \       Right Rotation          /  \
   x   T3     - - - - - - - >        T1   y 
  / \         < - - - - - - -            / \
 T1  T2       Left Rotation            T2  T3

  以上两个树中的键都遵循以下顺序(二叉查找树的性质):

  keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)。

 1     /**
 2      * 右旋转以y为根的子树
 3      *
 4      * @param y
 5      * @return
 6      */
 7     private Node rightRoate(Node y) {
 8         Node x = y.left;
 9         Node T2 = x.right;
10 
11         /* 执行旋转 */
12         x.right = y;
13         y.left = T2;
14 
15         /* 更新高度 */
16         y.height = max(height(y.left), height(y.right)) + 1;
17         x.height = max(height(x.left), height(x.right)) + 1;
18 
19         return x;
20     }
21 
22     /**
23      * 左旋转以x为根的子树
24      *
25      * @param x
26      * @return
27      */
28     private Node leftRoate(Node x) {
29         Node y = x.right;
30         Node T2 = y.left;
31 
32         /* 执行旋转 */
33         y.left = x;
34         x.right = T2;
35 
36         /* 更新高度 */
37         x.height = max(height(x.left), height(x.right)) + 1;
38         y.height = max(height(y.left), height(y.right)) + 1;
39 
40         return y;
41     }

三、AVL 树的插入操作

插入要遵循的步骤:

  新插入的节点为 w 

  1)对 w 执行标准 BST 插入。

  2)从 w 开始,向上移动并找到第一个不平衡节点。令 z 为第一个不平衡节点,y 为从 w 到 z 的路径中 z 的子代,x 为从 w 到 z 的路径中 z 的孙代。

  3)通过对以 z 为根的子树执行适当的旋转重新平衡树。可能有 4 种可能的情况需要处理,因为 x,y 和 z 可以 4 种方式排列。以下是可能的 4 种排列方式:

    a)y 是 z 的左子代,x 是 y 的左子代(左案例)

         z                                      y 
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z
      / \          - - - - - - - - ->      /  \    /  \ 
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2

    b)y 是 z 的左子代,x 是 y 的右子代(左案例)

     z                               z                           x
    / \                            /   \                        /  \ 
   y   T4  Left Rotate (y)        x    T4  Right Rotate(z)    y      z
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
T1   x                          y    T3                    T1  T2 T3  T4
    / \                        / \
  T2   T3                    T1   T2

    c)y 是 z 的右子代,x 是 y 的右子代(右右案例)

  z                                y
 /  \                            /   \ 
T1   y     Left Rotate(z)       z      x
    /  \   - - - - - - - ->    / \    / \
   T2   x                     T1  T2 T3  T4
       / \
     T3  T4

    d)y 是 z 的右子代,x 是 y 的左子代(右左案例)

   z                            z                            x
  / \                          / \                          /  \ 
T1   y   Right Rotate (y)    T1   x      Left Rotate(z)   z      y
    / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
   x   T4                      T2   y                  T1  T2  T3  T4
  / \                              /  \
T2   T3                           T3   T4

  插入操作:

 1     /**
 2      * AVL树的插入
 3      *
 4      * @param node
 5      * @param key
 6      * @return
 7      */
 8     private Node insert(Node node, int key) {
 9         /* 执行正常的BST插入 */
10         if (node == null)
11             return (new Node(key));
12 
13         if (key < node.key)
14             node.left = insert(node.left, key);
15         else if (key > node.key)
16             node.right = insert(node.right, key);
17         else    // 不允许重复的key
18             return node;
19 
20         /* 更新此祖先节点的高度 */
21         node.height = 1 + max(height(node.left), height(node.right));
22 
23         /* 获取此祖先的平衡因子以检查此节点是否变为不平衡 */
24         int balance = getBalance(node);
25 
26         /* 如果此节点变得不平衡,则存在有4种情况 */
27         if (balance > 1 && key < node.left.key) {
28             return rightRoate(node);
29         }
30 
31         if (balance < -1 && key > node.right.key) {
32             return leftRoate(node);
33         }
34 
35         if (balance > 1 && key > node.left.key) {
36             node.left = leftRoate(node.left);
37             return rightRoate(node);
38         }
39 
40         if (balance < -1 && key < node.right.key) {
41             node.right = rightRoate(node.right);
42             return leftRoate(node);
43         }
44 
45         return node;
46     }

四、AVL 树的删除操作

删除要遵循的步骤:

  令 w 为要删除的节点

  1)对 w 执行标准BST删除。

  2)从 w 开始,向上移动并找到第一个不平衡节点。令 z 为第一个不平衡节点,y 为 z 的较大孩子,x 为 y 的较大孩子。请注意,x 和 y 的定义与此处的插入不同。

  3)通过对以 z 为根的子树执行适当的旋转来重新平衡树。有 4 种可能的情况需要处理,因为 x,y 和 z 可以 4 种方式排列。以下是可能的 4 种排列方式:

    a)y 是 z 的左子代,x是y的左子代(左案例)

         z                                      y 
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z
      / \          - - - - - - - - ->      /  \    /  \ 
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2

    b)y 是 z 的左子代,x 是 y 的右子代(左案例)

     z                               z                           x
    / \                            /   \                        /  \ 
   y   T4  Left Rotate (y)        x    T4  Right Rotate(z)    y      z
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
T1   x                          y    T3                    T1  T2 T3  T4
    / \                        / \
  T2   T3                    T1   T2

    c)y 是 z 的右子代,x 是 y 的右子代(右右案例)

  z                                y
 /  \                            /   \ 
T1   y     Left Rotate(z)       z      x
    /  \   - - - - - - - ->    / \    / \
   T2   x                     T1  T2 T3  T4
       / \
     T3  T4

    d)y 是 z 的右子代,x 是 y 的左代子(右左案例)

 

   z                            z                            x
  / \                          / \                          /  \ 
T1   y   Right Rotate (y)    T1   x      Left Rotate(z)   z      y
    / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
   x   T4                      T2   y                  T1  T2  T3  T4
  / \                              /  \
T2   T3                           T3   T4

  与插入不同,在删除中,在 z 处进行旋转后,可能必须在 z 的祖先处进行旋转。因此,我们必须继续追踪路径,直到到达根为止。

  删除操作:

 1     /**
 2      * AVL树的删除
 3      *
 4      * @param N
 5      * @return
 6      */
 7     private Node deleteNode(Node root, int key) {
 8         if (root == null)
 9             return root;
10         /* 如果要删除的key小于root的key,则它位于左子树中 */
11         if (key < root.key)
12             root.left = deleteNode(root.left, key);
13 
14         /* 如果要删除的key大于root的key,则它位于右子树中 */
15         else if (key > root.key)
16             root.right = deleteNode(root.right, key);
17 
18         /* 如果key与root的key相同,则这个节点要被删除 */
19         else {
20             /* 只有一个孩子或没有孩子的节点 */
21             if ((root.left == null) || (root.right == null)) {
22                 Node temp = null;
23                 if (temp == root.left)
24                     temp = root.right;
25                 else
26                     temp = root.left;
27 
28                 /* 没有孩子的情况 */
29                 if (temp == null) {
30                     temp = root;
31                     root = null;
32                 } else {    // 只有一个孩子
33                     root = temp; // 复制非空孩子的内容
34                 }
35 
36             } else {
37                 /* 有两个子节点的节点:获取后继节点(在右侧子树中最小) */
38                 Node temp = minValueNode(root.right);
39                 /* 将后继节点的数据复制到此节点 */
40                 root.key = temp.key;
41                 /* 删除后继节点 */
42                 root.right = deleteNode(root.right, temp.key);
43             }
44         }
45 
46         /* 如果树只有一个节点,则返回 */
47         if (root == null)
48             return root;
49 
50         /* 更新当前节点的高度 */
51         root.height = max(height(root.left), height(root.right)) + 1;
52         /* 获取此节点的平衡因素 */
53         int balance = getBalance(root);
54 
55         /* 如果此节点变得不平衡,则有4种情况 */
56         if (balance > 1 && getBalance(root.left) >= 0) {
57             return rightRoate(root);
58         }
59 
60         if (balance > 1 && getBalance(root.left) < 0) {
61             root.left = leftRoate(root.left);
62             return rightRoate(root);
63         }
64 
65         if (balance < -1 && getBalance(root.right) <= 0) {
66             return leftRoate(root);
67         }
68 
69         if (balance < -1 && getBalance(root.right) > 0) {
70             root.right = rightRoate(root.right);
71             return leftRoate(root);
72         }
73 
74         return root;
75     }

本文源代码:

AVL树的插入和删除
  1 package algorithm;
  2 
  3 /**
  4  * 自平衡二叉树,左右子树的高度差不大于1
  5  */
  6 public class AVLTree {
  7 
  8     private Node root;
  9 
 10     /**
 11      * 树高度
 12      *
 13      * @param N
 14      * @return
 15      */
 16     private int height(Node N) {
 17         if (N == null) {
 18             return 0;
 19         }
 20         return N.height;
 21     }
 22 
 23     private int max(int a, int b) {
 24         return Math.max(a, b);
 25     }
 26 
 27     /**
 28      * 右旋转以y为根的子树
 29      *
 30      * @param y
 31      * @return
 32      */
 33     private Node rightRoate(Node y) {
 34         Node x = y.left;
 35         Node T2 = x.right;
 36 
 37         /* 执行旋转 */
 38         x.right = y;
 39         y.left = T2;
 40 
 41         /* 更新高度 */
 42         y.height = max(height(y.left), height(y.right)) + 1;
 43         x.height = max(height(x.left), height(x.right)) + 1;
 44 
 45         return x;
 46     }
 47 
 48     /**
 49      * 左旋转以x为根的子树
 50      *
 51      * @param x
 52      * @return
 53      */
 54     private Node leftRoate(Node x) {
 55         Node y = x.right;
 56         Node T2 = y.left;
 57 
 58         /* 执行旋转 */
 59         y.left = x;
 60         x.right = T2;
 61 
 62         /* 更新高度 */
 63         x.height = max(height(x.left), height(x.right)) + 1;
 64         y.height = max(height(y.left), height(y.right)) + 1;
 65 
 66         return y;
 67     }
 68 
 69     /**
 70      * 获取N结点的平衡
 71      *
 72      * @param N
 73      * @return
 74      */
 75     private int getBalance(Node N) {
 76         if (N == null)
 77             return 0;
 78 
 79         return height(N.left) - height(N.right);
 80     }
 81 
 82     /**
 83      * AVL树的插入
 84      *
 85      * @param node
 86      * @param key
 87      * @return
 88      */
 89     private Node insert(Node node, int key) {
 90         /* 执行正常的BST插入 */
 91         if (node == null)
 92             return (new Node(key));
 93 
 94         if (key < node.key)
 95             node.left = insert(node.left, key);
 96         else if (key > node.key)
 97             node.right = insert(node.right, key);
 98         else    // 不允许重复的key
 99             return node;
100 
101         /* 更新此祖先节点的高度 */
102         node.height = 1 + max(height(node.left), height(node.right));
103 
104         /* 获取此祖先的平衡因子以检查此节点是否变为不平衡 */
105         int balance = getBalance(node);
106 
107         /* 如果此节点变得不平衡,则存在有4种情况 */
108         if (balance > 1 && key < node.left.key) {
109             return rightRoate(node);
110         }
111 
112         if (balance < -1 && key > node.right.key) {
113             return leftRoate(node);
114         }
115 
116         if (balance > 1 && key > node.left.key) {
117             node.left = leftRoate(node.left);
118             return rightRoate(node);
119         }
120 
121         if (balance < -1 && key < node.right.key) {
122             node.right = rightRoate(node.right);
123             return leftRoate(node);
124         }
125 
126         return node;
127     }
128 
129     /**
130      * 给定一个非空的二叉查找树,返回树中最小key值的结点(注意无需遍历整个树)
131      *
132      * @param node
133      * @return
134      */
135     private Node minValueNode(Node node) {
136         Node current = node;
137 
138         while (current.left != null)
139             current = current.left;
140 
141         return current;
142     }
143 
144     /**
145      * AVL树的删除
146      *
147      * @param N
148      * @return
149      */
150     private Node deleteNode(Node root, int key) {
151         if (root == null)
152             return root;
153         /* 如果要删除的key小于root的key,则它位于左子树中 */
154         if (key < root.key)
155             root.left = deleteNode(root.left, key);
156 
157         /* 如果要删除的key大于root的key,则它位于右子树中 */
158         else if (key > root.key)
159             root.right = deleteNode(root.right, key);
160 
161         /* 如果key与root的key相同,则这个节点要被删除 */
162         else {
163             /* 只有一个孩子或没有孩子的节点 */
164             if ((root.left == null) || (root.right == null)) {
165                 Node temp = null;
166                 if (temp == root.left)
167                     temp = root.right;
168                 else
169                     temp = root.left;
170 
171                 /* 没有孩子的情况 */
172                 if (temp == null) {
173                     temp = root;
174                     root = null;
175                 } else {    // 只有一个孩子
176                     root = temp; // 复制非空孩子的内容
177                 }
178 
179             } else {
180                 /* 有两个子节点的节点:获取后继节点(在右侧子树中最小) */
181                 Node temp = minValueNode(root.right);
182                 /* 将后继节点的数据复制到此节点 */
183                 root.key = temp.key;
184                 /* 删除后继节点 */
185                 root.right = deleteNode(root.right, temp.key);
186             }
187         }
188 
189         /* 如果树只有一个节点,则返回 */
190         if (root == null)
191             return root;
192 
193         /* 更新当前节点的高度 */
194         root.height = max(height(root.left), height(root.right)) + 1;
195         /* 获取此节点的平衡因素 */
196         int balance = getBalance(root);
197 
198         /* 如果此节点变得不平衡,则有4种情况 */
199         if (balance > 1 && getBalance(root.left) >= 0) {
200             return rightRoate(root);
201         }
202 
203         if (balance > 1 && getBalance(root.left) < 0) {
204             root.left = leftRoate(root.left);
205             return rightRoate(root);
206         }
207 
208         if (balance < -1 && getBalance(root.right) <= 0) {
209             return leftRoate(root);
210         }
211 
212         if (balance < -1 && getBalance(root.right) > 0) {
213             root.right = rightRoate(root.right);
214             return leftRoate(root);
215         }
216 
217         return root;
218     }
219 
220     /**
221      * 先序遍历
222      *
223      * @param node
224      */
225     private void preOrder(Node node) {
226         if (node != null) {
227             System.out.print(node.key + " ");
228             preOrder(node.left);
229             preOrder(node.right);
230         }
231     }
232 
233     public static void main(String[] args) {
234 
235         /* ---------------------------------------------------- */
236 
237         AVLTree tree = new AVLTree();
238 
239         /* 构造AVL树 */
240         tree.root = tree.insert(tree.root, 9);
241         tree.root = tree.insert(tree.root, 5);
242         tree.root = tree.insert(tree.root, 10);
243         tree.root = tree.insert(tree.root, 0);
244         tree.root = tree.insert(tree.root, 6);
245         tree.root = tree.insert(tree.root, 11);
246         tree.root = tree.insert(tree.root, -1);
247         tree.root = tree.insert(tree.root, 1);
248         tree.root = tree.insert(tree.root, 2);
249 
250         /* 构造的AVL树:
251                  9
252                 / \
253                1   10
254               / \    \
255              0   5   11
256             /   / \
257            -1  2   6
258         */
259         System.out.println("Preorder traversal of constructed tree is : ");
260         tree.preOrder(tree.root);
261 
262         tree.root = tree.deleteNode(tree.root, 10);
263 
264         /* 删除10后的AVL树:
265                   1
266                 /   \
267                0     9
268               /     / \
269             -1     5   11
270             / \
271            2   6
272         */
273         System.out.println();
274         System.out.println("Preorder traversal after "+
275                 "deletion of 10 :");
276         tree.preOrder(tree.root);
277     }
278 }
279 
280 class Node {
281     int key, height;
282     Node left, right;
283 
284     Node(int d) {
285         key = d;
286         height = 1;
287     }
288 
289 }
View Code
上一篇:SpringBoot2.0 集成thymeleaf


下一篇:用js来实现那些数据结构14(树02-AVL树)