Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

Поиск узла в дереве

Поиск узла в дереве (в том числе в двоичное дереве понска) может выполняться по такому же принципу, что и просмотр де- рева, но в этом случае теряется эффективность этой структуры данных, а поиск фактически приобретает линейный характер. Qля сохранения эффективности поиска следует или использовать pe- курсивную функцию, аналогичную показанным выше inorde г, pr eordeг и т.п., преобразовав её так, чтобы её работа (и все pe- курсивные вызовы) завершалась после нахождения требуемых данных, или отказаться от рекурсии.

Рекурсивная функция поиска.
void poisk1(node* r, int skey, node*& f) if (г == NULL f) return;
if (r->key == skey)
{ f = r; return; } // Выход, если нашли else
if (skey < r->key)
poisk1(r->left, skey, f); else
poisk1(r->right, skey, f);
Третий аргумент пode * s I — одновременно узел, в кото- ром находятся найденные данные, и признак успеха поиска. Пе- ред вызовом этой функции соответствующий фактический аргу- мент должен быть равен нулю.

126
PeKypcnBHhIe npouepypsI ii QyHKuHii, npii Bcex cx pOCTOHHCT- BiIX, o6aap£tloT OQHHM Cé]3h 3HhIM HéQOGTlITKOM — BO3MOWHOCTI›IO Hé]3éHOJIHéHHIf CTéKI1 BO3B]3I1TI1 H3 HonnporpaMM H]3H 6oJIsIIIOM KOJIH- uéCTBé pexypcnBHhIX BhI3OBOB (II CTO MOWéT H]3OH3O TH H]3H 6ous-

IIIOM ]3iI3Mé]3e cTpyKTypsI plIHHI›IX), nO3ToMy pacCMOT]3HM ppyroii Bl-
]3HI1HT ]3é8JIH3I1IJHH HOHGKI1 — ncnous3OBllHHe HepeKypc BHOii npoue-
pypsI.
HepexypcHBHas yHKuHs Ht3HCK£t B @BOHUHOM ,IJé]3éBé His II3I›IKé
IlCKdJlh.
function search tree(skey:integer; var tree, fnode: ptr) :boolean;
var
p, q: ptr; b: boolean;
begin
b false;
p tree;
if tree <> nil then repeat

q P(

if p’.key = skey then
b true
else begin
if skey < p’.key then p := p’.left
else
p := p’.right
end
until (b) or (p = nil); search tree := b;
fnode q; end;

AHi1JI€1FHUHas §iyHKuHII Hit II3hIKé FH+ .

void poisk2(node* r, int skey, node*& f) while (r != NULL && f == NULL)

127
if (r->key == skey)
{ f = г; return; } // Выход, если нашли else
if (skey < r— >key)
г = r— >left; else
г = r->right;

Эта функция практически идентична по общей структуре предыдущей рекурсивной функции. В этом примере виден и спо- соб преобразования рекурсивных функций в нерекурсивные: ре- курсивный вызов, находящийся в конце процедуры («хвостовая» рекурсия) заменяется на цикл (в этом примере вием), а рекурсивный вызов, размещённый где—либо до конца процедуры, заменяется на оператор if .

Длительность поиска зависит от структуры дерева. Для сба— лансированного дерева (изображено на рисунке 10.8) поиск ана- логичен двоичному — то есть нужно просмотреть не более ^lO_g2^N узлов.

f

Рис. 10.8 — Сбалансированное дерево

Для вырожденного дерева (изображено на рисунке 10.9) по- иск аналогичен поиску в односвязном списке — в среднем нужно просмотреть половину узлов, а в худшем случае — все N узлов.

128