Высота бинарного дерева на большом дереве

Question

Высота бинарного дерева на большом дереве

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

Мне удалось получить высоту дерева:

    $depth = 0;
/* @var $db PDO */
$stmt = $db->prepare( "SELECT id FROM wp_members WHERE parent = :parent AND matrix_id = :matrix_id" );

$q = new SplQueue();
$q->push( array( 0, 0 ) );

while (!$q->isEmpty()) {
$cur = $q->pop();

$stmt->bindParam( ':parent', $cur[0] );
$stmt->bindParam( ':matrix_id', $matrix_id );

$stmt->execute();

$ids = $stmt->fetchAll();

if ($cur[1] > $depth) $depth++;

if (count($ids) > 0) $q->add( 0, array( $ids[0]['id'], $cur[1] + 1));
if (count($ids) > 1) $q->add( 0, array( $ids[1]['id'], $cur[1] + 1));
}

return $depth;

PS: matrix_id => давайте назовем идентификатор дерева

Он возвращает правильную высоту дерева, но проблема в том, что база данных имеет более 18 тыс. Узлов, и для получения высоты дерева требуется много времени.

Я хочу знать, что я могу сделать, чтобы решить эту ситуацию? требуется более 60 секунд, чтобы получить высоту дерева.

1

binary-tree mysql php tree

Решение

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

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

Источник

Accepted Answer

Я использовал решение, предложенное @ M0rtiis:

ALTER TABLE `wp_members` ADD `depth` INT UNSIGNED NOT NULL AFTER `parent`;

и я написал скрипт, чтобы путешествовать по дереву, хранящему уровень.

после этого я просто:

$sql = $wpdb->prepare( "SELECT MAX(depth) FROM wp_members WHERE matrix_id = '%d'", $matrix_id );
$height = $wpdb->get_var( $sql );

return $height === NULL ? 0 : $height;

и получил высоту дерева;)

PS: я выбираю решение @ M0rtiis, потому что оно выглядит так просто, а в другой функции мне нужно получить все узлы по указанному уровню.

0