Differences

This shows you the differences between two versions of the page.

--- projects:proof:populatedifftree [2023/02/27 18:00] – Owen Mellema
+++ projects:proof:populatedifftree [2023/02/27 19:22] (current) – Owen Mellema
@@ Line 5: / Line 5: @@
 The purpose of this algorithm is to add information to a tree about what will change in another tree. This includes information about creation and deletion of nodes, as well as movement.
-We are given two trees - an **original** tree and a **modified** tree. In the image below, the left tree is original, and the right tree is modified.
+We are given two trees - an **original** tree and a **modified** tree. The original tree will have the new information added. In the image below, the left tree is original, and the right tree is modified.
 {{:projects:proof:origin.png?400|}}
@@ Line 49: / Line 49: @@
 We do this for each pair of matched nodes. On this level, there are no mismatched nodes, but there will be in the next level, under node F.
-==== Checking for new nodes ====
+==== Scanning for, and handling, creation ====
 Next, we check if we need to add new nodes. We start in the modified tree, scanning for any nodes that are unmatched.
@@ Line 69: / Line 69: @@
 {{:projects:proof:creation1e.png?400|}}
-We move to the node that matches this node. This will be the previous node, before C1.
+We move to the node that matches this node, B1. This will be the previous node, before C1.
 {{:projects:proof:creation1f.png?400|}}
+To find the node that comes after, we just scan forward to the next node, which is D1.
+{{:projects:proof:creation1g.png?400|}}
+With that, we have all the information we need to add the new node to the original.
+{{:projects:proof:creation1h.png?400|}}
+There are no more unmatched nodes in the modified tree.
+==== Scanning for, and handling, deletion ====
+Handling deletions is really simple.
+We start at the first node in the original tree, and scan for unmatched nodes.
+{{:projects:proof:deletion1a.png?400|}}
+{{:projects:proof:deletion1b.png?400|}}
+{{:projects:proof:deletion1c.png?400|}}
+{{:projects:proof:deletion1d.png?400|}}
+When we find one, we mark it as deleted.
+{{:projects:proof:deletion1e.png?400|}}
+That's literally it - we don't need to actually delete any nodes, we just need a node telling us that we deleted a node.