90
if (tree != null)
if (data < Convert.ToInt32(tree.data))
Delete(data, ref tree.left);
else
if (data > Convert.ToInt32(tree.data))
Delete(data, ref tree.right);
else {
q = tree;
if (q.right == null)
tree = q.left;
else
if (q.left == null)
tree = q.right;
else
Del(ref q.left);
}
}
Вспомогательная
рекурсивная функция Del вызывается только в слу-
чае, когда удаляемый узел имеет двух сыновей.
Листинг 4.13. Вспомогательная функция удаления
void Del(ref Node r)
{
if (r.right != null)
Del(ref r.right);
else
{
q.data = r.data; q = r; r = r.left;
}
}
21 / 23
91
Эта функция обеспечивает движение вниз до конца самой правой ветви
левого
поддерева удаляемого узла q и
затем заменяет ключ в q соответст-
вующим значением самого правого узла
r этого левого поддерева. После чего
r удаляется.
Отметим, что структура упорядоченного дерева зависит от порядка до-
бавления элементов. Высокие и «тонкие» деревья, подобные представленно-
му на рисунке 4.5 слева, могут иметь высоту порядка числа узлов
N. Добав-
ление элемента в такое дерево или поиск в нем могут потребовать порядка
N
операций,
поэтому такие деревья, представляющие
собой сложную форму
списка, неэффективны для работы. Для эффективного использования древо-
видной структуры желательно
иметь упорядоченные и сбалансированные
деревья, то есть деревья, в которых у каждого узла левое и правое поддерево
содержат примерно одинаковое число узлов. Существуют хорошо известные
алгоритмы балансировки [12], но здесь они не рассматриваются.
Рис. 4.5. Деревья, построенные при различном порядке
поступления элементов
Do'stlaringiz bilan baham: 
