История изменений
Исправление pathfinder, (текущая версия) :
А может построить нечто вроде «дерева групп». Все узлы делятся на группы. В группе есть ограничение на максимальное количество участников. Группа - это структура со счетчиком участником, указателем на узел-родитель группы и указателем на группу предков. Пускай корневой узел создает первую группу и туда добавляются все его потомки первой линии, потом второй, потом третьей и так до тех пор, пока не будет превышен предел участников. Узлы-потомки, которые не смогли влезть в группу, создают свою, занося в структуру своей группы указатель на группу предков. И так всё продолжается по-новой.
В итоге получается дерево групп. Все участники одной группы имеют общего предка - создателя группы. Это необязательно ближайший общий предок, но довольно близкий. Потом ищем общего предка внутри этой группы.
Если в группе 1000 узлов. То дерево групп будет в 1000 раз меньше, чем исходное дерево. Если исходное дерево узлов сильно не сбалансировано, то порожденное дерево групп по идее должно быть более сбалансированным.
В самом дереве стоит таже задача - найти группу - общего предка. Т.е. можно повторить прием. Сделать дерево групп деревьев групп.
Исправление pathfinder, :
А может построить нечто вроде «дерева групп». Все узлы делятся на группы. В группе есть ограничение на максимальное количество участников. Группа - это структура со счетчиком участником, указателем на узел-родитель группы и указателем на группу предков. Пускай корневой узел создает первую группу и туда добавляются все его потомки первой линии, потом второй, потом третьей и так до тех пор, пока не будет превышен предел участников. Узлы-потомки, которые не смогли влезть в группу, создают свою, занося в структуру своей группы указатель на группу предков. И так всё продолжается по-новой.
В итоге получается дерево групп. Все участники одной группы имеют общего предка - создателя группы. Это необязательно ближайший общий предок, но довольно близкий. Потом ищем общего предка внутри этой группы.
Если в группе 1000 узлов. То дерево групп будет содержать в 1000 раз меньше узлов, чем исходное дерево. Если исходное дерево узлов сильно не сбалансировано, то порожденное дерево групп по идее должно быть более сбалансированным.
В самом дереве стоит таже задача - найти группу - общего предка. Т.е. можно повторить прием. Сделать дерево групп деревьев групп.
Исходная версия pathfinder, :
А может построить нечто вроде «дерева групп». Все узлы делятся на группы. В группе есть ограничение на максимальное количество участников. Группа - это структура со счетчиком участником, указателем на узел-родитель группы и указателем на группу предков. Пускай корневой узел создает первую группу и туда добавляются все его потомки первой линии, потом второй, потом третьей и так до тех пор, пока не будет превышен предел участников. Узлы-потомки, которые не смогли влезть в группу, создают свою, занося в структуру своей группы указатель на группу предков. И так всё продолжается по-новой.
В итоге получается дерево групп. Все участники одной группы имеют общего предка - создателя группы. Это необязательно ближайший общий предок, но довольно близкий. Потом ищем общего предка внутри этой группы.
Если в группе 1000 узлов. То дерево групп будет содержать в 1000 раз меньше узлов. Если исходное дерево узлов сильно не сбалансировано, то порожденное дерево групп по идее должно быть более сбалансированным.
В самом дереве стоит таже задача - найти группу - общего предка. Т.е. можно повторить прием. Сделать дерево групп деревьев групп.