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
| function Node(key) {
this.data = key
this.left = null
this.right = null
}
function AVL(arr) {
this.root = null
this.createAVL(arr)
}
AVL.prototype.createAVL = function(arr) {
const len = arr.length
if(len === 0) return null
let root = null
const res = []
for(let i = 0;i < len; i++) {
if(res.indexOf(arr[i]) === -1) {
root = this.insertNode(root, arr[i])
res.push(arr[i])
}
}
this.root = root
}
// RR型左旋
AVL.prototype.rotateL = function(AvlNode) {
var node = AvlNode.right; // 保存右子节点
AvlNode.right = node.left; // node的左子节点连接到AvlNode成为其右子节点
node.left = AvlNode; // AvlNode连接到node成为其左子节点
return node; // 返回node，连接到AvlNode最初的父节点
}
// LL型右旋
AVL.prototype.rotateR = function(AvlNode) {
var node = AvlNode.left;
AvlNode.left = node.right;
node.right = AvlNode;
return node
}
// RL型
AVL.prototype.rotateRL = function(AvlNode) {
AvlNode.right = this.rotateR(AvlNode.right)
return this.rotateL(AvlNode)
}
// LR型
AVL.prototype.rotateLR = function(AvlNode) {
AvlNode.left = this.rotateL(AvlNode.left)
return this.rotateR(AvlNode)
}
// 获取高度
AVL.prototype.getHeight = function(node) {
if(node === null) {
return 0
}
return Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1
}
AVL.prototype.balanceAVL = function(root) {
if(root === null) return root
let lHeight = this.getHeight(root.left)
let rHeight = this.getHeight(root.right)
if(lHeight - rHeight === 2) {
let ll = this.getHeight(root.left.left)
let lr = this.getHeight(root.left.right)
if(ll - lr === 1) {
root = this.rotateR(root) // LL型
} else {
root = this.rotateLR(root)//LR型
}
}
else if(rHeight - lHeight === 2) {
let rl = this.getHeight(root.right.left)
let rr = this.getHeight(root.right.right)
if(rr - rl === 1) { //RR型
root = this.rotateL(root)
} else {
root = this.rotateRL(root)
}
}
return root
}
AVL.prototype.insertNode = function(node, key) {
if(node === null) {
node = new Node(key)
} else {
if(key < node.data) {
node.left = this.insertNode(node.left, key)
node = this.balanceAVL(node)
} else if(key > node.data) {
node.right = this.insertNode(node.right, key)
node = this.balanceAVL(node)
}
}
return node
}
AVL.prototype.deleteNode = function(node, key) { // 返回删除后的值
if(node === null) {
return node
} else {
if(key === node.data) {
if(node.left === null && node.right === null) return null // 直接删除该节点
if(node.left === null && node.right !== null) {
node = node.right
return node
}
else if(node.right === null && node.left !== null) {
node = node.left
return node
} else {
// 左右节点都有的
node.data = node.right.data
node.right = this.deleteNode(node.right, key)
node = this.balanceAVL(node)
}
}
else if(key < node.data) {
// 将后面的值复制上来，然后递归删除
node.left = this.deleteNode(node.left, key)
node = this.balanceAVL(node)
} else {
node.right = this.deleteNode(node.right, key)
node = this.balanceAVL(node)
}
}
return node
}
const AVLobj = new AVL([2,3,9,1])
|