Skip to content

Commit 9dc1771

Browse files
amejiarosarioamejiarosario
committed
better docs
1 parent 6422e22 commit 9dc1771

4 files changed

Lines changed: 82 additions & 43 deletions

File tree

‎src/data-structures/trees/avl-tree.js‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
const BinarySearchTree = require('./binary-search-tree');
22
const {
3-
balanceUp,
3+
balanceUptream,
44
} = require('./tree-rotations');
55

66
class AvlTree extends BinarySearchTree {
@@ -11,7 +11,7 @@ class AvlTree extends BinarySearchTree {
1111
*/
1212
add(value) {
1313
const node = super.add(value);
14-
balanceUp(node);
14+
balanceUptream(node);
1515
return node;
1616
}
1717

@@ -23,7 +23,7 @@ class AvlTree extends BinarySearchTree {
2323
const node = super.find(value);
2424
if (node) {
2525
const found = super.remove(value);
26-
balanceUp(node.parent);
26+
balanceUptream(node.parent);
2727
return found;
2828
}
2929

‎src/data-structures/trees/tree-node.js‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -123,22 +123,22 @@ class TreeNode {
123123
* Height: distance from the deepest leaf to this node
124124
*/
125125
get height() {
126-
return Math.max(this.leftHeight, this.rightHeight);
126+
return Math.max(this.leftSubtreeHeight, this.rightSubtreeHeight);
127127
}
128128

129-
get leftHeight() {
129+
get leftSubtreeHeight() {
130130
return this.left ? this.left.height + 1 : 0;
131131
}
132132

133-
get rightHeight() {
133+
get rightSubtreeHeight() {
134134
return this.right ? this.right.height + 1 : 0;
135135
}
136136

137137
/**
138138
* Returns the difference the heights on the left and right subtrees
139139
*/
140140
get balanceFactor() {
141-
return this.leftHeight - this.rightHeight;
141+
return this.leftSubtreeHeight - this.rightSubtreeHeight;
142142
}
143143

144144
/**

‎src/data-structures/trees/tree-rotations.js‎

Lines changed: 54 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22
* Swap parent's child
33
*
44
*
5-
* @example Child on the left side
5+
* @example Child on the left side (it also work for the right side)
66
*
77
* p = parent
88
* o = old child
@@ -29,12 +29,24 @@ function swapParentChild(oldChild, newChild, parent) {
2929

3030
/**
3131
* Single Left Rotation (LL Rotation)
32+
*
33+
* @example: tree with values 1-2-3-4
34+
*
35+
* 1 1
36+
* \ \
37+
* 2* 3
38+
* \ --left-rotation(2)-> / \
39+
* 3 2* 4
40+
* \
41+
* 4
3242
* @param {TreeNode} node
43+
* @returns {TreeNode} new parent after the rotation
3344
*/
3445
function leftRotation(node) {
3546
const newParent = node.right;
3647
const grandparent = node.parent;
3748

49+
3850
swapParentChild(node, newParent, grandparent);
3951

4052
// do LL rotation
@@ -46,7 +58,19 @@ function leftRotation(node) {
4658

4759
/**
4860
* Single Right Rotation (RR Rotation)
61+
*
62+
* @example rotate node 3 to the right
63+
*
64+
* 4 4
65+
* / /
66+
* 3* 2
67+
* / / \
68+
* 2 ---| right-rotation(3) |--> 1 3*
69+
* /
70+
* 1
71+
*
4972
* @param {TreeNode} node
73+
* @returns {TreeNode} new parent after the rotation
5074
*/
5175
function rightRotation(node) {
5276
const newParent = node.left;
@@ -63,24 +87,41 @@ function rightRotation(node) {
6387

6488
/**
6589
* Left Right Rotation (LR Rotation)
90+
*
91+
* @example LR rotation on node 3
92+
* 4 4
93+
* / / 4
94+
* 3 3* /
95+
* / / 2
96+
* 1* --left-rotation(1)-> 2 --right-rotation(3)-> / \
97+
* \ / 1 3*
98+
* 2 1
99+
*
66100
* @param {TreeNode} node
101+
* @returns {TreeNode} new parent after the rotation
67102
*/
68103
function leftRightRotation(node) {
69-
let newParent;
70-
newParent = leftRotation(node.left);
71-
newParent = rightRotation(node);
72-
return newParent;
104+
leftRotation(node.left);
105+
return rightRotation(node);
73106
}
74107

75108
/**
76109
* Right Left Rotation (RL Rotation)
110+
*
111+
* @example RL rotation on 1
112+
*
113+
* 1* 1*
114+
* \ \ 2
115+
* 3 -right-rotation(3)-> 2 -left-rotation(1)-> / \
116+
* / \ 1* 3
117+
* 2 3
118+
*
77119
* @param {TreeNode} node
120+
* @returns {TreeNode} new parent after the rotation
78121
*/
79122
function rightLeftRotation(node) {
80-
let newParent;
81-
newParent = rightRotation(node.right);
82-
newParent = leftRotation(node);
83-
return newParent;
123+
rightRotation(node.right);
124+
return leftRotation(node);
84125
}
85126

86127
/**
@@ -97,14 +138,14 @@ function rightLeftRotation(node) {
97138
*/
98139
function balance(node) {
99140
if (node.balanceFactor > 1) {
100-
// left subtree is heighter than right subtree
141+
// left subtree is higher than right subtree
101142
if (node.left.balanceFactor > 0) {
102143
rightRotation(node);
103144
} else if (node.left.balanceFactor < 0) {
104145
leftRightRotation(node);
105146
}
106147
} else if (node.balanceFactor < -1) {
107-
// right subtree is heighter than left subtree
148+
// right subtree is higher than left subtree
108149
if (node.right.balanceFactor < 0) {
109150
leftRotation(node);
110151
} else if (node.right.balanceFactor > 0) {
@@ -118,7 +159,7 @@ function balance(node) {
118159
*
119160
* @param {TreeNode} node
120161
*/
121-
function balanceUp(node) {
162+
function balanceUptream(node) {
122163
let current = node;
123164
while (current) {
124165
balance(current);
@@ -132,5 +173,5 @@ module.exports = {
132173
leftRightRotation,
133174
rightLeftRotation,
134175
balance,
135-
balanceUp,
176+
balanceUptream,
136177
};

‎src/data-structures/trees/tree-rotations.spec.js‎

Lines changed: 21 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -20,36 +20,34 @@ describe('Tree rotations', () => {
2020
});
2121

2222
describe('#leftRotation (LL Rotation)', () => {
23-
it('should rotate left with root (LL Rotation)', () => {
24-
// 1
25-
// \
26-
// 2*
27-
// \
28-
// 3
29-
// \
30-
// 4
23+
it('basic LL rotation', () => {
24+
/*
25+
* 1* 2*
26+
* \ / \
27+
* 2 ---| left-rotation(1) |--> 1 3
28+
* \
29+
* 3
30+
*/
3131
n1.right = n2;
3232
n2.right = n3;
33-
n3.right = n4;
3433

35-
const newParent = leftRotation(n2);
36-
37-
expect(newParent).toBe(n3);
34+
const newParent = leftRotation(n1);
35+
expect(newParent.value).toBe(2);
3836
expect(n1.toValues()).toMatchObject({
39-
value: 1, left: undefined, right: 3, parent: null,
37+
value: 1, left: undefined, right: undefined, parent: 2,
4038
});
4139
expect(n2.toValues()).toMatchObject({
42-
value: 2, left: undefined, right: undefined, parent: 3,
40+
value: 2, left: 1, right: 3, parent: null,
4341
});
4442
expect(n3.toValues()).toMatchObject({
45-
value: 3, left: 2, right: 4, parent: 1,
43+
value: 3, left: undefined, right: undefined, parent: 2,
4644
});
4745
});
4846

49-
it('should rotate left with root', () => {
50-
// 1*
47+
it('should rotate left with root (LL Rotation)', () => {
48+
// 1
5149
// \
52-
// 2
50+
// 2*
5351
// \
5452
// 3
5553
// \
@@ -58,17 +56,17 @@ describe('Tree rotations', () => {
5856
n2.right = n3;
5957
n3.right = n4;
6058

61-
const newParent = leftRotation(n1);
59+
const newParent = leftRotation(n2);
6260

63-
expect(newParent).toBe(n2);
61+
expect(newParent).toBe(n3);
6462
expect(n1.toValues()).toMatchObject({
65-
value: 1, left: undefined, right: undefined, parent: 2,
63+
value: 1, left: undefined, right: 3, parent: null,
6664
});
6765
expect(n2.toValues()).toMatchObject({
68-
value: 2, left: 1, right: 3, parent: null,
66+
value: 2, left: undefined, right: undefined, parent: 3,
6967
});
7068
expect(n3.toValues()).toMatchObject({
71-
value: 3, left: undefined, right: 4, parent: 2,
69+
value: 3, left: 2, right: 4, parent: 1,
7270
});
7371
});
7472

0 commit comments

Comments
 (0)