Как расставить узлы произвольного дерева? [закрыт]

#алгоритм #дерево #графы

                            
             
                
                    
                        
                            Закрыт. Этот вопрос необходимо уточнить или дополнить
подробностями. Ответы на него в данный момент не принимаются.
                            
                        
                    
                
            
                    
                
                        
                            
                        
                    
                        
                            Хотите улучшить этот вопрос? Добавьте больше подробностей
и уточните проблему, отредактировав это сообщение.
                        
                        Закрыт 4 года назад.
                    
                
        

Есть произвольное дерево, узлы-братья удалены друг от друга на динамически задаваемое
значение (в данном случаи 20), так же как и узлы-соседи (в данном случаи 40). В тот
момент, когда самая левая ветвь формируется, вызывается метод расстоновка_узлов в который
передается самый верхний-левый и самый верхний-правый и разница на которую увеличился
промежуток между ними (в данном случаи 20).
Вот что происходит в методе расстоновка_узлов -  

  


в цикле проходим от верхний-левой до верхней-правой и считаем промежутки (в данном
случаи это шесть пустых клеточек, которые как говорил ранее по 20, то есть сумма 120);  
делю сумму полученную на предыдущем шаге на кол-во узлов плюс один (120 / 3 = 40);  
проверяю на сколько текущий узел (я начинаю с лева на право и по этому текущий узел
это тот у которого два ребенка) удален от левого узла-брата (в данном случаи это 80).  
теперь я вычитаю из 80 - 40 = 40, это значение расстояние на которое я смещу текущую
ноду чтобы оказаться в нужном месте.
если это значение (40) больше чем то на которое увеличилось расстояние между двумя
крайними нодами, то это значение становится меньшим. То есть рассчитал что 40, но оно
больше позволенного и по этому значение меняется на 20.  
перемещаю ноду.  


  

Повторяю шесть предыдущих шагов для следующей ноды -
1. получаю 60
2. 60 / 2 = 30
3. 40
4. 30
5. 10
6. ... 

  

Видите как я усреднил? Сначала выяснил что сдвинуть нужно на сорок, но так как на
сорок сдвинуть я не могу (нарушится правило для нижних детей, они будут ближе чем на
сорок), я сдвигаю на максиму возможное, это двадцать. А потом я сдвигаю уже на десять.
Для примера, если бы у первой обрабатываемой ноды не было детей, то картина была
бы следующей -
  

На тот случай, если у меня сначала идет узел который можно сдвинуть на "сколько-то"
(без детей), а после тот который уже нельзя сдвинуть на "сколько-то", то второй я снова
сдвигаю на максимум, но при этом выполняю алгоритм с самого начала (точнее с самой
последней удачной точки), но на время подменяю самый верхний-правый текущим.  

Я бы показал код, но я не хочу чтобы Вы смотрели его недочеты, а лишь хочу чтобы
Вы поняли смысл.  

Вот. Но дальше я столкнулся с следующей проблемой, да и возможно это только одна из ...

Входные данные те же, но все ломается. Алгоритма, как я хотел, не получилось, да
и придумать я не могу.
Ниже конечный результат - 


Что есть у нод
indent - значение на которое текущая нода удалена от предыдущей ||->||
leftOffset - это значение на которое я смещаю влево. В самом начале оно ноль
rightOffset = это то значение на которое смещаю вправо. И тоже по дефолту ноль.  

Вот. Сами ноды, как обычные ноды, ссыдка на парента, в котором они хранятся в индексированном
массиве. Есть методы для получения ноды по индексу и получение самого индекса.
    

Ответы

Ответ 1

В общем, нужно расставлять узлы уже по факту, а не извращаться с двиганием в каких-то
рамках. Есть обе константы, "братья" и "соседи", причем "соседи" определяет, насколько
должны отстоять друг от друга соседние поддеревья на уровнях ниже первого, а "братья"
- на первом. Тогда задачу нужно решать снизу вверх: для каждого поддерева вначале выстраиваем
каждое из собственных поддеревьев, после чего выстраиваем текущее подерево, вычисляя
для каждого следующего поддерева минимальное смещение относительно нуля, при котором
на каждом уровне это поддерево не будет мешать уже установленным поддеревьям. В итоге
каждое подерево будет иметь параметр "занятый диапазон" на каждом уровне, где у него
есть хоть один лист, по нему и будет идти сравнение при размещении текущего поддерева
на верхнем уровне.

Т.е. алгоритм выглядит так:

BuiltTree buildTree(Tree tree) {
    BuiltTree[] siblings;
    foreach (subTree in tree.subTrees) siblings.push(buildTree(subTree));
    BuiltTree result=new BuiltTree(); // пустое
    foreach (sibling in siblings) {
        int minRightPos=0;
        for (i=0;i

Описание “дерева” Oracle в Django models.py

#oracle #python #дерево #django

Доброго времени суток. Помогите, пожалуйста, со следующим вопросом.
Необходимо описать модель дерева в Django. Используемая БД - Oracle.
Описываю так:
class TelDivisions(models.Model):
    parent = models.ForeignKey('self')
    name = models.CharField(max_length=50, blank=True)
    class Meta:
        db_table = u'tel_divisions'

но таким образом parent ссылается сам на себя. Каким образом сделать так, чтобы он
ссылался на столбец id данной таблицы?
Думал может получиться вот так:
class TelDivisions(models.Model):
    parent = models.ForeignKey(TelDivisions, db_column='id', blank=True)
    name = models.CharField(max_length=50, blank=True)
    class Meta:
        db_table = u'tel_divisions'

но команда python manage.py validate выявила:
parent = models.ForeignKey(TelDivisions, db_column='id', blank=True)
NameError: name 'TelDivisions' is not defined

Что, собственно, логично. Как же быть?
Спасибо.    

Ответы

Ответ 1

Рекомендую Вам использовать django-mtpp. Она была создана как раз для отображения
древовидных структур в реляционной модели.
А что касается вашего вопроса:
parent = models.ForeignKey('self', db_column='id', blank=True)

И всё должно заработать. Ссылаться надо на самого себя через self. Данный пример
описан в django docs.
И ещё одно. Если не укажите null = True, то не сможете создать ни одного корновего
экземпляра (т.е. такого, у которого нет родителя). Итого:
parent = models.ForeignKey('self', db_column='id', blank=True, null = True)

db_column='id' можно не указывать, т.к. он и так будет ссылаться по умолчанию на
ключевое поле таблицы, т.е. id.


Ответ 2

Правильно делаешь в первом варианте, в базе будет столбик parent_id типа integer.
Гляньте статейку и комментарии почитайте, там есть полезные ссылочки, сам на днях
разбирался с этим вопросом: деревья в джанго-шаблонах
Если дерево многоуровневое, то mtpp все рекомендуют, но если один уровень вложенности
как у меня, то я без дополнительных библиотек обошелся.

Удаление элемента из дерева, С++

#дерево #бинарное_дерево #алгоритм #cpp

Написал алгоритм удаления элемента из бинарного дерева поиска. Алгоритм не рекурсивный.
Так как это академическая задачка, требуют рекурсивный. Рекурсивный метод у меня не
выходит. Код выкладывать смысла нет. Если у кого есть простой и понятный рекурсивный
алгоритм удаления элемента из бинарного дерева поиска, буду благодарен.     

Ответы

Ответ 1

Если взять такое определение бинарного дерева.
class BinaryTreeNode {
public:
    BinaryTreeNode() : leftChild(NULL), rightChild(NULL), 
        parent(NULL), value(-1) {}
    BinaryTreeNode(int val) : leftChild(NULL), rightChild(NULL), 
        parent(NULL), value(val) {}
public: 
    static int getDepth(BinaryTreeNode * node) {
        int left = 0, right = 0;
        left = getDepth(node->leftChild);
        return 0;
    }
public:
    BinaryTreeNode * leftChild;
    BinaryTreeNode * rightChild;
    BinaryTreeNode * parent;
    int value;
};

То алгоритм может выглядеть так:
void DeleteNodeFromBinary(BinaryTreeNode * node, int value)
{
    if (node == NULL)
        return;

    if (value < node->value)
        return DeleteNodeFromBinary(node->leftChild, value);
    else if(value > node->value)
        return DeleteNodeFromBinary(node->rightChild, value);
    else  {
        if(node->leftChild == NULL && node->rightChild == NULL) {
            if (node->parent->leftChild == node) 
                node->parent->leftChild = NULL;
            else      
                node->parent->rightChild = NULL;
            delete node;
        } else {
            BinaryTreeNode * newnode = NULL;
            if(node->leftChild != NULL) {
                newnode = Rightmost(node->leftChild);
            } else                    
                newnode = Leftmost(node->rightChild);

            if (node->parent->leftChild == node) 
                node->parent->leftChild = newnode;
            else      
                node->parent->rightChild = newnode;

            newnode->parent = node->parent;
            newnode->rightChild = node->rightChild;
            newnode->leftChild = node->leftChild;

            delete node; 
        }
    }
}
BinaryTreeNode * Leftmost(BinaryTreeNode * node) {
    if (node == NULL)
        return NULL;
    if (node->leftChild != NULL) {
        return Leftmost(node->leftChild);
    }
    return node;
}
BinaryTreeNode * Rightmost(BinaryTreeNode * node) {
    if (node == NULL)
        return NULL;
    if (node->rightChild != NULL) {
        return Rightmost(node->rightChild);
    }
    return node;
}

Копия дерева на С++

#дерево #c #бинарное_дерево #алгоритм #cpp

В работе появилась простая, и в тоже время интересная задачка. Необходимо написать
функцию, которая будет копировать дерево. Язык С или С++, лучше на С++.
    

Ответы

Ответ 1

Если считать, что дерево бинарное, то можно предложить следующее:
Объявление класса
class BinaryTreeNode {
public:
    BinaryTreeNode() : leftChild(NULL), rightChild(NULL), 
        parent(NULL), value(-1) {}
    BinaryTreeNode(int val) : leftChild(NULL), rightChild(NULL), 
        parent(NULL), value(val) {}
public: 
    static int getDepth(BinaryTreeNode * node) {
        int left = 0, right = 0;
        left = getDepth(node->leftChild);
        return 0;
    }
public:
    BinaryTreeNode * leftChild;
    BinaryTreeNode * rightChild;
    BinaryTreeNode * parent;
    int value;
};

Функция копирования возвращает указатель на корень нового дерева.
BinaryTreeNode * CopyTree(BinaryTreeNode * node)
{
    if (node == NULL)
        return NULL;

    BinaryTreeNode * newnode = new BinaryTreeNode(node->value);
    newnode->leftChild = CopyTree(node->leftChild);
    newnode->rightChild = CopyTree(node->rightChild);

    return newnode;
}


Ответ 2

Если считать что дерево immutable и ссылки на родительскую вершину не нужны, то можно
скопировать дерево за O(1), достаточно скопировать только корень

Является ли граф деревом [закрыт]

#алгоритм #графы #дерево

        
             
                
                    
                        
                            Закрыт. На этот вопрос невозможно дать объективный ответ.
Ответы на него в данный момент не принимаются.
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            Хотите улучшить этот вопрос? Переформулируйте вопрос,
чтобы на него можно было дать ответ, основанный на фактах и цитатах, отредактировав его.
                        
                        Закрыт 4 года назад.
                                                                                
           
                
        
Задачка: Предложите алгоритм, который определяет, является ли граф деревом.
Мое решение, которое, как оказалась, неверное 
bool is_rec( int arr[SIZE][SIZE], int current, int root, int find )
{
    bool endFlag = true;
    for(int i = 0; i < SIZE; ++i){
        if((arr[current][i] == 1)&&(i!=root)){
            if(i!=find){
                endFlag = endFlag&&is_rec(arr,i,current,find);
            }else{
                return false;
            }
        }
    }
    return endFlag;
}

bool IsTree( int arr[SIZE][SIZE] )
{
    return is_rec(arr,0,0,0);
}

Думаю, некоторым будет интересно решить :)    

Ответы

Ответ 1

Дерево - связный граф с n-1 ребром.
bool dfs(int i, int arr[SIZE][SIZE], bool col[SIZE]) {
  if (col[i]) {
    return 0;
  }
  col[i] = true;
  for (int j = 0; j < SIZE; ++j) {
    if (ar[i][j]) {
      dfs(j, arr, col);
    }
  }
}

bool IsTree(int arr[SIZE][SIZE]) {
  int edges = 0;
  for (int i = 0; i < SIZE; ++i) {
    for (int j = i + 1; j < SIZE; ++j) {
      if (arr[i][j]) {
        edges++;
      }
    }
  }
  if (edges != SIZE - 1) {
    return false;
  }
  bool col[SIZE];
  memset(col, 0, sizeof(col));
  dfs(0, arr, col);
  for (int i = 0; i < SIZE; ++i) {
    if (!col[i]) {
      return false;
    }
  }
  return true;
}


Ответ 2

Моё решение на Pascal. Граф задаётся матрицей смежности (1 - есть ребро, 0 - иначе).
maxV - максимальное число вершин
maxE - максимальное число рёбер
Храню граф списком рёбер.
const
        maxV     = 111;
        maxE     = 111111*2;

var
        n,m,i,j,x       : longint;

        ef,es,next      : array [1..maxE] of longint;
        first,last      : array [1..maxV] of longint;
        c               : longint;

        used            : array [1..maxV] of boolean;
        flag            : boolean;

procedure add(v1,v2 : longint);
        begin
                inc(c);
                ef[c] := v1; es[c] := v2;
                if last[v1] <> 0 then next[last[v1]] := c;
                if first[v1] = 0 then first[v1] := c;

                last[v1] := c;
        end;

procedure dfs(v,dad : longint);
        var
                h,e : longint;
        begin
                used[v] := true;

                h := first[v];
                while h > 0 do begin
                        e := es[h];
                        if used[e] and (e <> dad) then begin
                                flag := false;
                                exit;
                        end;
                        if e <> dad then
                                dfs(e,v);
                        if not flag then
                                exit;
                        h := next[h];
                end;
        end;

begin
        assign(input,'input.txt'); reset(input);
        assign(output,'output.txt'); rewrite(output);

        readln(n);
        for i := 1 to n do
                for j := 1 to n do begin
                        read(x);
                        if x = 1 then
                                add(i,j);
                end;

        flag := true;
        dfs(1,1);
        for i := 1 to n do
                if not used[i] then
                        flag := false;

        if not flag then
                writeln('NO')
        else
                writeln('YES');

end.


Ответ 3

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


Ответ 4

Выполняем обычный проход по графу и каждую пройденный узел заносим в список, при
этом проверяем не содержится ли он в нем уже. Если содержится то всё не дерево :-)

Работа с бинарным деревом

#cpp #дерево

    #include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef int T;

queue  myqueue;

typedef struct Node {
  int data;
  Node *LeftBranch;
  Node *RightBranch;
  Node *Parent;
} Node;

Node* getFreeNode(T value, Node *Parent);

void addToTree(Node **head, int value);

void printTree(Node *Root, const char *dir, int level);

int min(Node *Root);

int find(Node *Root);

Node *deleteNode(Node *Root, int key);

void delete2(Node *Root);

bool isPrime(int n);

int main(int argc, char const *argv[]) {

  Node *Root = NULL;
  int* arr = new int[14];

  srand(time(NULL));
  for (int i = 0; i < 14; i++) {
    arr[i] = rand() % 198 - 99;
  }

  for (int i = 0; arr[i]; i++) {
    addToTree(&Root, arr[i]);
  }

    printTree(Root, "Root", 0);

    cout << "Min: " <LeftBranch = tmp->RightBranch = NULL;
  tmp->data = value;
  tmp->Parent = Parent;
  return tmp;
}

void addToTree(Node **head, int value) {
  Node *tmp = NULL;
  Node *ins = NULL;

  if (*head == NULL) {
    *head = getFreeNode(value, NULL);
    return;
  }

  tmp = *head;
  while (tmp) {
    if (value > tmp->data) {
      if (tmp->RightBranch) {
        tmp = tmp->RightBranch;
        continue;
      }
      else {
        tmp->RightBranch = getFreeNode(value, tmp);
        return;
      }
    }
    else if ( value < tmp->data) {
        if (tmp->LeftBranch) {
          tmp = tmp->LeftBranch;
          continue;
        }
        else {
          tmp->LeftBranch = getFreeNode(value, tmp);
          return;
        }
      }

    }
  }


void printTree(Node *Root, const char *dir, int level) {
    if (Root) {
        printf("lvl %d %s = %d\n", level, dir, Root->data);
        printTree(Root->LeftBranch, "left", level + 1);
        printTree(Root->RightBranch, "right", level + 1);
    }
}


int min(Node *Root) {
 while (Root->LeftBranch) {
   Root = Root->LeftBranch;
 }
 int min = Root->data;
 return min;
}


int find(Node *Root) {
  if (Root == NULL) {
     return 0;
  }

  if (isPrime(Root->data)) {
    myqueue.push(Root->data);

  }
  find(Root->LeftBranch);
  find(Root->RightBranch);
}

Node *minimum(Node *Root) {
    while (Root->LeftBranch) {
        Root = Root->LeftBranch;
    }
    return Root;
}


Node *deleteNode(Node *Root, int key) {
  if (Root == NULL) {
      return Root;
  }
  else {
     if (key < Root->data) {
        Root->LeftBranch = deleteNode(Root->LeftBranch, key);

      }
      else if(key > Root->data) {
        Root->RightBranch = deleteNode(Root->RightBranch, key);

      }
      else if (Root->LeftBranch != NULL && Root->RightBranch != NULL) {
        Root->data = minimum(Root->RightBranch)->data;
        Root->RightBranch = deleteNode(Root->RightBranch, Root->data);

      }
      else {
        if (Root->LeftBranch != NULL) {
          Root = Root->LeftBranch;
        }
        else {
          Root = Root->RightBranch;
        }
      }
    }
    return Root;
  }


void delete2(Node *Root) {
  cout << "My queue equal: ";
  while(!myqueue.empty()) {
    cout << myqueue.front() << " ";
    deleteNode(Root, myqueue.front());
    myqueue.pop();
  }

}

bool isPrime(int n) {
  for (int i = 2; i <= n; i++) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}


Дано бинарное дерево,рандомно было записано данные. Далее необходимо удалить все
простые числа. В функции find() происходит запись в очередь. После в функции delete2()
удаление. 
Проблема: в очередь попадають не те данные что нужно. Из-за етого происходит не коректное
удаление
Вопрос: помогите написать правильную реализацию find()
    

Ответы

Ответ 1

BUG1 : Проверка простоты числа: проверять на деление нужно от 2 до sqrt(n).
BUG2 : addToTree() при добавлении числа , которое уже есть в дереве будет глухой висяк.
BUG3 : min() при пустом дереве будет крушение программы вообще.
BUG4 : delete2(Node*) : новый указатель корня дерева возвращается из  deleteNode,
а сам результат нового корня игнорируется.


Ответ 2

Вы неверно реализовали алгоритм проверки простого числа в isPrime(int n)

#include 

bool isPrime(int n)
{
    for(int i = 2; i <= sqrt(n); i++)
    {
        if(n % i == 0)
            return false;
    }

    return true;
}


Ответ 3

bool isPrime(unsigned n)
{
    unsigned sn = sqrt(n) + 1;
    if(n % 2 == 0) return false;
    for(int i = 3; i < sn; i += 2)
    {
        if(n % i == 0)
            return false;
    }
    return true;
}


Это быстрее, но можно улучшить

Алгоритм упрощения математического выражения с переменными

#алгоритм #математика #дерево #интерпретатор

Здравствуйте! Задача - по возможности упростить математическое выражение. Упростить
- значит привести к более короткому виду. Выражение хранится в обратной польской записи,
или в виде дерева. Например, выражение x*2-(x+x) хранится в виде дерева - 

     (-)
     / \
   (*)  (+)
  /  \  / \
(x) (2)(x)(x)


или в ОПЗ - x2*xx+-
Подскажите, какие есть для этого алгоритмы. 
    

Ответы

Ответ 1

Можно попробовать воспользоваться готовым решением wolframalpha API, если это годится
для вашей задачи.

Вывод дерева mysql

#mysql #sql #дерево

Есть таблица elements следующей структуры Adjacency List Model:

id parent index


Где index - это порядок элемента.
Нужно одним запросом сформировать путь, получающийся при обходе в глубину.
То есть если у нас такой вид:

1 0 1
2 0 2
3 1 1
4 1 2
5 2 1
6 0 3


То выведется
1 3 4 2 5 6

Нужно на чистом mysql без использования php и тд.
Заранее спасибо

P.S. Менять в структуре, к сожалению, ничего нельзя

Заранее спасибо
    

Ответы

Ответ 1

В MySQL нет штатных средств для работы с рекурсивными запросами. Но как известно,
если очень хочется, то можно (хотя выглядит это жутковато и оптимизации по скорости
это не поддается):

select id,path
  from (
   select  @path:=if(@id!=id,`index`,
             coalesce(
               (select concat(`index`,'/',@path)
                  from Tree1 where id=@pid)
             ,@path)
           ) path,
           @pid:=if(@id!=id,parent,
             (select parent from Tree1 N
               where id=@pid)
             ),
            @id:=id id, N
     from Tree1 T,
          (select @n:=@n+1 N
             from Tree1,(select @n:=0) N limit 3) Seq,
          (select @id:=0,@path:='') X
    order by id, N
  ) X
 where N=3
 order by path


Так как ни рекурсии ни циклов в обычном смысле слов нет, то запрос эмулирует рекурсию
с помощью эмуляции цикла. В качестве цикла используется склейка с любой таблицей, в
которой записей не менее, чем максимально возможный уровень иерархии в дереве. В данном
примере используется выборка из той же самой таблицы, явно ограниченная limit 3 (если
вложенность дерева больше - число надо соответственно увеличить). Собственно данные
из этой таблицы не берутся, а создаются порядковые номера (N).

После этой склейки у нас в выборке появляется по 3 записи с одним и тем же id. На
каждой из них, с помощью переменных, мы получаем id очередной родительской ветки, углубляясь
по дереву (так как переменные помнят значения, сформированные в предыдущей строке).
Самое главное, что мы тут формируем это путь к данной записи в виде индексов сортировки
(если index может быть более 9 то для правильной сортировки надо выравнивать его в
пути до одинаковой длины с помощью lpad())

В какой то момент записи родителей заканчиваются, мы дошли до корня дерева, тогда
подзапрос индекса родителя возвращает NULL и при этом с помощью coalesce мы сохраняем
ранее сформированный путь. Таким образом в последней записи нашего "цикла" у нас гарантированно
будет полный путь до данного листа дерева. Нам остается только убрать из выборки рабочие
строки цикла с частично сформированными путями, т.е. выбрать только последние строки
(where N=3) и отсортировать по пути индексов.


Ответ 2

Чтобы вывести полный путь в одном запросе нужно использовать Nested Set Model. (Полная
информация по ссылке)


  Для построения пути можно использовать хранимую функцию. При
  процедурном языке мы можем начать в нижней части дерева и перебирать
  вверх, чтобы вернуть полное дерево или единственный путь.


https://web.archive.org/web/20110606032941/http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

Какие существуют виды деревьев или классификация деревьев в теории графов?

#дерево #графы #бинарное_дерево

Пишу работу по деревьям в теории графов и немного запутался в понятиях. Мне нужно
написать, какие существуют виды деревьев или классификацию деревьев. Я нашел что существует:
ориентированное/неориентированное дерево, остовное, лес, бинарное, n-мерное, упорядоченное
дерево. Но это всё больше похоже на свойства деревьев нежели на виды (кроме бинарного
и n-мерного). 

Что из этого (если я правильно нашел и ничего не пропустил) действительно будет являться
отдельным видом дерева? Также, есть например частный случай бинарного дерева - дерево
поиска. Будет ли такое дерево относиться к теории графов или это больше структура данных
в программировании? Тот же вопрос с деревом синтаксического анализа. И последний вопрос:
относится ли обход дерева к операциям с деревьями как графами или это алгоритм для
структуры данных - дерево?
    

Ответы

Ответ 1

Раз вы пишите какую-то работу на тему деревьев, то лучше как можно более полно изложить
материал.

Часть того, что вы перечислили - общие понятия для графов, часть - понятия для деревьев.

Я бы на вашем месте сделал классификацию по признакам:

По направленности - ориентированное (однонаправленное, двунаправленное), неориентированное

По степени вершины (бинарное, n-арное, и т.п.)

По частным случаям - тоже неплохо описать было бы, чего как. Дерево бинарного поиска
можно вложить в классификацию по степеням вершины и описать чем оно выделяется. Дерево
синтаксического анализа более специфичная вещь, но если сможете описать - отлично.

Поскольку дерево является графом, то к нему применимы классические алгоритмы обхода
любого графа, но помимо этого существуют специфичные алгоритмы именно для деревьев.

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

Алгоритм разбиения дерева на компоненты связности

#алгоритм #графы #дерево

Есть дерево, в котором каждая вершина имеет свой вес, нужно разбить дерево на три
компоненты связности, в каждой из которых суммарный вес всех вершин одинаков. 

Подскажите, какой алгоритм стоит использовать? 

Пока вижу такое решение - перебор всех пар ребер, с последующей проверкой - но это
тяжелое решение по производительности.
    

Ответы

Ответ 1

Ясно, что для выполнения разбиения надо удалить ровно два ребра. Ясно также, что
каждая компонента будет деревом. Также заранее ясно, чему будет равен суммарный вес
вершин в каждом из трех поддеревьев. Пусть это будет Starget.

Обозначим любую вершину дерева корнем и далее рассматриваем корневое дерево.


Будем строить наши связные компоненты путем наращивания (и объединения) множества
поддеревьев снизу-вверх, от листьев к корню. Начинаем с набора стартовых поддеревьев,
каждое из которых состоит из одной листовой вершины дерева. 
Если на каком-то этапе построения мы обнаруживаем поддерево T с суммой Starget, то
существует решение, включающее поддерево T (если у задачи вообще есть решение). Все
остальные варианты разбиения могут лишь "наращивать" T дополнительными вершинами, суммарный
вес которых равен нулю. Будем назвать поддерево с суммой Starget завершенным.
Рассмотрим незавершенное поддерево T, корневая вершина которого являются сыном вершины
P. Ясно, что P должно входить в одну и ту же связную компоненту, что и T. 
Из последнего утверждения сразу следует, что если у нас есть несколько незавершенных
поддеревьев, корневые вершины которых являются сыновьями одного и того же предка P,
то все они должны входить в одну и ту же связную компоненту, включающую также и P.


Отсюда автоматически следует, что решение задачи достаточно тривиально: 


Начинаем с набора стартовых поддеревьев T, каждое из которых состоит из одной листовой
вершины дерева.   
Циклически обрабатываем текущий набор поддеревьев T, пока у нас не останется ровно
одно поддерево:
    Если суммарный вес какого-то поддерева строго равен Starget (завершенное поддерево),
то считаем его частью результата и исключаем из дальнейшего рассмотрения (исключаем
из T и условно исключаем из исходного дерева). 
    Если в процессе такого исключения какая-то вершина исходного дерева становится
листовой, то добавляем ее в T как отдельное поддерево.
    Если у нас в T присутствуют все незавершенные поддеревья, чьи корни являются
сыновьями некоей вершины P, то объединяем их в одно поддерево с корнем P.
По завершению работы цикла 2-5 мы получим набор связных компонент, полученных на
шаге 3, а также единственное оставшееся поддерево в T. 
    Если на шаге 3 получено ровно 2 завершенных поддерева, а вес оставшегося поддерева
в T тоже равен Starget - то это наше решение. 
    Если на шаге 3 получено ровно 3 завершенных поддерева, а вес оставшегося поддерева
в T равен нулю - то объединяем оставшееся поддерево с любым из завершенных и получаем
решение.
    В противном случае задача решения не имеет.


Ответ 2

Задачка, кажущаяся на первой взгляд, переборной со сложностью  (N -- число вершин),
может быть решена проще, быстрее, за полиномиальное время. Почему это так я хочу описать
ниже.

Во-первых, кажущийся переборный алгоритм имеет место для произвольного графа (возможно
есть оптимизации и можно решить быстрее). У нас же граф очень специфический. Он намного
проще того, что есть в общем случае. Эта простота, например, выражается в отсутствии
циклов.

Во-вторых, нам нужно разбить наш граф всего на 3 компоненты связности.

Теперь давайте обсудим: как это разбивать граф на компоненты связности. Мы сразу
скажем, что разбиение на компоненты связности -- это удаление некоторых рёбер. Приведу
пример разбиения на компоненты связности следующего графа:



Получим 2 компоненты связности:



Получим 3 компоненты связности:



Другой пример. Получим 2 компоненты связности (вершина 1 -- это заменена на вершину 15):



Получим 3 компоненты связности:



Как можно наблюдать, всегда при удалении 1 ребра, появляется ещё одна компонента
связности. Это можно доказать срого. Но воздержимся, дабы не загружать текст. Таким
образом, нужно удалить 2 ребра так, чтобы у нас оказалось 3 компоненты связности.

Давайте немного переформулируем задачу. Нам необходимо поставить 2 метки на рёбра
так, чтобы в каждой компоненте оказался суммарный вес одинаковым. Что же для этого
нужно сделать? ОЧЕВИДНО! Перебрать все пары рёбер. Для этого занумеруем их от 0 до
N-1. Переберём все пары рёбер. И для каждой пары будем проверять: правильное ли у нас
разбиение или нет. Напишем псевдокод:

# Перебираем все рёбра
for i in range edge:
    for j in range edge:
       # Если разбиение делит наше дерево на равные по весу части, то заканчиваем
выполнение
       if Splitting(i, j):
           break


Очевидно, что сложность такого алгоритма будет полиномиальной 

,

где g(n) -- время работы Splitting. 

Но что делаь с функцией Splitting(i, j)? Очевидно, что Splitting(i, j) может отработать
за линейное время. Запустим из каждой вершины обход в глубину, причём, если в некоторой
вершине мы уже были, то не будем туда заходить больше. Вот и получится, что мы обошли
все вершины лишь по одному разу. Т.е. мы обошли каждую компоненту связности единожды.
В таком случае, ассимптотическое время работы будет , хотя, по факту, это будет 2N.
Внутри DFS (обход в глубину) мы будем считать веса для каждой компоненты связности.

Время работы Splitting можно улучшить следующим образом. Сделаем для этого предподсчёт.
Для каждого ребра будем хранить 2 параметра: суммарный вес вершин выше ребра и суммарный
вес ниже ребра. Приведём пример:



Т.е. для ребра, соединяющего вершины 15 (она же 1, см. выше) и 3, мы можем посчитать
суммарный вес в каждом кластере. Делать это будем следующим образом. Запустим LR-обход
дерева и для каждого ребра (Замечу, что рёбра можно ассоциировать с соответствующими
вершинами. Например, ребро (11, 10) ассоциируем с вершиной 11, ребро (6, 2) ассоциируем
с вершиной 6 и т.д. Далее будем говорить о вершинах, а не о рёбрах).

Продемонстрируем пример обхода:

0 - 10 - 11 - 12 - 13 - 15 (1) - 3 - 4 - 5 - 9 - 2 - 6 - 7 - 8


При обходе будем суммировать считать вес поддерева. Под весом поддерева будем разуметь
сумму всех вершин. Пусть на i-ом шаге мы уже подсчитали вес поддерева с корнем в вершине
v. Тогда нам необходимо перейти на уровень выше и посчитать вес поддерева более высокого
уровня. Проиллюстрируем на рисунке ниже. 



Пусть мы находимся в вершине 11. И для поддерева этой вершины мы уже посчитали вес
(на рисунке она изображена листом, но будем считать, что у неё есть поддерево). Тогда
нам необходимо перейти в вершину 10 и подсчитать вес поддерева вершины 10. В порядке
LR-обхода, посетим и подсчитаем вес поддерева с корнем в вершине 12, 13. Тогда вес
поддерева с корнем в вершине 10, будет суммой весов поддеревьев 11, 12, 13:



Имеем формулу в общем случае:



Для вершины v обозначим вес дерева выше неё:



ниже неё:



Теперь, нам нужно вычислить аналогично, для каждой вершины вес дерева выше неё. Для
этого будем считать, что выше корневой вершины ничего нет. Тогда ещё раз запустим LR-обход
(модифицированный). Модификация будет состоять в том, что мы будем осуществлять все
действия ещё при спуске.

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

Таким образом, для каждой вершины имеем вес дерева ниже неё и вес дерева выше неё.

Теперь нам необходимо научиться быстро узнавать: лежит ли данная вершина v в поддереве
другой вершины u. Введём функцию:



Для её быстрого вычисления нам понадобятся дополнительные ухищрения. И ещё один предподсчёт.

Где хранить исходные файлы / задания проекта?

#файловая_система #дерево #проект

Интересует правильное именование папок или файловой структуры (если такая существует).

В самом начале разработки мне передают файлы для верстки, ТЗ и т.д.
Где правильно хранить исходные файлы проекта?
Например, такие как:


design.psd
design.jpg
ТЗ.doc


и т.п.

Естественно, файлов может быть больше / меньше и их названия могу варьироваться.
Основной смысл заключается в правильности их размещения в проекте или вне проекта.

Push-ить ли их в репозиторий вместе с исходными кодами или нет?

Изначальная файловая структура была следующей:  


  .git
  .idea - именно сюда я и складывал изначальные файлы, пока не прочитал, что это
директория для IDE, в связи с чем и возник данный вопрос.
  src
  package.json
  ...

    

Ответы

Ответ 1

Ваш вопрос:  


  Интересует правильное именование папок или файловой структуры (если такая существует).  


Ответ:
Могу лишь поделится личным опытом структурирования файлов на фронтенде. На вопрос,
как правильно, который я задал с десятку знакомых (когда у меня он встал на повестке
дня), мне отвечали по разному, но общая параллель была. В основном это две основные
папки (названия каждый называл разные, но суть одна и та же) + папки node_modules,
bower_components. Эта структура обычного фронтенд проекта (хотя, как написал выше,
все это опционально). 
 Получается структура вроде этой:  


  |-/build
  |-/node_modules
  |-/bower_components
  |-/src
  |--- doc/
  |--- fonts/
  |--- img/
  |--- scripts/
  |--- style/
  |--- vendors/
  |--- template/
  |--- index.html
  |- .gitignore
  |- gulpfile.js
  |- package.json
  |- bower.json
  |- README.md  


/built - папка продакшена (многие ее именуют /dist).
/src - папка исходников (многие ее именуют /app).  

Также еще может быть отдельная папка для тасков. Папка /src тоже может структурироватся
иначе, не все прям в нее на кучу (все зависит от объема), а подразделять ее на папки
типа: /assets,/template и т.д.  

Ваш вопрос:  


  В самом начале разработки мне передают файлы для верстки, ТЗ и т.д.
  Где правильно хранить исходные файлы проекта?  


Ответ:
Я храню в /template, мне кажется это логичным. Также рекомендую нормально структурировать
.gitignore - комментируйте, что там откуда и куда, вам же легче будет.  

Ваш вопрос:  


  Push-ить ли их в репозиторий вместе с исходными кодами или нет?  


Ответ:
Я не делаю для них push, нет необходимости.


Ответ 2

Нашел ответы по запросу: 


  структура проектной папки


И как осознание, что единой структуры не существует и под каждый проект своя структура.

Решил взять на вооружение некоторые советы отсюда:
https://habrahabr.ru/post/319296/

Создал рядом с папкой 


  .git


папку 


  .incoming  


В которой уже все структурирую в зависимости от проекта.

Максимальная непрерывная сумма в двоичном дереве за N переходов

#алгоритм #дерево #теория

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

Мой текущий алгоритм:


Найти последний доступный узел(в котором количество ходов равно 0, либо отсутствуют
дети).  
Записать в массив текущее значение и количество доступных ходов(с учетом потомков).
Перейти в родительский узел, скопировать оба массива(если 2 потомка), либо 1 массив
(1 потомок).
Повторять п.2-3 до возврата в корневой узел.
На основании массива в корневом узле (в котором находятся все
возможные сочетания значений+ходов) найти максимальное значение.


Основные вопросы:


Существует ли лучший алгоритм?
Возможно ли оптимизировать данный алгоритм т.к. работает слишком
долго и требует слишком много памяти?

    

Ответы

Ответ 1

Решение за N*S памяти, N*S*S или N*S*log S времени. S - размер дерева.

Динамика F[vert][size] - оптимальный ответ если мы в поддереве вершины vert берём
size элементов.

Для любого элемента F[u][0] = 0
Для листа на этом всё. 

Для вершины псевдокод. (r - правый потомок, l - левый).

for (int i=0;i
Ответ 2

Собственно ответ,возможно пригодится кому-то:
В дереве всегда добавляю сначала левую ноду , затем правую(см. if(left!=NULL & right==NULL).

void getMax(Node *curr,int turns)
{
    int i,j;
    if(curr->left!=NULL && turns!=0)
        getMax(curr->left,turns-1);
    if(curr->right!=NULL && turns!=0)
        getMax(curr->right,turns-1);
    curr->res=new int[turns+1]();
    curr->res[0]=0;
    if(curr->left==NULL && curr->right==NULL || turns==0)
    {
        for(i=1;ires[i]=0;
        return;
    }
    else
    {
        if(curr->left!=NULL && curr->right==NULL)
        {
            Node*next=curr->left;
            for(i=0;ires[i+1]=next->res[i]+next->value;
            }
        }
        else
        {
                Node *left=curr->left;
                Node *right=curr->right;
                for(i=0;ires[0]=0;
                            }
                            if(i==0 && j>=1)
                            {
                                curr->res[j]=max(curr->res[j],right->value+right->res[j-1]);
                            }
                            if(i>=1 && j==0)
                            {
                                curr->res[i]=max(curr->res[i],left->value+left->res[i-1]);
                            }
                            if(i>=1 && j>=1)
                            {
                                curr->res[i+j]=max(curr->res[i+j],left->value+right->value+left->res[i-1]+right->res[j-1]);
                            }

                    }
                }
    }
}
}


и сам класс

class Node
{
public:
Node *parent;
Node *left;
Node *right;
int id;
int value;
int *res;};

Деревья Меркле. Проверка “листьев” в ее составе

#алгоритм #хеширование #дерево #blockchain

Читаю интернет и не до конца понимаю одну вещь. Есть Дерево Меркля (или Меркле).
Допустим оно имеет N-количество отсортированных "листьев", представляющими блоки данных.
Как проверяется, что конкретный "блок" не находится в дереве?


    

Ответы

Ответ 1

Проверка принадлежности происходит очень просто - считается хеш блока, а потом просто
проверка с хешом во всех листьях. Если есть совпадение, дальше проверяется валидность
самого дерева, проходом от этого листа до корня дерева. Например, если это L2 на вашем
рисунке, тогда проверяется Hash(Hash(0-0), Hash(0-1)), и дальше корневой хеш: Hash(Hash(0),
Hash(1))

Свойства криптографических хеш-функций гарантируют, что произведя всего несколько
простых вычислений хеша над небольшими объемами данных, мы гарантируем, что этот блок
данных действительно входит в хеш в корне дерева.

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

Еще хочу добавить, что операция проверки блока в дереве, это не то, ради чего используют
дерево Меркля в blockchain-технологиях. Основное преимущество, это очень быстрый пересчет
хеша при поступлении новых данных. А так же быстрый пересчет хеша, при удалении блока
данных.

Пример с биткоин. Майнер непрерывно изменяет несколько байт в блоке, и считает хеш,
что бы получить хеш начинающийся с множества нулей. В это время приходят новые транзакции,
и нужно быстро пересчитать хеш в корне дерева (который является частью блока). Для
этого понадобится всего O(log n) операций пересчета хеша. Если майнер решил выкинуть
транзакцию с блока, и включить другую (с большей комиссией), все так же нужно O(log
n) пересчетов.

Бинарное дерево поиска на C/C++

#c #алгоритм #бинарное_дерево #дерево #cpp

Есть задачка. Имеется бинарное дерево. Требуется определить, является ли это дерево
бинарным деревом поиска. Желательно представить решение на языке С++ или С. Оцениваются
временная и пространственная сложность алгоритма, а так же универсальность подхода.    

Ответы

Ответ 1

UPD: моя неправда, исправляю.
Предположим, что дерево определено так:
struct BinaryTreeNode {
    BinaryTreeNode(int val) : leftChild(NULL), rightChild(NULL), 
        parent(NULL), value(val) {}

    BinaryTreeNode * leftChild;
    BinaryTreeNode * rightChild;
    BinaryTreeNode * parent;
    int value;
};

Тогда алгоритм проверки будет следующим:
bool isBST(BinaryTreeNode * root)
{
    return isBST_(root, 0, 0);
}

bool isBST_(BinaryTreeNode * node, BinaryTreeNode * minParent, BinaryTreeNode * maxParent)
{
    if (minParent && minParent->value >= node->value)
        return false;
    if (maxParent && maxParent->value <= node->value)
        return false;
    if (node->leftChild != 0 && !isBST_(node->leftChild, minParent, node))
        return false;
    if (node->rightChild != 0 && !isBST_(node->rightChild, node, maxParent))
        return false;
    return true;    
}

Временная сложность O(n), где n — количество узлов в дереве. Пространственная сложность
O(h), где h — глубина дерева.


Ответ 2

http://www.structur.h1.ru/derevo.htm - тут написанна структура дерева
по сути ваша задача хорошо решается рекурсией рекурсивно идете вниз по дереву если
при проверке оказывается что это не дерево - throw SomeError; если все нормально -
то никаких исключений кидать не надо рекурсия развернется свернется и говорите что все ОК


Ответ 3

Обходим дерево по правилу ЛКП, по дороге проверяем, получается ли возрастающая последовательность
(или убывающая, можно определить по первым двум неравным значениям). Если не получается
- то не дерево поиска. Как то так.

Почти полное бинарное дерево

#дерево #бинарное_дерево #cpp

Подскажите, пожалуйста, как сделать так, чтобы функция проходилась к примеру по всей
левой части дерева? 

Я сделал функцию проверки дерева на то, является ли оно почти полным, но при входе
в левое поддерево, функция проверяет не всех потомков.. аналогичная проблема в правом
поддереве

bool PBDPP1 (TNode* ptree, int &cnt)
{
    if (ptree != NULL)
    {   cnt++;
        if(ptree->right != 0 && ptree->left == 0)            
            return false;
        PBDPP1(ptree->left, cnt);
        PBDPP1(ptree->right, cnt);
    }
    else return true;
}

bool PPBD(TNode *rootTree)
{
    int cnt1 = 0, cnt2 = 0;
    if(rootTree != NULL)
    {
       if(PBDPP1(rootTree->left, cnt2))
       {
          if(PBDPP1(rootTree->right, cnt1))
          {
              int res = cnt2 - cnt1;
              if(res >= 0)
                  return true;
              else
                  return false;
          }
       }
   }
   else return false;
}


Напомню, почти полным двоичным деревом называется двоичное дерево, для которого существует
такое целое число h ≥ 0, что: 


каждый лист в дереве имеет уровень h или h + 1
если узел дерева имеет правого потомка уровня h + 1, тогда все его левые потомки,
являющиеся листами, также имеют уровень h + 1.

    

Ответы

Ответ 1

Решение взято от сюда. 

Предлагается обходить дерево в ширину и на каждом шаге проверять условия:


если найден лист то все последующие узлы также листы
если узел имеет правого потомка, то он должен иметь и левого.


В коде вот так примерно:

bool IsAlmostComplete(TNode * root)
{
    std::queue nodes;
    nodes.push(root);

    bool leaf_found = false;
    while(!nodes.empty())
    {
         TNode * node = nodes.front(); 
         nodes.pop();

         if(leaf_found && (node->left || !node->right))
             return false;          // у автора true, думаю он ошибся

         if(!node->left && !node->right)
             leaf_found = true;

         if(node->left && !node->right)
             return false;

         if(node->left)
             nodes.push(node->left);

         if(node->right)
             nodes.push(node->right);
    }
    return true;
}

Упорядоченный обход префиксного дерева

#алгоритм #структуры #дерево #структуры_данных

Существует префиксное дерево (нагруженное дерево, trie).


Дерево хранит в себе пару ключ/значение.
Необходимо реализовать упорядоченный обход дерева по значению, т.е. необходимо идти
от ветвей с наибольшим значением к ветвям с наименьшим.
Поскольку первая и вторая пары результирующего набора могут быть в противоположных
ветвях, то возникают сложности.

Обновление

Дерево никак не отсортировано. У каждого узла может быть бесконечно потомков. Думаю
хранить в каждом узле максимальное значение на этой ветви. И пытаться делать прицельный
обход.
    

Ответы

Ответ 1

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

При этом построение кучи O(2n*log n), добавление элемента O(log n)

Ускoрение суффикснoгo автoмaтa

#c #дерево #cpp #теория_автоматов

Имеется суффиксный автомат. Необходимо найти самую длинную пoдстpoку (oбщyю).
Автомат реализован на основе данной статьи: Суффиксный автомат.
(если с суффиксным автоматом не знакомы или статью не смотрели, дальше можно не читать)
Работает быстрее Хорспула. Но при работе с длинными строками скорости всё равно недостаточно.
Может кто-нибудь работал с подобной структурой и знает, как её можно ускорить?    

Ответы

Ответ 1

Из известных сейчас данных можно сделать вывод, что асимптотически улучшить ничего
нельзя, 500000 тысяч раз выполнять O(5*1000) с маленькой скрытой константой даст таки
4-5 секунд.
Остается попробовать уменьшить эту константу.
1) 
if (state.next[DELIM_FIRST + i] != 0)
...
for (int i = 0; i < ALPHABET; i++)
{
    if (state.next[CHAR_FIRST + i] != 0)
    {

так делать не совсем верно в плане быстродействия. map::operator[] вставляет элемент
при его отсутствии, а значит появятся пустые переходы, в которых нет необходимости.
Нужно что то такое:
if (state.next.find(DELIM_FIRST + i) != state.next.end())

а тут просто перебор:
for (std::map::const_iterator i = state.next.begin(); i!= state.next.end(); ++i)
{
    ...

Так немного ускорим обработку, убрав заранее ненужные операции.

2) Раз строк для поиска всего 5, state::result можно сделать std::bitset или свою
битовую маску на базе char/int.
3) В реализации из оригинальной статьи используется std::map для хранения переходов.
Это дает экономию памяти и быстрый перебор, но требует логарифмическое время на нахождение
перехода. Переходы эти можно сделать обычным массивом, это даст честную константу на
поиске, но придется перебирать отсутствующие переходы при переборе (в старой версии
статьи об этом было написано, не знаю почему убрали)
struct state {
    int len, link;
    int next[ALPHABET_SIZE];
};

На деле в столь маленькой std::map будет больше оверхэда (на поддержание дерева),
и она будет работать помедленнее массива. Имеет смысл поменять и посмотреть (Если сделать
так, совет #1 будет неверен).
Еще можно поменять на хэш-таблицу.
Не исключены также оптимизации исходящие из структуры входных данных.

UPD.
4) Присваивание лучше конечно убрать, вместо оператора суммы для состояния сделать
operator | (это семантически вернее отражает действие), внутри битовый OR для маски.

Дерево в SQL

#дерево #sql

Всем добрый день. У меня появился такой вопрос. Скажем имеется таблица в которой
хранится древовидная структура. Допустим в таблице есть Id - ид записи и IdParent -
ид родителя. Как можно с помощью sql запроса выбрать самого верхнего родителя у записи
с id = 10? Возможно ли вообще такое средствами sql?    

Ответы

Ответ 1

Возможность создания рекурсивных запросов есть начиная с SQL 1999. Это возможно с
помощью  оператора WITH. В MS Sql будет выглядеть так: 
WITH rec AS
(
   SELECT * 
   FROM MyTable
   WHERE Id = 10

   UNION ALL

   SELECT mt.*
   FROM MyTable mt
   JOIN rec p ON mt.parentID = p.id
)
SELECT ParentId 
FROM rec
where Id = 10

Если не ошибаюсь, в MySql это работать не будет. Насчет Oracle - не в курсе


Ответ 2

@ReinRaus - вместо NS, я бы посоветовал использовать Materialized path (PostgreSQL
Ltree). У NS возникают большие нагрузки при перемещении узла с большим количеством
дочерних элементов, так как для каждого элемента необходимо пересчитать левый и правый
ключи.


Ответ 3

По стандарту вроде нельзя. Для Oracle, PostgresSQL есть реализация древовидных запросов.
В MS sql server'e вроде от версии зависит, в новых вроде появилась возможность но не
уверен. По стандарту можно только если костылями со вложенными запросами ограничив
по уровню вложенности например так:
  select * from table as l0 
  left join table as l1 on(l1.parent_id = l0.id)
  left join table as l2 on(l2.parent_id = l2.id)
  left join table as l3 on(l3.parent_id = l1.id)
  where l0.parent_id is null and (l1.id = 10 or l2.id = 10 or l3.id = 10)

Оптимизация операций для двоичного индексированного дерева (дерево Фенвика)

#алгоритм #любой_язык #дерево #структуры_данных #сложность

Я занимаюсь оптимизацией в одном проекте, который сильно не укладывается в требования
по производительности. Тут широко используются деревья Фенвика для быстрого получения
префиксных сумм (AKA промежуточные суммы) для  массива с постоянно изменяющимся содержимым.
Сама по себе структура очень полезная и сильно выручает, но здесь кроме стандартных
операций инкремента произвольных элементов очень часто используются две дополнительные
нестандартные операции (я не нашел аналогов в литературе). И на эти операции приходится
значительная часть вычислительной нагрузки.


Получение значений (выгрузка во внешний массив) префиксных сумм для
элементов из непрерывного диапазона от i до i + k.
Обнуление (или, скажем, заполнение константой) элементов из непрерывного
диапазона от i до i + k с корректным пересчетом всех затрагиваемых сумм.


Важно: Для обоих операций среднее значение k много меньше n (количества элементов
в дереве).

На данный момент реализованы эти операции тупо и просто:


В цикле (отдельно!) для каждого элемента из диапазона выполняется нахождение его
значения (стандартная операция для дерева Фенвика). Итого: сложность операции составляет
O(k*log(n)) для k элементов.
В цикле (отдельно!) для каждого элемента выполняется нахождение его значения, после
чего выполняется его инкремент на число обратное его текущему значению (для сброса
в ноль). Сложность, опять же, равна O(k*log(n)).


Я задумался над структурой деревьев и этими операциями. И мне кажется, обе они могут
быть реализованы с меньшей сложностью. Ведь log(n) это глубина прохода от корня до
произвольного элемента, а в этих операциях выполняется обход группы последовательно
расположенных элементов. Из этого факта возможно извлечь пользу, так как ближайший
общий узел дерева в лучшем случае лежит на глубине log(k) от любого из конечных узлов
в непрерывном диапазоне длинной k. Значит для обхода всего диапазона можно спуститься
от корня за log(n), после чего подниматься и спускаться от одного соседнего элемента
к другому за log(k). Итого: сложность алгоритма должна составить O(log(n) + k*log(k))
(что намного лучше текущего варианта). Это для лучшего случая. Но и средняя оценка
должна быть близка к этому, так как худший случай O(k*log(n)) маловероятен при k ≪ n.

Сейчас я залип над реализаций алгоритмов для этих двух операций. Пока что мне не
совсем понятно как перейти от элемента i к элементу i+1, не возвращаясь к корню. По
идее надо подниматься до ближайшего общего узла и спускаться обратно к следующему элементу,
по дороге подсчитывая суммы, необходимые для получения значения следующего элемента.
А для операции (2), видимо, следует на этом же проходе одновременно корректировать
значения промежуточных узлов как при выполнении стандартного инкремента (если это вообще
возможно сделать одновременно).

Это все общие соображения для бинарных деревьев. Как это должно реализовываться конкретно
для дерева Фенвика я пока не представляю.

Буду благодарен за помощь с конкретными алгоритмами на псевдокоде или любом императивном
языке.

Если мои рассуждения на счет сложности неверны, то хотелось бы узнать в чем конкретно
я ошибаюсь.
    

Ответы

Ответ 1

Да, можно попробовать ускорить эти операции. Приведу для начала свою реализацию: 

int next2n(int x) {
    // only 32bit
    x = x - 1;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    return x+1;
}
class BIT_plus {
    std::vector in;
    std::vector num;
    int n;
     public:
    BIT_plus(int n) {
        init(n);
    }

    BIT_plus(const std::vector& list) {
        init(list);
    }

    void init(const std::vector& list) {
        init(list.size());
        for(auto i=0u; i < list.size(); ++i) {
            inc(i, list[i]);
        }    
    }

    std::vector sum_dip(int start, int len) {
        int summ = sum(start);
        std::vector res;
        for(int i=start; i < start + len; i++) {
            res.push_back(summ);
            summ += num[i+1];
        }
        return res;
    }

    void init(int n) {
        in.assign(n, 0);
        num.assign(n, 0);
        this->n = n;
    }

    int size() {
        return n; 
    }

    void inc (int i, int delta) {
        num[i] += delta;

        for (; i < n; i = (i | (i+1)))
            in[i] += delta;
    }

    int sum (int r) const {
        int result = 0;
        for (; r >= 0; r = (r & (r+1)) - 1)
            result += in[r];
        return result;
    }

    int sum (int l, int r) const{
        return sum (r) - sum (l-1);
    }

    void fill_const(int start, int len, int val) {
        int n2n = next2n(start + len + 1)-1;
        int sumdelta = 0;
        for(int i = start; i < start + len; i++) {
            int delta = val - num[i];
            sumdelta += delta;
            for(int j = i; j < n2n; j = (j|(j+1))) {
                in[j] += delta;
            }
            num[i] = val;
        }
        for(int i = n2n; i < n; i = (i|(i+1))) {
            in[i] += sumdelta;
        }
    }

    auto get_num() const {
        return num;
    }
    auto get_in() const {
        return in;
    }
};


Она немножко раздута лишними методами, но всё самое важное в ней есть. (За некоторую
основу взял реализацию отсюда). В ней по сравнению с обычной реализацией есть два новых
метода: fill_const (заполняет определенным числом диапазон исходной последовательности)
и sum_range (возвращает префиксные суммы элементов из диапазона).



Основная идея реализации довольно проста. Она заключается в том, что помимо непосредственно
массива для дерева Фенвика(in) мы храним и сами исходные элементы (num).
1. Тогда нахождение всех префиксных сумм из диапазона [i, i+k] происходит так: сначала
мы находим префиксную сумму для i-го элемента. Это происходит как и в обычной реализации.
Сложность вычисления будет O(log(n)). А дальше, чтобы найти sum(i+1) прибавить число
num[i+1]. И действительно если sum(i) -- сумма первых i элементов, то 
sum(i) + num[i+1] -- сумма первых i+1 элемента.
2. Вторая часть с заполнением константой чуть сложнее. Сначала поймём, какие элементы
нам нужно изменить в исходном массиве in. Если мы
 меняем элемент с индексом i, то сначала мы должны сменить элемент с индексом i,
потом f(i), f(f(i)), где f(i) = i|(i+1) ( | --
 побитовое или).
Заметим, что если в какой-то момент мы попали в 2k-1, то дальше мы также будем попадать
в 2i-1. Более того, если мы начинаем из некого числа i, то в следующее за ним число
вида 2k-1 мы2 не пропустим (иначе как мы получим единицу в следующем разряде, а функция
у нас монотонно возрастающая). 
Воспользуемся этим так: от числа j из [i, i+k) будем изменять ячейки (по стандартным
правилам. Прибавляя к ним delta) пока номер ячейки, которую мы меняем будет меньше,
чем следующее за i+k число вида 2k-1 (next2n(i+k)). Дальше же индексы массива, который
мы будем менять для всех j совпадут. И менять мы их будем на сумарную величину изменений
всех ячеек.

Вероятно, второй алгоритм можно несколько оптимизировать (сейчас он работает, кажется,
за O(k*log(i)+log(N)), что асимптотически не быстрее (i может быть порядка n), но быстрее
практически особенно при маленькиx i), но уже в такой его реализации он будет работать
быстрее, чем независимое изменение для каждой переменной.


Ответ 2

Операция выгрузки ответов во внешний массив делается за O(k + log n) следующим образом:


Отдельно храним исходный массив
Выгружаем за O(log n) сумму до первого элемента (i).
За O(1) прибавляем к ней элемент i+1, получаем сумму до элемента i+1.
Аналогично считаем суммы до всех элементов до i+k, итого O(k) операций.


С изменением сложнее - дерево Фенвика такую операцию так просто не поддерживает.
Однако вам может помочь дерево отрезков с групповым изменением - оно весьма популярно
в спортивном программировании. По этому поводу есть, например, руководство на e-maxx,
но никаким разумным стандартам читаемости и поддерживаемости кода оно не удовлетворит,
поэтому надо вникать и писать свою реализацию (возможно, есть библиотечная, но я не
изучал).

Дерево отрезков позволит сделать подсчёт суммы и массовое присваивание на любом отрезке
за O(log n) (независимо от k), а выгрузку операций можно либо сделать за O(k * log
n) "в лоб", либо за O(k + log n) примерно той же оптимизацией, что и с Фенвиком - сначала
считаем сумму до элемента i, а далее по одному находим значения следующих элементов.
Это можно делать массово, и там получится O(k) операций (придётся полностью обойти
несколько поддеревьев суммарного размера O(k)).


Ответ 3

Алгоритмы с использованием массива исходных данных (из которых строилось дерево)
будут, конечно, работать быстрее. Так что, если проект позволяет хранить копию исходных
данных параллельно с деревом Фенвика, рекомендую обратиться в первую очередь к ответам
других участников.

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

Пункт 1 - получение значений (выгрузка во внешний массив) префиксных сумм для элементов
из непрерывного диапазона от i до (i+k)

Перейти от префиксной суммы i-го элемента к префиксной сумме (i+1)-го на самом деле
несложно.
У меня получился следующий алгоритм:
1) собираем частичные суммы, составляющие i-й элемент, кладём их в структуру данных
"стек", в порядке их индексов в дереве от наименьших к наибольшим;
   в целях оптимизации можно хранить в стеке не сами частичные суммы а нарастающий
итог по ним;
   вершина стека при этом будет хранить значение i-й префиксной суммы (возвращаем
её в ответ);
например, при i = 10, стек будет таким:
   stack[0] = tree_item[7]
   stack[1] = tree_item[7] + tree_item[9]
   stack[2] = tree_item[7] + tree_item[9] + tree_item[10]  // вершина стека, равная
10-му префиксу
   кстати, максимальный размер этого стека совсем невелик - log2(max_size), т.е.
когда количество исходных элементов описывается 32-разрядным числом, размер данного
стека будет всего 32 элемента;
2) рассматриваем двоичную запись числа (i+1), записывая биты слева направо от старших
к младшим;
   если двоичная запись заканчивается нулём, переходим к следующему шагу;
   если двоичная запись заканчивается некоторой непрерывной последовательностью единиц,
то подсчитываем количество этих единиц, и удаляем с вершины стека столько элементов,
сколько обнаружили завершающих единиц;
например, при i = 10, имеем:
   (i+1) = 11 (десятичная запись) = 0001011 (двоичная запись);
   двоичная запись числа заканчивается группой из 2-х единиц;
   следовательно, снимаем со стека 2 элемента, и содержимое стека становится таким:
   stack[0] = tree_item[7]
3) добавляем в стек (i+1)-й элемент дерева;
   при этом вершина стека станет содержать значение (i+1)-й префиксной суммы (возвращаем
её в ответ);
например, при i = 10, имеем:
   stack[0] = tree_item[7]
   stack[1] = tree_item[7] + tree_item[11]  // вершина стека, равная 11-му префиксу
4) повторяем шаги 2-3 для индексов (i+2),(i+3),...(i+k).

для большей ясности выпишу ещё несколько шагов:
   (i+2), двоичная запись 0001100; из стека ничего не удаляется;
   stack[0] = tree_item[7]
   stack[1] = tree_item[7] + tree_item[11]
   stack[2] = tree_item[7] + tree_item[11] + tree_item[12]  // 12-й префикс
   (i+3), двоичная запись 0001101; из стека удаляется только 1 элемент;
   stack[0] = tree_item[7]
   stack[1] = tree_item[7] + tree_item[11]
   stack[2] = tree_item[7] + tree_item[11] + tree_item[13]  // 13-й префикс
   (i+4), двоичная запись 0001110; из стека ничего не удаляется;
   stack[0] = tree_item[7]
   stack[1] = tree_item[7] + tree_item[11]
   stack[2] = tree_item[7] + tree_item[11] + tree_item[13]
   stack[3] = tree_item[7] + tree_item[11] + tree_item[13] + tree_item[14]  // 14-й
префикс
   ...
все эти операции со стеком очень легко понять если смотреть на картинку, изображающую
дерево Фенвика в 2-мерном виде, примерно как здесь

По части владения Big-O-notation у меня не очень, поэтому не могу точно определить
сложность данного алгоритма. Могу только сказать, что это точно будет намного лучше,
чем O(k*log(i)), когда i достаточно велико.

Пункт 2 - заполнение константным значением элементов из непрерывного диапазона от
i до (i+k) с корректным пересчетом всех затрагиваемых сумм

Здесь у меня получилось очень похоже на то, что описано в ответе участника retorta,
поэтому не буду зря дублировать.
Упомяну только о том, что тут приходилось дополнительно вычислять исходные значения.
value[i] = prefix(i) - prefix(i-1)
Тривиальная реализация требует 2*k обращений к функции вычисления префиксной суммы,
и это легко оптимизировать до (k+1) обращений.
Однако, можно зайти и с другой стороны: неплохо оптимизируется функция, вычисляющая
i-е значение исходного массива, если основываться на том, что каждый чётный элемент
дерева есть значение исходное, а из нечётных каждый второй - равен сумме i-го и (i-1)-го
исходных значений, и т.д...
В общем же случае - опять "выстреливает" подсчет количества единичных битов в младших
разрядах числа, как и по пункту 1 :)

Реализация
Текста получилось уже и так довольно много, поэтом код я решил вынести на github,
надеюсь это не запрещается :)
Закодил в итоге на C++ в MS Visual Studio Community 2015.
В коде отсутствуют некоторые проверки, зато есть простенькие тесты на валидность
и производительность кода.
Отдельно хочу напомнить, что результаты замеров сильно различаются в Debug- и Release-конфигурациях,
в последней выигрыш обычно меньше.
Ссылка на код

Как получить древовидную структуру файловой системы?

Нужно получить список файлов в директориях и поддиректориях в таком виде:
A\B\1 A\B\2 A\B\C\1 A\B\C\2 A\B\C\3 A\B\C\D\1 A\B\C\D\2 A\E\1 A\E\2 ...
Ясно, что нужно использовать рекурсию. Вот, что у меня получилось:
#include #include #include #include #include
struct Tree { bool is_folder; wchar_t data[256]; unsigned children_num; struct Tree* parent; struct Tree* children[1024]; };
void create_tree(struct Tree* node);
int main() { struct Tree Root = { .is_folder = true, .data = L"C:\\Users\\user\\Music", .parent = NULL, .children_num = 0 };
create_tree(&Root);
return 0; }
void create_tree(struct Tree* Root) { WIN32_FIND_DATAW find_file_data; HANDLE file_handel;
/* Файлы и директории ищутся по маске. Т.е. мы находим все файлы подходящие под маску "C:\\Users\\user\\Music\\*". */ wchar_t patch[258]; wcscpy(patch, Root->data); wcscat(patch, L"\\*");
file_handel = FindFirstFileW(patch, &find_file_data); if (file_handel != INVALID_HANDLE_VALUE) { do { /* "." - текущая директория, ".." - директория уровнем выше. */ if (!wcscmp(find_file_data.cFileName, L".") || !wcscmp(find_file_data.cFileName, L"..")) { continue; }
struct Tree* node = malloc(sizeof(*node)); node->children_num = 0; /* Записываем имя элемента. */ wcscpy(node->data, find_file_data.cFileName);
/* Мы нашли директорию. */ if ((find_file_data.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)) { node->is_folder = true; /* По-идее, так как в этой директории могут быть свои файлы и подпапки, нужно обработать и их. */ create_tree(node); } else { node->is_folder = false; }
wprintf(L"%s\\%s%s", Root->data, node->data, node->is_folder ? L"\\
" : L"
");
/* Добавляем елемент в дерево. */ Root->children[Root->children_num] = node; Root->children_num++; } while (FindNextFileW(file_handel, &find_file_data));
FindClose(file_handel); } }
Вот результат работы программы:
C:\Users\user\Music\1.txt C:\Users\user\Music\25-17\ C:\Users\user\Music\2Pac\ C:\Users\user\Music\5'nizza\ C:\Users\user\Music\50 Cent\ C:\Users\user\Music\ACDC\ C:\Users\user\Music\Avicii\ C:\Users\user\Music\Beatles\ C:\Users\user\Music\CENTER\ C:\Users\user\Music\Chuck Berry\ C:\Users\user\Music\Classic\ C:\Users\user\Music\Covers\ C:\Users\user\Music\Cranberries\ C:\Users\user\Music\Crash Test Dummies\ C:\Users\user\Music\Dash\ C:\Users\user\Music\David Bowie\ C:\Users\user\Music\desktop.ini C:\Users\user\Music\Eminem\ C:\Users\user\Music\Imagine Dragons\ C:\Users\user\Music\John Lenon\ C:\Users\user\Music\Kellee Maize\ C:\Users\user\Music\KISS\ C:\Users\user\Music\Kongos\ C:\Users\user\Music\Lil Peep\ C:\Users\user\Music\Lil Pump\ C:\Users\user\Music\Linkin Park\ C:\Users\user\Music\Metallica\ C:\Users\user\Music\MS MR\ C:\Users\user\Music\Nautilus Pompilus\ C:\Users\user\Music\Nirvana\ C:\Users\user\Music\Noize MC\ C:\Users\user\Music\Old Gods of Asgard\ C:\Users\user\Music\One Rupublic\ C:\Users\user\Music\Other\ C:\Users\user\Music\Oxxxymiron\ C:\Users\user\Music\Pink Floyd\ C:\Users\user\Music\Poets of the Fall\ C:\Users\user\Music\Post Malone\ C:\Users\user\Music\Radiohead\ C:\Users\user\Music\Roy Jones Jr\ C:\Users\user\Music\Soundtracks\ C:\Users\user\Music\Sting\ C:\Users\user\Music\The Animals\ C:\Users\user\Music\The Lonely Biscuits\ C:\Users\user\Music\The Shins\ C:\Users\user\Music\The Wanted\ C:\Users\user\Music\Three Days Grace\ C:\Users\user\Music\Twenty One Pilots\ C:\Users\user\Music\VLNY\ C:\Users\user\Music\Yong Jeezy\ C:\Users\user\Music\Zayde Wolf\
Как видно, выводятся директории и файлы только первого уровня. В связи с этим, пару вопросов:
Правильно ли написан алгоритм? Если да, то почему программа работает неверно? Есть ли более лучший способ выполнить эту задачу?

Ответ

У вас в node->data, как я понял лежит только имя файла, без пути к нему. И когда вы вызываете рекурсивно create_tree, то на входе в Root->data видит только имя файла и, конечно, ничего найти не может. В node->data надо класть полный путь от корня. – Mike