Блог

Я ищу итеративную вставку без стека (из-за ограничений памяти и минимального рефакторинга) только для вставки в kd-tree.

У меня есть целая библиотека kd-tree, работающая на C, функции (вставка, чтение, обновление, удаление, поиск knn, перебалансировка) Я начал заменять все рекурсивные функции итеративными.

Однако я заметил, что моя вставка не работала для некоторых тестовых данных. На самом деле поиск не смог найти вставленные узлы при использовании итеративной реализации, но все данные были найдены при использовании рекурсивной реализации, следовательно, ошибка находится в версии итеративной вставки.

структура узла:

 typedef struct kd_tree_node
{  
    struct kd_tree_node* left; 
    struct kd_tree_node* right; 
    struct kd_tree_node* parent; 
    float* dataset;  
    float distance_to_neighbor;
} kd_tree_node;
  

Ниже приведена итеративная вставка (я включил части, непосредственно связанные. Нет логики перебалансировки и т.д. …):

 void
kd_tree_add_record(kd_tree_node* root, const float data [], int depth,
        const int k_dimensions,
        const int copying, const float rebuild_threshold) {

   /*rebalancing logic is NOT relevant, which  I have NOT include, we can just build inefficient tree*/
    
    /* is root empty? */
    if (is_empty_node(root, k_dimensions)) {
        root = kd_tree_new_node(data, k_dimensions, copying);
        /*was the root set before*/
        if (is_empty_node(kd_tree_get_root(), k_dimensions)) {
            kd_tree_set_root(root);
        }
    } else {
        /*iteratively insert new node*/
        current = kd_tree_get_root();
        /*while current is NOT null*/
        while (!is_empty_node(current, k_dimensions)) {
            parent = current;
            /* Calculate current dimension (cd) of comparison */
            cd = depth % k_dimensions;
            /*determine current dimension/*/
            /*by using modula operator we can cycle through all dimensions */
            /* and decide the left or right subtree*/
            median = kd_tree_get_column_median(cd);
            //printf("kd_tree_add_record.(), median=%fn",median);
            if (data[cd] < median) {
              current = current->left; 
               
            } else {
                current = current->right;
                
            }
            depth  ;
        }//end while
        
        /*should be inserted left or right of the parent*/
        int insert_left = 1; 
        depth = 0;  
        if (!is_empty_node(parent,k_dimensions)) {
            int c = 0;
            for (; c < k_dimensions; c  ) {
            
            cd = depth % k_dimensions;
            median = kd_tree_get_column_median(cd);
                if (parent->dataset[cd] < median) {
                   
                } else {
                     insert_left = 0;
                     break; 
                   
                }
            depth  ;
            }
            
            if (insert_left)
            {
                 parent->left = kd_tree_new_node(data, k_dimensions, copying);
                 
            }
            else
            {
                 parent->right = kd_tree_new_node(data, k_dimensions, copying);
                 
            }
        }
        
    }//end else

}
  

Я основал свою итеративную вставку в kd-tree на приведенном выше коде, пытаясь следовать итеративному коду вставки двоичного дерева C из: (https://www.techiedelight.com/insertion-in-bst /), который можно протестировать онлайн, смотрите Ниже (обратите внимание, что это не мой код и он предоставлен в качестве ссылки):

 void insertIterative(Node*amp; root, int key)
{
    // start with root node
    Node *curr = root;

    // pointer to store parent node of current node
    Node *parent = nullptr;

    // if tree is empty, create a new node and set root
    if (root == nullptr)
    {
        root = newNode(key);
        return;
    }

    // traverse the tree and find parent node of key
    while (curr != nullptr)
    {
        // update parent node as current node
        parent = curr;

        // if given key is less than the current node, go to left subtree
        // else go to right subtree
        if (key < curr->data)
            curr = curr->left;
        else
            curr = curr->right;
    }

    // construct a new node and assign to appropriate parent pointer
    if (key < parent->data)
        parent->left = newNode(key);
    else
        parent->right = newNode(key);
}
  

Вот моя предыдущая версия рекурсивной вставки в kd-tree, которая работает:

    kd_tree_node *
  kd_tree_add_record(kd_tree_node * root,
    const float data[], int depth,
      const int k_dimensions,
        const int copying,
          const float rebuild_threshold) {
    float median = 0.0;
    /* Tree is empty? */
    if (NULL == root || NULL == root -> dataset || is_empty_node(root, k_dimensions)) {

      root = kd_tree_new_node(data, k_dimensions, copying);

      //update the root globally
      if (kd_tree_get_root() == NULL) {
        kd_tree_set_root(root);
      }

    } else {

      /* Calculate current dimension (cd) of comparison */
      size_t cd = depth % k_dimensions;
      /*determine current dimension/*/
      /*by using modula operator we can cycle through all dimensions */

      /* and decide the left or right subtree*/
      median = kd_tree_get_column_median(cd);

      if (data[cd] < median) {

        root -> left = kd_tree_add_record(root -> left, data, depth   1,
          k_dimensions,
          copying, rebuild_threshold);
      } else {

        root -> right = kd_tree_add_record(root -> right, data, depth   1,
          k_dimensions,
          copying, rebuild_threshold);
      }
    } //end else
    return root;

  } 
  

текущие результаты тестирования:

 -53.148998,0.000000,9.000000 Found
 7.999700,0.069812,8.000000 Found
 7.998780,0.139619,8.000000 Found
 7.997260,0.209416,8.000000 Not Found!
7.995130,0.279196,8.000000 Not Found!
 7.992390,0.348955,8.000000 Not Found!
8.987670,0.471024,9.000000 Found
8.983210,0.549437,9.000000 Found
 7.980510,0.558052,8.000000 Not Found!
 3.000000,3.000000,3.000000 Found
4.000000,4.000000,4.000000 Found
5.000000,5.000000,5.000000 Found!
100.000000,100.000000,100.000000 Found
  

Как я могу распространить итеративный алгоритм вставки двоичных файлов без стека на kd-деревья?

Действительно ценится!