cleanup b+ tree

justcoding121 · justcoding121 · commit 6cbe9e985797 · 2019-03-12T11:25:50.000-04:00
diff --git a/src/Advanced.Algorithms/DataStructures/Tree/B+Tree.cs b/src/Advanced.Algorithms/DataStructures/Tree/B+Tree.cs
@@ -199,30 +199,7 @@ private void insertAndSplit(ref BpTreeNode<T> node, T newValue,
             //connect leaves via linked list for faster enumeration
             if (node.IsLeaf)
             {
-                left.Next = right;
-                right.Prev = left;
-
-                if (node.Next != null)
-                {
-                    right.Next = node.Next;
-                    node.Next.Prev = right;
-                }
-                else
-                {
-                    //bottom right most node
-                    BottomRightNode = right;
-                }
-
-                if (node.Prev != null)
-                {
-                    left.Prev = node.Prev;
-                    node.Prev.Next = left;
-                }
-                else
-                {
-                    //bottom left most node
-                    BottomLeftNode = left;
-                }
+                connectLeaves(node, left, right);
             }
 
             //median of current Node
@@ -396,6 +373,35 @@ private void insertToNotFullNode(ref BpTreeNode<T> node, T newValue,
             setChild(node, node.KeyCount, newValueRight);
         }
 
+
+        private void connectLeaves(BpTreeNode<T> node, BpTreeNode<T> left, BpTreeNode<T> right)
+        {
+            left.Next = right;
+            right.Prev = left;
+
+            if (node.Next != null)
+            {
+                right.Next = node.Next;
+                node.Next.Prev = right;
+            }
+            else
+            {
+                //bottom right most node
+                BottomRightNode = right;
+            }
+
+            if (node.Prev != null)
+            {
+                left.Prev = node.Prev;
+                node.Prev.Next = left;
+            }
+            else
+            {
+                //bottom left most node
+                BottomLeftNode = left;
+            }
+        }
+
         /// <summary>
         /// Time complexity: O(log(n)).
         /// </summary>
@@ -552,25 +558,7 @@ private void sandwich(BpTreeNode<T> leftSibling, BpTreeNode<T> rightSibling, T d
             //if leaves are merged then update the Next and Prev pointers
             if (leftSibling.IsLeaf)
             {
-                if (leftSibling.Prev != null)
-                {
-                    newNode.Prev = leftSibling.Prev;
-                    leftSibling.Prev.Next = newNode;
-                }
-                else
-                {
-                    BottomLeftNode = newNode;
-                }
-
-                if (rightSibling.Next != null)
-                {
-                    newNode.Next = rightSibling.Next;
-                    rightSibling.Next.Prev = newNode;
-                }
-                else
-                {
-                    BottomRightNode = newNode;
-                }
+                mergeLeaves(newNode, leftSibling, rightSibling);
             }
 
             var newIndex = 0;
@@ -754,6 +742,28 @@ private void leftRotate(BpTreeNode<T> leftSibling, BpTreeNode<T> rightSibling)
             }
         }
 
+        private void mergeLeaves(BpTreeNode<T> newNode, BpTreeNode<T> leftSibling, BpTreeNode<T> rightSibling)
+        {
+            if (leftSibling.Prev != null)
+            {
+                newNode.Prev = leftSibling.Prev;
+                leftSibling.Prev.Next = newNode;
+            }
+            else
+            {
+                BottomLeftNode = newNode;
+            }
+
+            if (rightSibling.Next != null)
+            {
+                newNode.Next = rightSibling.Next;
+                rightSibling.Next.Prev = newNode;
+            }
+            else
+            {
+                BottomRightNode = newNode;
+            }
+        }
         /// <summary>
         /// Locate the node in which the item to delete exist
         /// </summary>
diff --git a/tests/Advanced.Algorithms.Tests/DataStructures/Tree/QuadTree_Tests.cs b/tests/Advanced.Algorithms.Tests/DataStructures/Tree/QuadTree_Tests.cs
@@ -7,7 +7,7 @@
 using System.Text;
 using System.Threading.Tasks;
 
-namespace Advanced.Algorithms.Tests.DataStructures.Tree
+namespace Advanced.Algorithms.Tests.DataStructures
 {
     public class QuadTree_Tests
     {
diff --git a/tests/Advanced.Algorithms.Tests/DataStructures/Tree/RTree_Tests.cs b/tests/Advanced.Algorithms.Tests/DataStructures/Tree/RTree_Tests.cs
@@ -5,7 +5,7 @@
 using System.Collections.Generic;
 using System.Linq;
 
-namespace Advanced.Algorithms.Tests.DataStructures.Tree
+namespace Advanced.Algorithms.Tests.DataStructures
 {
     [TestClass]
     public class RTree_Tests

Original file line number	Diff line number	Diff line change
`@@ -7,7 +7,7 @@`
`7`	`7`	`using System.Text;`
`8`	`8`	`using System.Threading.Tasks;`
`9`	`9`
`10`		`-namespace Advanced.Algorithms.Tests.DataStructures.Tree`
	`10`	`+namespace Advanced.Algorithms.Tests.DataStructures`
`11`	`11`	`{`
`12`	`12`	`public class QuadTree_Tests`
`13`	`13`	`{`
Original file line number	Diff line number	Diff line change
`@@ -5,7 +5,7 @@`
`5`	`5`	`using System.Collections.Generic;`
`6`	`6`	`using System.Linq;`
`7`	`7`
`8`		`-namespace Advanced.Algorithms.Tests.DataStructures.Tree`
	`8`	`+namespace Advanced.Algorithms.Tests.DataStructures`
`9`	`9`	`{`
`10`	`10`	`[TestClass]`
`11`	`11`	`public class RTree_Tests`