前端学习笔记

第七章、树

根节点：树的顶部节点 内部节点：至少有一个子节点的节点 外部节点、叶子节点：没有子节点的节点 子树：子节点和子节点的所有子节点构成的树

二叉树和二叉搜索树

二叉树：所有节点最多只能有两个子节点，找一个左侧一个右侧 二叉搜索树：二叉树的一种，但是只允许左侧节点小于父节点，右侧节点大于父节点

// 节点元素
class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null
  }
}

// 二叉搜索树
class BinarySearchTree {
  constructor() {
    this.root = null
  }

  // 插入键
  insert(key) {
    if (this.root === null) {
      // 根节点为空时
      this.root = new Node(key)
    } else {
      // 根节点不为空时
      this.insertNode(this.root, key)
    }
  }
  insertNode(node, key) {
    // 父节点值 > 新节点值，将新节点存入父节点左侧
    if (node.key > key) {
      if (node.left === null) {
        node.left = new Node(key)
      } else {
        this.insertNode(node.left, key)
      }
    } else {
      // 父节点值 <= 新节点值，将新节点存入父节点右侧
      if (node.right === null) {
        node.right = new Node(key)
      } else {
        this.insertNode(node.right, key)
      }
    }
  }

  // 中序遍历 从最小到最大的顺序访问所有节点
  inOrderTraverse(callback) {
    this.inOrderTraverseNode(this.root, callback)
  }
  inOrderTraverseNode(node, callback) {
    if (node !== null) {
      this.inOrderTraverseNode(node.left, callback)
      callback(node.key)
      this.inOrderTraverseNode(node.right, callback)
    }
  }

  // 先序遍历 先访问节点本身，在访问左节点，最后访问右节点
  preOrderTraverse(callback) {
    this.preOrderTraverseNode(this.root, callback);
  }
  preOrderTraverseNode(node, callback) {
    if (node !== null) {
      callback(node.key)
      this.preOrderTraverseNode(node.left, callback)
      this.preOrderTraverseNode(node.right, callback)
    }
  }

  // 后序遍历 先访问后代节点，在访问节点本身
  postOrderTraverse(callback) {
    this.postOrderTraverseNode(this.root, callback);
  }
  postOrderTraverseNode(node, callback) {
    if (node !== null) {
      this.postOrderTraverseNode(node.left, callback)
      this.postOrderTraverseNode(node.right, callback)
      callback(node.key)
    }
  }

  // 查找树的最小值，最小值位于最左侧
  min() {
    return this.minNode(this.root)
  }
  minNode(node) {
    let current = node
    while (current !== null && current.left !== null) {
      current = current.left
    }
    return current
  }

  // 查找树的最大值，最大值位于最右侧
  max() {
    return this.maxNode(this.root)
  }
  maxNode(node) {
    let current = node
    while (current !== null && current.right !== null) {
      current = current.right
    }
    return current
  }

  // 查找特定值
  search(key) {
    return this.searchNode(this.root, key)
  }
  searchNode(node, key) {
    // 递归未查找到节点，返回false
    if (node === null) {
      return false
    }
    // 当前节点值 < 特定值，则递归查找当前节点右侧
    if (node.key < key) {
      return this.searchNode(node.right, key)
    } else if (node.key > key) {
      // 当前节点值 > 特定值，则递归查找当前节点左侧
      return this.searchNode(node.left, key)
    } else {
      // 当前节点值 = 特定值，则返回当前节点
      return node
    }
  }
  
  // 移除节点
  remove(key) {
    this.root = this.removeNode(this.root, key)
  }
  removeNode(node, key) {
    if (node === null) {
      return false
    }
    // 当前节点值 > 特定值，则递归查找当前节点右侧
    if (node.key > key) {
      node.left = this.removeNode(node.left, key)
      return node
    } else if (node.key < key) {
      // 当前节点值 < 特定值，则递归查找当前节点左侧
      node.right = this.removeNode(node.right, key)
      return node
    } else {
      // 当前节点值 = 特定值，移除节点分3种情况
      // 第一种为要被移除的节点没有子节点时，直接移除子节点
      if (node.left === null && node.right === null) {
        node = null;
        // 返回null 对应的父节点就指向null
        return node
      }
      // 第二种情况为要被移除的节点只有一个左子节点或一个右子节点
      if (node.left === null) {
        node = node.right;
        // 返回修改后的节点 对应的父节点就指向新的节点
        return node
      } else if (node.right === null) {
        node = node.left;
        // 返回修改后的节点 对应的父节点就指向新的节点
        return node
      }
      // 第三种情况为要被移除的节点有两个子节点时
      // 需要先找到要被移除节点的右边子树中的最小值，因为右边子树中的值都是大于要被移除节点的
      // 找到右边子树中最小的值，相当于找到了所有大于要被移除节点的节点中，最接近要被移除节点的节点
      // 找到的这个节点将成为被移除节点的继承者
      const rightMin = this.minNode(node.right)
      node.key = rightMin.key
      // 右侧子树中最小的值替换掉要被移除的节点后，将右侧子树中最小的值移除
      node.right = this.removeNode(node.right, rightMin.key)
      // 返回更新后的节点让父节点引用
      return node
    }
  }
}
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
168
169
170
171

AVL树

二叉搜索树的分支可能会不平衡，某个节点的左右子树高度差可能会非常高，AVL树在添加或删除节点时会保持自平衡，使得任意一个节点的左右子树高度差不超过1。

class AVLNode {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
    this.height = 1;
  }
}

// 继承BST树的基础方法
class AVLTree extends BinarySearchTree {
  constructor() {
    super();
    this.root = null;
  }

  // 查询节点的高度
  getHeight(node) {
    return node === null ? 0 : node.height;
  }

  // 计算平衡因子，及左右子树的高度差
  getBalancefactor(node) {
    return node === null
      ? 0
      : this.getHeight(node.left) - this.getHeight(node.right);
  }

  // 判断树是否平衡
  isBalance(node) {
    if (node === null) {
      return true;
    }
    // 当左右子树高度差大于1时表示不平衡
    if (Math.abs(this.getBalancefactor(node)) > 1) {
      return false;
    }
    // 递归判断子节点是否平衡
    return this.isBalance(node.left) && this.isBalance(node.right);
  }

  // 右旋转树 不平衡的节点位于新插入节点的右侧的右侧时使用
  rotationLL(node) {
    let mid = node.left;
    node.left = mid.right;
    mid.right = node;
    // 旋转完后更新节点的高度
    node.height =
      1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
    mid.height =
      1 + Math.max(this.getHeight(mid.left), this.getHeight(mid.right));
    return mid;
  }

  // 左旋转树 不平衡的节点位于新插入节点的左侧的左侧时使用
  rotationRR(node) {
    let mid = node.right;
    node.right = mid.left;
    mid.left = node;
    // 旋转完后更新节点的高度
    node.height =
      1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
    mid.height =
      1 + Math.max(this.getHeight(mid.left), this.getHeight(mid.right));
    return mid;
  }

  // 插入键
  insert(key) {
    this.root = this.insertNode(this.root, key);
  }
  insertNode(node, key) {
    if (node === null) {
      return new AVLNode(key);
    } else if (node.key > key) {
      // 父节点值 > 新节点值，将新节点存入父节点左侧
      node.left = this.insertNode(node.left, key);
    } else {
      // 父节点值 <= 新节点值，将新节点存入父节点右侧
      node.right = this.insertNode(node.right, key);
    }

    // 添加完加点后计算当前节点的高度值
    node.height =
      1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));

    // 计算完高度后，查询平衡因子，平衡因子的绝对值大于1时，表示树不平衡
    let balancefactor = this.getBalancefactor(node);
    // 当平衡因子大于1 且不平衡的节点的左侧节点平衡因子大于等于0，表示是因为当前节点左侧的左侧新增加了节点导致了不平衡
    if (balancefactor > 1 && this.getBalancefactor(node.left) >= 0) {
      return this.rotationLL(node);
    }

    // 当平衡因子小于-1 且不平衡的节点的又侧节点平衡因子小于等于0，表示是因为当前节点右侧的右侧新增加了节点导致了不平衡
    if (balancefactor < -1 && this.getBalancefactor(node.right) <= 0) {
      return this.rotationRR(node);
    }

    // 当平衡因子大于1 且不平衡的节点的左侧节点平衡因子大于0，表示是因为当前节点左侧的右侧新增加了节点导致了不平衡
    if (balancefactor > 1 && this.getBalancefactor(node.left) < 0) {
      node.left = this.rotationRR(node.left);
      return this.rotationLL(node);
    }

    // 当平衡因子小于-1 且不平衡的节点的右侧节点平衡因子大于0，表示是因为当前节点右侧的左侧新增加了节点导致了不平衡
    if (balancefactor < -1 && this.getBalancefactor(node.right) > 0) {
      node.right = this.rotationLL(node.right);
      return this.rotationRR(node);
    }

    return node;
  }

  // 移除节点
  remove(key) {
    this.root = this.removeNode(this.root, key);
  }
  removeNode(node, key) {
    if (node === null) {
      return null;
    }
    // 与BST树不同，需要临时创建一个参数来储存节点，因为移除节点后需要更新高度和平衡信息
    // 判断也和BST树不同，因为没有直接返回节点，所以需要使用if else if的方式，不然会进入多个if判断
    let newNode;
    // 当前节点值 > 特定值，则递归查找当前节点右侧
    if (node.key > key) {
      node.left = this.removeNode(node.left, key);
      newNode = node;
    } else if (node.key < key) {
      // 当前节点值 < 特定值，则递归查找当前节点左侧
      node.right = this.removeNode(node.right, key);
      newNode = node;
    } else {
      // 当前节点值 = 特定值，移除节点分3种情况
      // 第一种为要被移除的节点没有子节点时，直接移除子节点
      if (node.left === null && node.right === null) {
        node = null;
        // 返回null 对应的父节点就指向null
        newNode = node;
      } else if (node.left === null) {
        // 第二种情况为要被移除的节点只有一个左子节点或一个右子节点
        node = node.right;
        // 返回修改后的节点 对应的父节点就指向新的节点
        newNode = node;
      } else if (node.right === null) {
        node = node.left;
        // 返回修改后的节点 对应的父节点就指向新的节点
        newNode = node;
      } else {
        // 第三种情况为要被移除的节点有两个子节点时
        // 需要先找到要被移除节点的右边子树中的最小值，因为右边子树中的值都是大于要被移除节点的
        // 找到右边子树中最小的值，相当于找到了所有大于要被移除节点的节点中，最接近要被移除节点的节点
        // 找到的这个节点将成为被移除节点的继承者
        const rightMin = this.minNode(node.right);
        node.key = rightMin.key;
        // 右侧子树中最小的值替换掉要被移除的节点后，将右侧子树中最小的值移除
        node.right = this.removeNode(node.right, rightMin.key);
        // 返回更新后的节点让父节点引用
        newNode = node;
      }
    }
    if (newNode === null) {
      return null;
    }
    // 删除完加点后计算当前节点的高度值
    newNode.height =
      1 + Math.max(this.getHeight(newNode.left), this.getHeight(newNode.right));

    // 计算完高度后，查询平衡因子，平衡因子的绝对值大于1时，表示树不平衡
    let balancefactor = this.getBalancefactor(newNode);
    // 当平衡因子大于1 且不平衡的节点的左侧节点平衡因子大于等于0，表示是因为当前节点左侧的左侧新增加了节点导致了不平衡
    if (balancefactor > 1 && this.getBalancefactor(newNode.left) >= 0) {
      return this.rotationLL(newNode);
    }

    // 当平衡因子小于-1 且不平衡的节点的又侧节点平衡因子小于等于0，表示是因为当前节点右侧的右侧新增加了节点导致了不平衡
    if (balancefactor < -1 && this.getBalancefactor(newNode.right) <= 0) {
      return this.rotationRR(newNode);
    }

    // 当平衡因子大于1 且不平衡的节点的左侧节点平衡因子大于0，表示是因为当前节点左侧的右侧新增加了节点导致了不平衡
    // 需要先对其左子树进行左旋转，在对其进行右旋转
    if (balancefactor > 1 && this.getBalancefactor(newNode.left) < 0) {
      newNode.left = this.rotationRR(newNode.left);
      return this.rotationLL(newNode);
    }

    // 当平衡因子小于-1 且不平衡的节点的右侧节点平衡因子大于0，表示是因为当前节点右侧的左侧新增加了节点导致了不平衡
    // 需要先对其右子树进行右旋转，在对其进行左旋转
    if (balancefactor < -1 && this.getBalancefactor(newNode.right) > 0) {
      newNode.right = this.rotationLL(newNode.right);
      return this.rotationRR(newNode);
    }

    return newNode;
  }
}
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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197

红黑树

// 红用true表示，黑用false表示
const RED = true;
const BLACK = false;

// 红黑树节点
class RBNode {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
    // 新节点默认为红节点，因为红黑树保持的是黑节点的绝对平衡，新增节点不能破坏黑节点的平衡，所以新节点默认为红节点
    this.color = RED;
  }
}

// 红黑树
class RBTree extends BinarySearchTree {
  constructor() {
    super();
    this.root = null;
  }
  insert(key) {
    this.root = this.insertNode(this.root, key);
    // 红黑树插入节点后，要保持根节点为黑色
    this.root.color = BLACK;
  }
  insertNode(node, key) {
    if (node === null) {
      return new RBNode(key);
    } else if (node.key > key) {
      // 父节点值 > 新节点值，将新节点存入父节点左侧
      node.left = this.insertNode(node.left, key);
    } else {
      // 父节点值 <= 新节点值，将新节点存入父节点右侧
      node.right = this.insertNode(node.right, key);
    }

    // 维护红黑树的平衡
    // 新增节点后，右节点为红节点，而左节点不为红节点，表示新增的节点在原节点的左侧的右侧，进行左旋转
    if (this.isRed(node.right) && !this.isRed(node.left)) {
      node = this.leftRotate(node);
    }
    // 新增节点后，左节点为红节点，且左节点的左节点也为红节点，表示新增的节点在原节点左侧的左侧，进行又旋转
    if (this.isRed(node.left) && this.isRed(node.left.left)) {
      node = this.rightRotate(node);
    }
    // 新增节点后，左节点和右节点都为红色，表示新增节点在原节点的右侧，进行颜色翻转
    if (this.isRed(node.left) && this.isRed(node.right)) {
      this.flipColor(node);
    }
    return node;
  }

  // 判断节是否为红节点
  isRed(node) {
    return node === null ? BLACK : node.color;
  }

  // 左旋转树 要保持红色节点只会出现在当前节点左侧，如果出现在了右侧，则进行左旋转
  leftRotate(node) {
    let mid = node.right;
    node.right = mid.left;
    mid.left = node;
    // 旋转后改变颜色，新增节点继承原节点的颜色，左旋转导致做倾斜的节点变为红色
    mid.color = node.color;
    node.color = RED;
    return mid;
  }

  // 右旋转树 新增节点后左侧出现了连续的两个红节点的情况，进行右旋转
  rightRotate(node) {
    let mid = node.left;
    node.left = mid.right;
    mid.right = node;
    // 旋转后改变颜色 新节点的父节点继承将被旋转的节点的颜色，被旋转节点改为红色
    // 此时mid节点的左右节点都为红色，将会进行颜色翻转已保证红黑树特性
    mid.color = node.color;
    node.color = RED;
    return mid;
  }

  // 颜色翻转
  flipColor(node) {
    node.color = RED;
    node.left.color = BLACK;
    node.right.color = BLACK;
  }
}
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

几种树的优劣势：

  1. 对于完全随机的数据，二分搜索树更好，因为不需要进行频繁的平衡处理（二分搜索树在数据近乎有序时会造成树的极度不平衡，最坏的情况会退化成链表）
  2. 对于查询较多的情况，AVL树更好，因为AVL树是完全平衡的，查询速度会稳定
  3. 对于添加操作较多的情况，红黑树更好，红黑树牺牲了一定的平衡性，只保持了黑节点的绝对平衡，但简化了添加时的频繁旋转平衡操作
  4. 综合所有（增删查改）统计性能的情况下，红黑树更好