Статьи

Алгоритм недели: поиск самого низкого общего предка

Декабрь 2, 2018

Вступление

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

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

В поисках самого низкого общего предка

 

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

обзор

Допустим, у нас есть дерево (не двоичное!) И два узла из этого дерева. Задача — найти их самого низкого общего предка. Дело в том, что мы мало знаем о том, где они находятся на дереве.

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

Самый низкий общий предок

 

Сначала мы должны найти оба пути от корня до каждого целевого узла. Обратите внимание, что это требует дополнительной памяти! Затем за линейное время мы можем пройти через эти «пути» и просканировать их от корня до узлов. Мы ожидаем, что эти массивы будут равны по крайней мере в их первом элементе (корне). При использовании этого сценария наименьший общий предок является последним равным элементом в обоих массивах.

Самые низкие пути общего предка

Как только мы узнаем пути от корня до узлов, мы можем сравнить их, чтобы найти наименьшего общего предка!

Чтобы увидеть, как этот алгоритм может быть существенно изменен в зависимости от структуры данных, давайте посмотрим на другой пример. Теперь допустим, что у нас есть двоичное дерево поиска (BST). Мы знаем, что в BST все элементы в левом поддереве меньше, чем корень, а все элементы в правом поддереве больше, чем корень. Это верно также для левых и правых поддеревьев.

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

Самый низкий общий в BST

В BST мы сравниваем оба значения с данным узлом (начиная с корня). В случае, если значение узла находится между ними — это самый низкий общий предок. Если нет — мы идем либо налево, либо направо!

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

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

Код

Вот очень простая реализация PHP, показывающая нам эти два алгоритма.

class Tree
{
    public $node = null;
    public $id = null;
    public $parent = null;
    public $children = array();
 
    public function __construct($node, $id = null)
    {
        $this->node = $node;
        $this->id = $id;
    }
 
    public function addChild(Node &$n)
    {
        $n->parent = $this;
        $this->children[] = $n;
    }
 
    /**
     * Returns an element by its id
     * 
     * @param mixed $id
     * @return Node 
     */
    public function search($id)
    {
        if ($this->id == $id) {
            return $this;
        }
 
        $a = false;
 
        // search all the children starting from the left-most
        foreach ($this->children as $child) {
            $a = $child->search($id);
        }
 
        return $a;
    }
 
    /**
     * Finds a path from the root to the 
     * item and returns it as a list
     * 
     * @param mixed $id 
     * @return array
     */
    public function find_path($id, &$path)
    {
        array_push($path, $this->id);
 
        if ($this->id == $id) {
            return 1;
        }
 
        foreach ($this->children as $child)  {
            if (1 == $child->find_path($id, $path)) return 1;
            array_pop($path);
        }
    }
 
    public function __toString()
    {
        return $this->node . ' ' . $this->id . "\n";
    }
}
 
$dom = new Tree('DOM', 'ROOT');
 
$body = new Tree('BODY', 1);
$div1 = new Tree('DIV', 'div-1');
$div2 = new Tree('DIV', 'my-id');
 
$a = new Tree("A", 'some-link');
 
$dom->addChild($body);
$body->addChild($div1);
$body->addChild($div2);
$div2->addChild($a);
 
$path1 = $path2 = array();
$dom->find_path('div-1', $path1);
$dom->find_path('some-link', $path2);

Нахождение самого низкого общего предка в BST

class Tree
{
    public $key;
 
    public $parent  = null;
    public $left    = null;
    public $right   = null;
 
    public function __construct($key) 
    {
        $this->key = $key;
    }
 
    public function insert(Tree $n) 
    {
        if ($this->key < $n->key) {
            if ($this->right == null) {
                // insert
                $this->right = $n;
                $n->parent = $this;
            } else {
                $this->right->insert($n);
            }
        }
        if ($this->key > $n->key) {
            if ($this->left == null) {
                // insert
                $this->left = $n;
                $n->parent = $this;
            } else {
                $this->left->insert($n);
            }
        }
    }
}
 
$t = new Tree(10);
 
$n1 = new Tree(20);
$n2 = new Tree(5);
$n3 = new Tree(7);
$n4 = new Tree(13);
 
$t->insert($n1);
$t->insert($n2);
$t->insert($n3);
 
function find_common($node1, $node2, $tree) 
{
    if ($node1->key < $tree->key && $node2->key > $tree->key) {
        return $tree;
    } else if ($node1->key < $tree->key && $node2->key < $tree->key) {
        find_common($node1, $node2, $tree->left);
    } else if ($node1->key > $tree->key && $node2->key > $tree->key) {
        find_common($node1, $node2, $tree->right);
    }
}
 
$node = find_common($n3, $n4, $t);

заявка

Типичным вариантом использования этого алгоритма является нахождение наименьшего общего предка двух узлов в дереве DOM. Иногда нам просто нужно прикрепить прослушиватель событий к обоим элементам (даже до того, как они подключены к DOM!). Хотя присоединение этого события к «документу» будет работать нормально, все элементы от узлов до корня будут «захватывать» эти события из-за всплытия событий. Таким образом, присоединение события к самому низкому общему предку является лучшим решением.

40
Share: