Dia 54/2019 - Estruturas de dados em JS: árvores e (árvores BT, BST e AVL)

Desafio #92daysofcode que fiz no final de 2019. Nesse artigo temos o dia 54, mostrando o uso de árvores.

Código

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Node {
constructor(key) {
this.key = key;
this.left = undefined;
this.right = undefined;
}

toString() {
return `${this.key}`;
}
}

const Compare = {
LESS_THAN: -1,
BIGGER_THAN: 1,
EQUALS: 0
};

const defaultCompare = (a, b) => {
if (a === b) {
return Compare.EQUALS;
}
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
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
const BalanceFactor = {
UNBALANCED_RIGHT: 1,
SLIGHTLY_UNBALANCED_RIGHT: 2,
BALANCED: 3,
SLIGHTLY_UNBALANCED_LEFT: 4,
UNBALANCED_LEFT: 5
};

class AVLTree extends BinarySearchTree {
constructor(compareFn = defaultCompare) {
super(compareFn);
this.compareFn = compareFn;
this.root = null;
}

getNodeHeight(node) {
if (node == null) {
return -1;
}
return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
}

rotationLL(node) {
const tmp = node.left;
node.left = tmp.right;
tmp.right = node;
return tmp;
}

rotationRR(node) {
const tmp = node.right;
node.right = tmp.left;
tmp.left = node;
return tmp;
}

rotationLR(node) {
node.left = this.rotationRR(node.left);
return this.rotationLL(node);
}

rotationRL(node) {
node.right = this.rotationLL(node.right);
return this.rotationRR(node);
}

getBalanceFactor(node) {
const heightDifference = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
switch (heightDifference) {
case -2:
return BalanceFactor.UNBALANCED_RIGHT;
case -1:
return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
case 1:
return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
case 2:
return BalanceFactor.UNBALANCED_LEFT;
default:
return BalanceFactor.BALANCED;
}
}

insert(key) {
this.root = this.insertNode(this.root, key);
}

insertNode(node, key) {
if (node == null) {
return new Node(key);
} if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
node.left = this.insertNode(node.left, key);
} else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
node.right = this.insertNode(node.right, key);
} else {
return node;
}

const balanceFactor = this.getBalanceFactor(node);
if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
if (this.compareFn(key, node.left.key) === Compare.LESS_THAN) {
node = this.rotationLL(node);
} else {
return this.rotationLR(node);
}
}
if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
if (this.compareFn(key, node.right.key) === Compare.BIGGER_THAN) {
node = this.rotationRR(node);
} else {
return this.rotationRL(node);
}
}
return node;
}

removeNode(node, key) {
node = super.removeNode(node, key);
if (node == null) {
return node;
}

const balanceFactor = this.getBalanceFactor(node);
if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
if (
this.getBalanceFactor(node.left) === BalanceFactor.BALANCED
|| this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
) {
return this.rotationLL(node);
}

if (this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
return this.rotationLR(node.left);
}
}
if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
if (
this.getBalanceFactor(node.right) === BalanceFactor.BALANCED
|| this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT
) {
return this.rotationRR(node);
}

if (this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
return this.rotationRL(node.right);
}
}
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
class BinarySearchTree {
constructor(compareFn = defaultCompare) {
this.compareFn = compareFn;
this.root = undefined;
}

insert(key) {
if (this.root == null) {
this.root = new Node(key);
} else {
this.insertNode(this.root, key);
}
}

insertNode(node, key) {
if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
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);
}
}

getRoot() {
return this.root;
}

search(key) {
return this.searchNode(this.root, key);
}

searchNode(node, key) {
if (node == null) {
return false;
}
if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
return this.searchNode(node.left, key);
} if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
return this.searchNode(node.right, key);
}
return true;
}

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;
}

remove(key) {
this.root = this.removeNode(this.root, key);
}

removeNode(node, key) {
if (node == null) {
return undefined;
}
if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
node.left = this.removeNode(node.left, key);
return node;
} if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
node.right = this.removeNode(node.right, key);
return node;
}

// 1 - a leaf node
if (node.left == null && node.right == null) {
node = undefined;
return node;
}
// 2 - a node with only 1 child
if (node.left == null) {
node = node.right;
return node;
} if (node.right == null) {
node = node.left;
return node;
}
// 3 - a node with 2 children
const aux = this.minNode(node.right);
node.key = aux.key;
node.right = this.removeNode(node.right, aux.key);
return node;
}
}

Conclusão

A postagem original pode ser vista no meu Instagram e o código está acessível no meu Github.

Relacionados

Ao fechar este aviso ou continuar navegando no site Nerd Calistênico, você aceita o uso de cookies.

Este site usa cookies para assegurar a melhor experiência para os nossos usuários. Consulte nossa política de privacidade.

Uma nova versão está disponível. Clique aqui para atualizar.