curTain

实现

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
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
class AVLNode {
    constructor( data, left=null, right=null, height=1 ){
        // 存储数据
        this.data = data
        this.left = left
        this.right = right
        this.height = height
    }
}

// 平衡二叉树
// 平衡二叉查找树
class AVL {
    constructor(){
        // 平衡二叉树的根节点
        this.root = null
    }
    // 计算某一个节点的高度
    getHeight( node ){
        return node == null ? 0 : node.height
    }
    // 计算 AVL 树的高度
    getTreeHeight(){
        return this.getHeight( this.root )
    }
    // 计算两个高度中的最大值
    getMaxHeight( h1, h2 ){
        return h1 > h2 ? h1 : h2
    }
    // 打印二叉平衡树--中序遍历
    midMap( node, res=[] ){
        if( !node ) return
        node.left && this.midMap( node.left, res )
        res.push( node.data )
        node.right && this.midMap( node.right, res )
    }
    // toString 方法
    toString(){
        let res = []
        this.midMap( this. root, res )
        console.log("最后的结果：", res )
    }

    // LL 左左旋转
    /**
    * @param node 失衡节点
    * @return 左旋后的根节点
    */
    ll( node ){
        // 定义变量保存失衡节点的左子树
        let nodeLeft = node.left
        // 将失衡节点的左子树的右子树，作为失衡节点的右子树
        node.left = nodeLeft.right
        // 将失衡节点作为调整根节点的右子树
        nodeLeft.right = node
        // 重新计算失衡节点和旋转后根节点的高度
        node.height = this.getMaxHeight(this.getHeight(node.left), this.getHeight(node.right))+1
        nodeLeft.height = this.getMaxHeight(this.getHeight(nodeLeft.left),this.getHeight(nodeLeft.right))+1

        // 返回旋转后的根节点
        return nodeLeft
    }

    rr( node ){
        let nodeRight = node.right
        node.right = nodeRight.left
        nodeRight.left = node
        // 计算高度
        node.height = this.getMaxHeight(this.getHeight(node.left),this.getHeight(node.right))+1
        nodeRight.height = this.getMaxHeight(this.getHeight(nodeRight.left),this.getHeight(nodeRight.right))+1
        return nodeRight
    }

    lr( node ){
        // 先进行 RR
        node.left = this.rr( node.left )
        // 再进行 LL
        let root = this.ll( node )
        return node
    }

    rl( node ){
        // 先 ll
        node.right = this.ll( node.right )
        // 再 rr
        let root = this.rr( node )
        return root
    }
    insert( data ){
        this.root = this.insertNode( this.root, data )
    }
    // 插入元素
    insertNode( node, data ){
        // 空树
        if( !node ){
            return new AVLNode(data)
        } else {
            if( node.data < data ){
                node.right = this.insertNode( node.right, data )
                if( this.getHeight( node.right ) - this.getHeight( node.left ) === 2 ){
                    if( data > node.right.data ){
                        node = this.rr( node )
                    } else {
                        node = this.rl( node )
                    }
                }
            } else if( node.data > data ){
                node.left = this.insertNode( node.left, data )
                if( this.getHeight( node.left ) - this.getHeight( node.right ) === 2 ){
                    if( data > node.left.data ){
                        node = this.lr( node )
                    } else {
                        node = this.ll( node )
                    }
                }
            }
            // 相等不进行操作
            // 计算节点的高度
            node.height = this.getMaxHeight(this.getHeight(node.left),this.getHeight(node.right))+1
            return node
        }
    }
    delete( data ){
        this.root = this.deleteNode( this.root, data )
    }
    deleteNode( node, data ){
        // 递归查找
        if( !node ){
            return null
        } else {
            if( data > node.data ){
                node.right = this.deleteNode( node.right, data )
                // 比较高度，看是否需要调整
                if( this.getHeight( node.right ) - this.getHeight( node.left ) === 2 ){
                    node = this.rr( node )
                }
                if( this.getHeight( node.left ) - this.getHeight( node.right ) === 2 ){
                    node = this.ll( node )
                }
                node.height = this.getMaxHeight(this.getHeight(node.left),this.getHeight(node.right))+1
                // 设置当前节点的高度
                return node
            } else if( data < node.data ){
                node.left = this.deleteNode( node.left, data )
                if( this.getHeight( node.left ) - this.getHeight( node.right ) === 2 ){
                    node = this.ll( node )
                }
                if( this.getHeight( node.right ) - this.getHeight( node.left ) === 2 ){
                    node = this.rr( node )
                }
                node.height = this.getMaxHeight(this.getHeight(node.left),this.getHeight(node.right))+1
                return node
            } else {
                // 等于当前节点，删除当前节点
                // 分四种情况--没有子节点，只有一个子节点，有两个子节点
                // 没有子节点
                if( !node.left && !node.right ){
                    return null
                }
                // 有左子节点
                if( node.left && !node.right ){
                    return node.left
                }
                // 有右子节点
                if( !node.left && node.right ){
                    return node.right
                }
                // 左右子节点都有
                // 判定谁的高度更高
                // 左子树更高
                let resNode
                if( this.getHeight( node.left ) <= this.getHeight( node.right ) ){
                    let minNode = {}
                    node.right = this.delMin( node.right, minNode )
                    // 找到最小节点
                    resNode = minNode.min
                    resNode.left = node.left
                    resNode.right = node.right
                    resNode.height = this.getMaxHeight( this.getHeight( resNode.left ), this.getHeight( resNode.right ) ) + 1
                } else {
                    let maxNode = {}
                    resNode = maxNode.max
                    resNode.right = node.right
                    resNode.left = node.left
                    resNode.height = this.getMaxHeight( this.getHeight( resNode.left ), this.getHeight( resNode.right ) ) + 1
                }
                // 设置当前节点的高度
                return resNode
            }
        }
    }
    delMin( node, res ){
        if( node.left ){
            node.left = this.delMin( node.left, res )
            if(  node.left && !node.left.left ){
                node.left = node.left.right
                res.min = node.left
            }
            if( this.getHeight( node.right ) - this.getHeight( node.left ) === 2 ){
                node = this.rr( node )
            }
            node.height = this.getMaxHeight( this.getHeight( node.left ), this.getHeight( node.right ) ) + 1
            return node
        } else {
            res.min = node
            return null
        }
    }
    delMax( node, res ){
        if( node.right ){
            node.right = this.delMax( node.right, res )
            if( !node.right.right ){
                node.right = node.right.left
                res.max = node.right
            }
            if( this.getHeight( node.right ) - this.getHeight( node.left ) === 2 ){
                node = this.ll( node )
            }
            node.height = this.getMaxHeight( this.getHeight( node.left ), this.getHeight( node.right ) ) + 1
            return node
        } else {
            res.max = node
            return null
        }
    }
}

// 测试

let tree = new AVL()
// tree.insert( 10 )
// tree.insert( 8 )
tree.insert( 3 )
// tree.insert( 12 )
// tree.insert( 9 )
tree.insert( 4 )
tree.insert( 5 )
tree.insert( 7 )
// tree.insert( 1 )
tree.insert( 11 )
tree.insert( 17 )
tree.insert( 19 )
tree.insert( 20 )

// console.log( tree )
tree.delete( 7 )
console.log( tree )
tree.toString()

 评论