Как найти k-й лист в дереве avl - PullRequest
Новая
       9

Как найти k-й лист в дереве avl

0 голосов
/ 23 марта 2020

Я хочу решить эту проблему, добавив поле листа к моему узлу дерева avl для представления листьев под узлом, поле листа скажет, сколько листьев находится под каждым узлом (n-> leaves = n-> left-> leaves + n -> вправо-> листья) и изменить во время вставки и удаления. Благодаря этому я могу двигаться быстрее, например, если я ищу 100-й лист, а у левого поддерева 90 листов, я могу напрямую перейти к правому поддереву, меняя сложность по времени до O (logn), а не O (n) 

typedef struct tr_n_t { 
//int leaf
    key_t key;
    struct tr_n_t *left;
    struct tr_n_t *right;
    int height; 
} tree_node_t;

1 Ответ

0 голосов
/ 23 марта 2020

Узел является листом, если у него нет дочерних узлов. В случае OP, если (и только если) оба члена узла left и right равны NULL, тогда узел является конечным узлом.

Поскольку тип OP tree_node_t не имеет Указатель на родительский узел, рекурсивная функция может использоваться для выполнения упорядоченного обхода. Упорядоченный обход используется для поиска k -го листового узла. Счетчик может использоваться для отслеживания того, сколько конечных узлов было найдено до сих пор. Когда этот счетчик достигает желаемого значения k, нужный листовой узел найден, поэтому функция может вернуть указатель на нужный узел, в противном случае он должен вернуть 0. 

// recursive helper function
static tree_node_t *find_leaf_k_internal(tree_node_t *node, unsigned int *count, unsigned int k)
{
    tree_node_t *kth;

    if (!node)
        return NULL; // not a node

    if (!node->left && !node->right) {
        // node is a leaf
        if (*count == k)
            return node; // node is the kth leaf

        (*count)++; // increment leaf counter
        return NULL; // not the kth leaf
    }

    // node is not a leaf
    // perform in-order traversal down the left sub-tree
    kth = find_leaf_k_internal(node->left, count, k);
    if (kth)
        return kth; // return found kth leaf node
    // kth leaf node not found yet
    // perform in-order traversal down the right sub-tree
    return find_leaf_k_internal(node->right, count, k);
}

// find kth in-order leaf node of tree counting from 0.
// returns pointer to kth leaf node, or NULL if tree contains fewer than k+1 leaf nodes.
tree_node_t *find_leaf_k(tree_node_t *root, unsigned int k)
{
    unsigned int count = 0; // in-order running count of leaf nodes

    return find_leaf_k_internal(root, &count, k);
}
...