Getting the maintainNode to be the leaf-most node, so that the update… · 4db/javascript-algorithms@fe9fd72 · GitHub

4db / javascript-algorithms Public

forked from mgechev/javascript-algorithms

• Notifications You must be signed in to change notification settings
• Fork 0
• Star 1

• Code
• Pull requests
• Actions
• Projects
• Wiki
• Security and quality
• Insights

Additional navigation options

Commit fe9fd72

Browse filesBrowse the repository at this point in the historyBrowse files

lygstate

committed

Getting the maintainNode to be the leaf-most node, so that the updateSize would always be right and

the rotate always working.

1 parent d2f065a commit fe9fd72
Copy full SHA for fe9fd72

1 file changed

+11-15Lines changed: 11 additions & 15 deletions

File tree

Expand file treeCollapse file tree

Open diff view settings

Filter options

• src/data-structures
  • size-balanced-tree.js

Expand file treeCollapse file tree

Open diff view settings

Collapse file

‎src/data-structures/size-balanced-tree.js‎

Copy file name to clipboardExpand all lines: src/data-structures/size-balanced-tree.js

+11-15Lines changed: 11 additions & 15 deletions

Original file line number	Diff line number	Diff line change
@@ -75,17 +75,17 @@
75	75
76	76	function updateChild(node, newChild) {
77	77	let parent = node.parent;
78		- if (parent !== Nil) {
79		- if (parent.right === node) {
80		- parent.right = newChild;
81		- newChild.parent = parent;
82		- } else {
83		- parent.left = newChild;
84		- newChild.parent = parent;
85		- }
86		- return parent;
	78	+ if (parent.right === node) {
	79	+ parent.right = newChild;
	80	+ newChild.parent = parent;
	81	+ } else if (parent.left === node) {
	82	+ parent.left = newChild;
	83	+ newChild.parent = parent;
	84	+ }
	85	+ if (newChild !== Nil) {
	86	+ return newChild;
87	87	}
88		- return newChild;
	88	+ return parent;
89	89	}
90	90
91	91	function LeftRotate(node, childNode) {
@@ -267,12 +267,8 @@
267	267	updateChild(node, node.left)
268	268	LRM.right = node.right
269	269	LRM.right.parent = LRM;
270		- maintainNode = LRM;
	270	+ maintainNode = node.right;
271	271	}
272		- if (maintainNode !== Nil) {
273		- maintainNode.updateSize();
274		- }
275		-
276	272	this._root = maintainSizeBalancedTree(maintainNode);
277	273	return removedNode;
278	274	};

0 commit comments

Comments

0 (0)