TADM2E 3.14 - Revision history

Matt: Undo revision 1085 by FuckMatt (talk)

2020-08-01T00:51:11Z

Undo revision 1085 by FuckMatt (talk)

FuckMatt: Redirected page to UNTV

2020-07-31T10:13:21Z

Redirected page to UNTV

Algowikiadmin: Recovering wiki

2014-09-11T18:22:39Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:13:21Z

Recovering wiki

New page

In each node of a binary tree store the sub tree sum for the left sub tree.

#''Add'': while descending the tree to the left update the sub tree sum by adding the value
#''Insert'': same as add, only now we have to add a new node too. To guaranty <math>O(n \log n)</math> times we can use any balanced tree types, but the balancing step we have to take care of the sub tree sums. For example in AVL trees balancing operations are tree rotations. If P is the left child of Q, and we are doing a right rotation rooted at Q, than the left sub tree of P remains the same, while the left sub tree of Q will now be the original left sub tree of Q minus the left sub tree of P and P itself. The case of a left rotation is similar. Hence the left sub tree sum values can be maintained in <math>O(1)</math> during rotation operations.
#''Delete'': When the deleted element has at most 1 child, we only need to update the nodes ancestors. If there are two children, we also need to update elements on the path between the deleted element and it's successor. (The element with which we will swap it before deleting.)
#''Partial sum'': With the left sub tree sum values stored in the nodes this operation only involves searching for the element with the specified key, and summing sub tree sums along the way.

← Older revision		Revision as of 00:51, 1 August 2020
Line 1:		Line 1:
−	#~~REDIRECT [[UNTV]]~~	+	In each node of a binary tree store the sub tree sum for the left sub tree.
		+
		+	#''Add'': while descending the tree to the left update the sub tree sum by adding the value
		+	#''Insert'': same as add, only now we have to add a new node too. To guaranty <math>O(n \log n)</math> times we can use any balanced tree types, but the balancing step we have to take care of the sub tree sums. For example in AVL trees balancing operations are tree rotations. If P is the left child of Q, and we are doing a right rotation rooted at Q, than the left sub tree of P remains the same, while the left sub tree of Q will now be the original left sub tree of Q minus the left sub tree of P and P itself. The case of a left rotation is similar. Hence the left sub tree sum values can be maintained in <math>O(1)</math> during rotation operations.
		+	#''Delete'': When the deleted element has at most 1 child, we only need to update the nodes ancestors. If there are two children, we also need to update elements on the path between the deleted element and it's successor. (The element with which we will swap it before deleting.)
		+	#''Partial sum'': With the left sub tree sum values stored in the nodes this operation only involves searching for the element with the specified key, and summing sub tree sums along the way.

← Older revision		Revision as of 10:13, 31 July 2020
Line 1:		Line 1:
−	~~In each node of a binary tree store the sub tree sum for the left sub tree.~~	+	#REDIRECT [[UNTV]]
−
−	#~~''Add'': while descending the tree to the left update the sub tree sum by adding the value~~
−	#''Insert'': same as add, only now we have to add a new node too. To guaranty <math>O(n \log n)</math> times we can use any balanced tree types, but the balancing step we have to take care of the sub tree sums. For example in AVL trees balancing operations are tree rotations. If P is the left child of Q, and we are doing a right rotation rooted at Q, than the left sub tree of P remains the same, while the left sub tree of Q will now be the original left sub tree of Q minus the left sub tree of P and P itself. The case of a left rotation is similar. Hence the left sub tree sum values can be maintained in <math>O(1)</math> during rotation operations.
−	#''Delete'': When the deleted element has at most 1 child, we only need to update the nodes ancestors. If there are two children, we also need to update elements on the path between the deleted element and it's successor. (The element with which we will swap it before deleting.)
−	~~#''Partial sum'': With the left sub tree sum values stored in the nodes this operation only involves searching for the element with the specified key, and summing sub tree sums along the way.~~

@@ Line 2: / Line 2: @@
 #''Add'': while descending the tree to the left update the sub tree sum by adding the value
-#''Insert'': same as add, only now we have to add a new node too. To guaranty  &lt;math&gt;O(n \log n)&lt;/math&gt; times we can use any balanced tree types, but the balancing step we have to take care of the sub tree sums. For example in AVL trees balancing operations are tree rotations. If P is the left child of Q, and we are doing a right rotation rooted at Q, than the left sub tree of P remains the same, while the left sub tree of Q will now be the original left sub tree of Q minus the left sub tree of P and P itself. The case of a left rotation is similar. Hence the left sub tree sum values can be maintained in &lt;math&gt;O(1)&lt;/math&gt; during rotation operations.
+#''Insert'': same as add, only now we have to add a new node too. To guaranty  <math>O(n \log n)</math> times we can use any balanced tree types, but the balancing step we have to take care of the sub tree sums. For example in AVL trees balancing operations are tree rotations. If P is the left child of Q, and we are doing a right rotation rooted at Q, than the left sub tree of P remains the same, while the left sub tree of Q will now be the original left sub tree of Q minus the left sub tree of P and P itself. The case of a left rotation is similar. Hence the left sub tree sum values can be maintained in <math>O(1)</math> during rotation operations.
 #''Delete'': When the deleted element has at most 1 child, we only need to update the nodes ancestors. If there are two children, we also need to update elements on the path between the deleted element and it's successor. (The element with which we will swap it before deleting.)
 #''Partial sum'': With the left sub tree sum values stored in the nodes this operation only involves searching for the element with the specified key, and summing sub tree sums along the way.