-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathAVLtree.js
141 lines (132 loc) · 3.85 KB
/
AVLtree.js
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
//AVL TREE
class Tree {
constructor() {
this.root = null;
}
add(value) {
if (!this.root) {
this.root = new Node(value);
} else this.root.add(value);
}
toObject() {
return this.root;
}
}
class Node {
constructor(value) {
this.value = value;
this.height = 1;
this.right = null;
this.left = null;
}
add(value) {
if (value < this.value) {
if (this.left) {
// go left
this.left.add(value);
} else this.left = new Node(value);
this.updateHeightInLocation();
} else {
// go right
if (this.right) this.right.add(value);
else this.right = new Node(value);
this.updateHeightInLocation();
}
this.balance();
}
updateHeightInLocation() {
if (!this.left && !this.right) {
this.height = 1;
} else if (!this.right || this.right.height < this.left.height) {
this.height = this.left.height + 1;
} else if (!this.left || this.left.height < this.right.height) {
this.height = this.right.height + 1;
}
}
balance() {
let leftHeight = this.left?.height || 0;
let rightHeight = this.right?.height || 0;
if (leftHeight > rightHeight + 1) {
let leftLeftHeight = this.left.left?.height; // check if more ? needed
let leftRightHeight = this.left.right?.height;
if (leftRightHeight > leftLeftHeight) {
this.left.rotateRR();
}
this.rotateLL();
} else if (rightHeight > leftHeight + 1) {
let rightRightHeight = this.right.right?.height;
let rightLeftHeight = this.right.left?.height;
if (rightLeftHeight > rightRightHeight) {
this.right.rotateLL();
}
this.rotateRR();
}
}
rotateRR() {
let valueBefore = this.value;
let leftBefore = this.left;
this.value = this.right.value;
this.left = this.right;
this.left.right = this.right.left;
this.right = this.right.right;
this.left.left = leftBefore;
this.left.value = valueBefore;
this.left.updateHeightInLocation();
this.updateHeightInLocation();
}
rotateRR() {
let valueBefore = this.value;
let rightBefore = this.right;
this.value = this.left.value;
this.right = this.left;
this.right.left = this.left.right;
this.left = this.left.left;
this.right.right = rightBefore;
this.right.value = valueBefore;
this.right.updateHeightInLocation();
this.updateHeightInLocation();
}
}
const tree = new Tree();
// Add values to the tree
tree.add(10);
tree.add(5);
tree.add(15);
tree.add(3);
tree.add(8);
// Print the tree structure
console.log(tree.toObject());
// Expected output:
// {
// value: 10,
// left: {
// value: 5,
// left: {
// value: 3,
// left: null,
// right: null,
// height: 1
// },
// right: {
// value: 8,
// left: null,
// right: null,
// height: 1
// },
// height: 2
// },
// right: {
// value: 15,
// left: null,
// right: null,
// height: 1
// },
// height: 3
// }
console.log('----------AVL END-------------');
/**
* updateInNewLocation
* If the node has no left child and no right child (i.e., it is a leaf node), then its height is set to 1. This is because a leaf node is considered to have a height of 1.
If the node has no right child or its left child's height is greater than its right child's height, then its height is set to the height of its left child plus 1. This is because the node's height is determined by the height of its left subtree.
If the node has no left child or its right child's height is greater than its left child's height, then its height is set to the height of its right child plus 1. This is because the node's height is determined by the height of its right subtree.
*/