Двоичное дерево, удаление элемента и повторное подключение узла - PullRequest
0 голосов
/ 16 октября 2010

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

alt text Ссылка на изображение для просмотра без изменения размера

Ответы [ 2 ]

0 голосов
/ 16 октября 2010

Да, они есть.Обратите внимание, что вы также можете сделать версию «зеркального отображения» для каждого способа, так что на самом деле это всего 4 способа.

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

0 голосов
/ 16 октября 2010

Два метода выглядят правильно. Первый метод перебалансирует дерево, а второй просто выполняет соединение.

...