Алгоритм двоичного дерева (другой подход)

Question

Алгоритм двоичного дерева (другой подход)

Я пытаюсь разработать алгоритм для двоичного дерева MySQL. Это работает так:

Таблица «сеть»: id_network, parent, child, position

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

У каждого родителя может быть только двое детей, поэтому следующим должен быть его внук и так далее. (Слева направо)

У меня есть свой php-код:

function insertUser($user, $parent) {

$childs = $db -> read('parent =' . $parent); // Return an array with the results from network

$data['parent'] = $parent;
$data['child'] = $user;

if(!$childs[0]) {
$data['position'] = 'left';
$db -> insert($user);
}else{
if(!$childs[1]) {
$data['position'] = 'right';
$db -> insert($user);
}
}
}

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

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

0

algorithm binary-tree mysql php

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

После долгих поисков, изучения и удивительной ссылки, которой поделился @Ryan Vincenti — я нашел решение.

Чтобы сделать что-то подобное, вам придется использовать несколько вещей:

Сила 2 (2, 4, 8, 16, 32, 64 …) для каждого уровня, который вы хотите
Чтобы получить детей слева, вы используете это (2 * n)
Чтобы получить права детей, используйте это (2 * n + 1)

В этом подходе я использовал такую схему БД:

Table "network":

id_network (primary key | auto increment)
id_user (int)
location (int)

Когда вы хотите вставить нового пользователя в дерево, вы проверяете каждый уровень от местоположения родителя (используя степень 2). Например: если мы хотим вставить нового «пользователя» … Допустим, у этого нового «пользователя» есть родитель (его местоположение — 3).

Сначала мы получаем «родительское» местоположение. Скажем, у родителя есть местоположение 3, и у него нет детей. Вы знаете, прежде чем вставить его, что новый «пользователь» будет левый сын «родителя». Но как мы вставим его в дерево? Достаточно просто:

Вы проверяете наличие циклов 2, 4, 8 … И проверяете каждый уровень, если есть все дочерние элементы, если нет, вы берете последнюю позицию детей и добавляете 1+ (вы получили новое местоположение вашего нового пользователя)

Несколько замечаний:

Чтобы получить каждый уровень, вы можете использовать BETWEEN first_level_number AND last_level_number. Чтобы получить свой первый номер, используйте формулу (2 * n), а чтобы получить свой последний, используйте (2 * n + 1)

Я надеюсь, что это помогает другим людям.

0