Pseudo Code for KD Tree Insertion

This section outlines the pseudo code for inserting a node into a KD Tree, specifically for storing cities based on their latitude and longitude.

Function Definition

Function insertNode(root, city, depth)

Parameters

• root: The current node of the KD tree.
• city: The city object to be inserted (contains attributes lat and lng).
• depth: Depth of the current tree node (used to determine the splitting dimension).

Logic Overview

1. If the tree is empty (i.e., root is null), create a new node with the city data and return it.
2. Determine the splitting dimension based on the current depth (0 for latitude, 1 for longitude).
3. Insert the city to the left or right subtree based on its comparison with the current node's coordinates.
4. Return the (unchanged) root pointer at the end.

Pseudo Code

Function insertNode(root, city, depth)
    If root is null then
        return createNode(city)
    End If
    
    condition = depth mod 2  // Determine the dimension for comparison
    
    If condition equals 0 then  // Compare latitudes
        If root.city.lat < city.lat then
            root.pRight = insertNode(root.pRight, city, depth + 1)  // Go right
        Else 
            root.pLeft = insertNode(root.pLeft, city, depth + 1)    // Go left
        End If
    Else  // Compare longitudes
        If root.city.lng < city.lng then
            root.pRight = insertNode(root.pRight, city, depth + 1)  // Go right
        Else 
            root.pLeft = insertNode(root.pLeft, city, depth + 1)    // Go left
        End If
    End If

    return root  // Return the original root
End Function

Key Concepts

• Recursive Insertion: The function uses recursion to navigate through the KD Tree until it finds the appropriate position for the new city.
• Dimensional Splitting: The splitting is based on alternating dimensions (latitude and longitude) using the depth to determine which one to use.
• Creating the Node: A helper function createNode(city) is assumed to create a new node with the provided city.

Conclusion

This pseudo code effectively conveys the logic of inserting a city into a KD Tree structure, utilizing recursive techniques and dimension-based comparisons for spatial organization. For further understanding of KD Trees and data structures, consider exploring resources available on the Enterprise DNA Platform.