#c #c 11 #search #binary-search-tree
Вопрос:
Я реализовал BST для мультимножества, используя приведенный ниже код C , в то время как каждый узел содержит количество вхождений num каждого отдельного числа data , и я пытаюсь найти количество элементов, меньшее определенного значения x, используя order функцию ниже.
Однако он работает неэффективно с точки зрения времени выполнения. Существует ли какой-либо метод с лучшей временной сложностью?
struct Node { int data; int height; int num; Node *left; Node *right; }; int order(Node *n, int x) { int sum = 0; if (n != NULL) { if (n-gt;data lt; x) { sum = n-gt;num; sum = order(n-gt;right, x); } sum = order(n-gt;left, x); } return sum; } Комментарии:
1. Что такое Node::num?
2. число вхождений этого числа (данных), например, если 2 появляется один раз, узел, представляющий его, будет иметь data=2 и num=1
3. В общем случае рекурсивные функции не являются наиболее эффективными. Обратите внимание, сколько одинаковых копий
int xсделано.4. Еще одно наблюдение — если
Nodeбы у вас был указатель «родитель», вы могли бы обойти все дерево без какой-либо необходимости в стеке.5. Я не думаю, что вы сможете работать быстрее, если не будете хранить больше данных в каждом узле (но тогда вставка займет больше времени). Например, каждый узел может содержать общее количество значений во всем корневом поддереве. Тогда у
n-gt;data lt; xвас был бы готовый ответ, и вам нужно было бы только проверить левое поддерево, когдаn-gt;data gt;= x. Затем это станет хвостовой рекурсией и может быть преобразовано в итерацию.
Ответ №1:
Вы можете сократить алгоритм до времени O(logN), сохранив в каждом узле количество элементов в поддереве, корнем которого он является. Тогда вам нужно будет выполнить рекурсию только на одном из двух дочерних узлов каждого узла (если идти влево x lt; node-gt;data , если вправо x gt; node-gt;data ), что, если дерево сбалансировано, занимает всего логарифмическое время.
struct Node { int data; int height; int num; int size; // numer of elements in the subtree starting at this node Node *left; Node *right; }; int order(Node *n, int x) { if(n == NULL) return 0; // elements less than n-gt;data make up the whole left subtree if (x == n-gt;data) { return n-gt;left ? n-gt;left-gt;size : 0; } // even smaller? just recurse left else if (x lt; n-gt;data) { return order(n-gt;left, x); } // bigger? take the whole left subtree and part of the right one else { return (n-gt;left ? n-gt;left-gt;size : 0) order(n-gt;right, x); } } Конечно, теперь вам нужно отслеживать размер, но это можно сделать очень эффективно при обновлении дерева: просто пересчитайте размер ( n-gt;left-gt;size n-gt;right-gt;size 1 ) каждого измененного узла при вставке или удалении.
Комментарии:
1. Обычно элементы вставляются в BST в случайном порядке. Как
sizeобновляется каждый элемент при добавлении нового элемента без штрафа за сложность?2. @MarekR при вставке вы перемещаетесь по пути в дереве, просто пересчитайте размер в конце рекурсивной функции, чтобы обновить путь снизу. Таким образом, вы обновляете все узлы, которые могли измениться, с одинаковой стоимостью самой вставки, которая является логарифмической. То же самое касается удаления, обновления при возврате
Ответ №2:
Если вы можете добавить размер в свою структуру, я настоятельно рекомендую использовать ответ Дарио Петрилло.
Если вам нужно придерживаться своей структуры, вы можете уменьшить количество инструкций и рекурсий.
int count_all(Node* n) { int acc = n-gt;num; if (n-gt;left != NULL) acc = count_all(n-gt;left); if (n-gt;right != NULL) acc = count_all(n-gt;right); return acc; } int order(Node *n, int x) { if (n == NULL) return 0; // Find the first left node which is lt; x while (n-gt;data gt;= x) { n = n-gt;left; if (n == NULL) return 0; } assert(n != NULL amp;amp; n-gt;data lt; x); int sum = n-gt;num; // Grab everything left because all of them are lt; x if (n-gt;left != NULL) sum = count_all(n-gt;left); // Some of the right nodes may be lt; x, some may not // Repeat the algorithm to find out if (n-gt;right != NULL) sum = order(n-gt;right, x); return sum; } Это уменьшает количество рекурсий, когда корень больше, чем x , и вы хотите быстро найти следующий левый узел, который удовлетворяет n-gt;data lt; x . Это также устраняет массу ненужных сравнений с x левой стороной дерева, где вы уже знаете, что все есть lt; x .