Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit02299b7

Browse files
committed
Add uncle property to binary tree node.
1 parente6de25e commit02299b7

File tree

2 files changed

+83
-1
lines changed

2 files changed

+83
-1
lines changed

‎src/data-structures/tree/BinaryTreeNode.js

Lines changed: 33 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
11
importComparatorfrom'../../utils/comparator/Comparator';
2+
importHashTablefrom'../hash-table/HashTable';
23

34
exportdefaultclassBinaryTreeNode{
45
/**
@@ -11,7 +12,7 @@ export default class BinaryTreeNode {
1112
this.value=value;
1213

1314
// Any node related meta information may be stored here.
14-
this.meta=newMap();
15+
this.meta=newHashTable();
1516

1617
// This comparator is used to compare binary tree nodes with each other.
1718
this.nodeComparator=newComparator();
@@ -53,6 +54,37 @@ export default class BinaryTreeNode {
5354
returnthis.leftHeight-this.rightHeight;
5455
}
5556

57+
/**
58+
* Get parent's sibling if it exists.
59+
*@return {BinaryTreeNode}
60+
*/
61+
getuncle(){
62+
// Check if current node has parent.
63+
if(!this.parent){
64+
returnundefined;
65+
}
66+
67+
// Check if current node has grand-parent.
68+
if(!this.parent.parent){
69+
returnundefined;
70+
}
71+
72+
// Check if grand-parent has more than two children.
73+
if(!this.parent.parent.left||!this.parent.parent.right){
74+
returnundefined;
75+
}
76+
77+
// So for now we know that current node has grand-parent and this
78+
// grand-parent has two children. Let's find out who is the uncle.
79+
if(this.nodeComparator.equal(this.parent,this.parent.parent.left)){
80+
// Right one is an uncle.
81+
returnthis.parent.parent.right;
82+
}
83+
84+
// Left one is an uncle.
85+
returnthis.parent.parent.left;
86+
}
87+
5688
/**
5789
*@param {BinaryTreeNode} node
5890
*@return {BinaryTreeNode}

‎src/data-structures/tree/__test__/BinaryTreeNode.test.js

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -207,4 +207,54 @@ describe('BinaryTreeNode', () => {
207207
expect(redNode.meta.get('color')).toBe('red');
208208
expect(blackNode.meta.get('color')).toBe('black');
209209
});
210+
211+
it('should detect right uncle',()=>{
212+
constgrandParent=newBinaryTreeNode('grand-parent');
213+
constparent=newBinaryTreeNode('parent');
214+
constuncle=newBinaryTreeNode('uncle');
215+
constchild=newBinaryTreeNode('child');
216+
217+
expect(grandParent.uncle).not.toBeDefined();
218+
expect(parent.uncle).not.toBeDefined();
219+
220+
grandParent.setLeft(parent);
221+
222+
expect(parent.uncle).not.toBeDefined();
223+
expect(child.uncle).not.toBeDefined();
224+
225+
parent.setLeft(child);
226+
227+
expect(child.uncle).not.toBeDefined();
228+
229+
grandParent.setRight(uncle);
230+
231+
expect(parent.uncle).not.toBeDefined();
232+
expect(child.uncle).toBeDefined();
233+
expect(child.uncle).toEqual(uncle);
234+
});
235+
236+
it('should detect left uncle',()=>{
237+
constgrandParent=newBinaryTreeNode('grand-parent');
238+
constparent=newBinaryTreeNode('parent');
239+
constuncle=newBinaryTreeNode('uncle');
240+
constchild=newBinaryTreeNode('child');
241+
242+
expect(grandParent.uncle).not.toBeDefined();
243+
expect(parent.uncle).not.toBeDefined();
244+
245+
grandParent.setRight(parent);
246+
247+
expect(parent.uncle).not.toBeDefined();
248+
expect(child.uncle).not.toBeDefined();
249+
250+
parent.setRight(child);
251+
252+
expect(child.uncle).not.toBeDefined();
253+
254+
grandParent.setLeft(uncle);
255+
256+
expect(parent.uncle).not.toBeDefined();
257+
expect(child.uncle).toBeDefined();
258+
expect(child.uncle).toEqual(uncle);
259+
});
210260
});

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp