Difference between pages "3.27" and "3.29"

From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation Jump to search
(Created page with "Let's put into the black box whole set <math>S=\{x_i\}_{i=1}^n</math>. If <math>bb(S)</math> is True, then such a subset exists and we can go on: # R:=S # for i:=1 to n do ##...")
 
(Created page with "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 #''Ins...")
 
Line 1: Line 1:
Let's put into the black box whole set <math>S=\{x_i\}_{i=1}^n</math>. If <math>bb(S)</math> is True, then such a subset exists and we can go on:
+
In each node of a binary tree store the sub tree sum for the left sub tree.
# R:=S
 
# for i:=1 to n do
 
## If <math>bb(R/\{x_i\})</math> is True then <math>R:=R/\{x_i\}</math>
 
When this iteration is finished R will be subset of S that adds up to k.
 
  
Above solution works even when there are multiple subsets that add up to k.
+
#''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.
  
  
 
Back to [[Chapter 3]]
 
Back to [[Chapter 3]]

Latest revision as of 18:08, 20 September 2020

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

  1. Add: while descending the tree to the left update the sub tree sum by adding the value
  2. Insert: same as add, only now we have to add a new node too. To guaranty [math]\displaystyle{ 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]\displaystyle{ O(1) }[/math] during rotation operations.
  3. 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.)
  4. 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.


Back to Chapter 3