Число узлов в сбалансированном дереве

Question

Итак, я столкнулся с интересной проблемой и увидел, был ли эффективный способ решить проблему. Таким образом, в основном существует сбалансированное двоичное дерево, в котором хранятся номера идентификаторов (это не bst, поэтому нет формальной компоновки). У вас есть ограниченное количество запросов, чтобы узнать, сколько узлов есть. Гарантируется, что для каждого узла E левое поддерево будет иметь столько или еще один узел, чем правое поддерево в этом узле E. Какой оптимальный способ попросить программу узнать, сколько узлов есть? Например дано дерево, как это:

  1 
     4  2 
    3 

Программа даст следующий вывод:

Query: 1 
Response: 4 2 
Query: 4 
Response 3 
Query: 3 
Response: 0 0 
Query: 2 
Response: 0 0 
Answer: 4 

Answer 1

int countnodes(ele,count) 
{ 
if(ele.right != null) 
    { 
     count += countnodes(ele.right,0); 
    } 
    if(ele.left != null) 
    { 
    count += countnodes(ele.left,0); 
    } 
    return count++; //got to count this node 
} 

Answer 2

я, наконец, озадачило его.

Из условия

Это гарантируется, что для каждого узла Е, что левое поддерево будет иметь столько же или еще один узел, чем правое поддерево в этом узле E.

следует что

1. Количество нелистовых узлов можно рассчитать по глубине дерева; это 2 ^{глубина - 1}. Поэтому интересно подсчитывать листовые узлы.
2. Учитывая условие балансировки, всегда есть только одно место, где можно вставить новый узел или удалить существующий. (Это означает, что заданное число листовых узлов подразумевает один и только один шаблон листовых узлов.)
3. Если нам известно количество листовых узлов левого поддерева узла, мы знаем, что количество листовых узлов (и количество узлов) в правом поддереве либо то же, либо меньше, чем это.
4. Из 2. и 3. следует, что в правом поддереве имеется только один слот листового узла, о котором мы не можем знать, не проверяя дерево, заполняется ли оно. Обнаружение этого - трюк в этом алгоритме.

Итак, что делает использование 3: Предположим, что мы имеем (суб) дерево T. Мы знаем число конечных узлов в левом поддереве равно п _влево. Поэтому мы знаем, что число листовых узлов в его правом поддереве равно либо n _{осталось}, либо n _{осталось} - 1, и в частности, что оно не более n _{осталось}.

Мы делаем шаг в правом поддереве. Зная максимальное число конечных узлов в этом поддереве, и зная, что они равномерно распределены между поддеревьев с обеих сторон, мы можем заключить две вещи:

• Если максимальное число конечных узлов в этом поддереве нечетно, то сомнительный слот находится слева, так как правая сторона не может быть тяжелее левой. Если он четный, то слот находится справа.
• Максимальное количество листовых узлов в каждом подпункте равно половине, чем у листовых узлов в поддереве, округленное слева, округленное справа.

Это решает суть дела; остальное - простая рекурсия. В C++:

#include <cstddef> 

// I'm using a simple node structure, you'd use query functions. The 
// algorithm is not meaningfully altered by this. 
struct node { 
    node *left = nullptr, *right = nullptr; 
}; 

struct node_counter { 
    std::size_t leaf;  // number of leaf nodes, 
    std::size_t trunk;  // number of trunk nodes, 
    std::size_t depth;  // and depth of the inspected subtree. 
}; 

// Interesting function #1: Given a right subtree and the leaf-count and 
// depth of its left sibling, find the node that might or might not be there 
node const *find_leaf(node const *branch, std::size_t leaf_count, std::size_t depth) { 
    // We've gone down, found the slot. Return it. 
    if(depth == 0) { return branch; } 

    // The heart of the matter: Step into the subtree that contains the 
    // questionable slot, with its maximum leaf node count and depth. 
    return find_leaf(leaf_count % 2 ? branch->left : branch->right, 
        (leaf_count + 1)/2, // int division 
        depth - 1); 
} 

// Recursive counter. This steps down on the left side, then infers the 
// number of leaf and trunk nodes on the right side for each level. 
node_counter count_nodes_aux(node const *root) { 
    // leftmost leaf node is reached. Return info for it. 
    if(!root->left) { 
    return { 1, 0, 0 }; 
    } 

    // We're in the middle of the tree. Get the counts for the left side, 
    auto ctr_left = count_nodes_aux(root->left); 

    // then find the questionable slot on the right 
    auto leaf_right = find_leaf(root->right, ctr_left.leaf, ctr_left.depth); 

    return { 
    // the number of leaf nodes in this tree is double that of the left 
    // subtree if the node is there, one less otherwise. 
    ctr_left.leaf * 2 - (leaf_right ? 0 : 1), 

    // And this is just an easy way to keep count of the number of non-leaf 
    // nodes and the depth of the inspected subtree. 
    ctr_left.trunk * 2 + 1, 
    ctr_left.depth + 1 
    }; 
} 

// Frontend function to make the whole thing easily usable. 
std::size_t count_nodes(node const *root) { 
    auto ctr = count_nodes_aux(root); 
    return ctr.leaf + ctr.trunk; 
} 

Чтобы попробовать это, я использовал следующие, чрезвычайно некрасиво main функция, которая просто строит дерево с большим количеством узлов, вставляет новые в нужных местах и ​​проверки, если счетчик ходов в правом путь. Это не очень, не соответствует лучшим практикам, и если вы пишете такой код в процессе производства, вам следует уволить. Так оно и есть, потому что основным моментом этого ответа является алгоритм, описанный выше, и я не видел смысла в этом.

void fill_node(node *n) { 
    n->left = new node; 
    n->right = new node; 
} 

int main() { 
    node *root = new node; 

    fill_node(root); 

    fill_node(root->left); 
    fill_node(root->right); 

    fill_node(root->left->left); 
    fill_node(root->left->right); 
    fill_node(root->right->left); 
    fill_node(root->right->right); 

    fill_node(root->left->left->left); 
    fill_node(root->left->left->right); 
    fill_node(root->left->right->left); 
    fill_node(root->left->right->right); 
    fill_node(root->right->left->left); 
    fill_node(root->right->left->right); 
    fill_node(root->right->right->left); 
    fill_node(root->right->right->right); 

    std::cout << count_nodes(root) << std::endl; 

    root->left ->left ->left ->left ->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->left ->left ->left ->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->right->left ->left ->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->right->left ->left ->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->left ->right->left ->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->left ->right->left ->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->right->right->left ->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->right->right->left ->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->left ->left ->right->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->left ->left ->right->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->right->left ->right->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->right->left ->right->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->left ->right->right->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->left ->right->right->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->right->right->right->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->right->right->right->left = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->left ->left ->left ->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->left ->left ->left ->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->right->left ->left ->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->right->left ->left ->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->left ->right->left ->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->left ->right->left ->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->right->right->left ->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->right->right->left ->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->left ->left ->right->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->left ->left ->right->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->right->left ->right->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->right->left ->right->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->left ->right->right->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->left ->right->right->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->left ->right->right->right->right = new node; std::cout << count_nodes(root) << std::endl; 
    root->right->right->right->right->right = new node; std::cout << count_nodes(root) << std::endl; 
}