Сбалансированные деревья, Находится ли максимальное число сбаланси Опции

[FENIX]

Прошу помочь в нелегком деле работы с деревьями
Задание такое:
Определить, находится ли максимальное число сбалансированного дерева глубже, чем минимальное.
Спасибо.

[volvo]

Посмотри вот эти ссылки:

AVL деревья
http://all-net.ru/Articles/IT/Programming/Alg/BinTree/Avl/
http://www.cmc-online.ru/forum/study/?subject=view&msg=3301

Зачем я тебе их привел? Все ОЧЕНЬ просто: Минимальный узел сбалансированного дерева находится в самом ЛЕВОМ листе, а максимальный - в самом ПРАВОМ (я имею в виду AVL деревья, естественно). Так что задача сводится (если дерево уже построено) к проходу по левой и правой ветви и сравнению результатов...

Вот иллюстрация (пример построения дерева взят по первой приведенной ссылке):

Type
  ref = ^node;
  node = record
    Key: integer;
    Left, right: ref;
    Bal: -1..1;
    count: integer;
  end;

procedure search(x: integer; var p: ref; var h: boolean);
var
  p1, p2: ref;
begin
  if p = nil then begin
    new(p);
    h := true;
    with p^ do begin
      key := x;
      count := 1;
      left := nil;
      right := nil;
      bal := 0;
    end
  end
  else
    if x < p^.key then begin
      search(x, p^.left, h);
      if h then
        case p^.bal of
          1 :
            begin
              p^.bal := 0; h := false
            end;

          0 : p^.bal := -1;
          -1:
            begin
              p1:= p^.left;
              if p1^.bal = -1 then begin
                p^.left := p1^.right;
                p1^.right := p;
                p^.bal := 0;
                p := p1
              end
              else begin
                p2 := p1^.right;
                p1^.right := p2^.left;
                p2^.left :=p1;
                p^.left := p2^.right;
                p2^. right := p;
                if p2^.bal =-1 then p^.bal:=1 else p^.bal := 0;
                if p2^.bal = 1 then p1^.bal := -1 else p1^.bal :=0;
                p :=p2;
              end;
              p^.bal := 0;
              h := false;
            end
        end
    end
    else
      if x > p^.key then begin
        search(x, p^.right, h);
        if h then
          case p^.bal of
            -1:
              begin
                p^.bal := 0; h :=false;
              end ;
            0 : p^.bal := 1;
            1 :
              begin
                p1 := p^.right;
                if p1^.bal =1 then begin
                  p^.right := p1^.left;
                  p1^.left := p;
                  p^.bal := 0;
                  p := p1;
                end
                else begin
                  p2 := p1^.left;
                  p1^.left := p2^.right;
                  p2^.right := p1;
                  p^.right := p2^.left;
                  p2^.left := p;
                  if p2^.bal = 1 then p^.bal := -1 else p^.bal:=0;
                  if p2^.bal = -1 then p1^.bal := 1 else p1^.bal := 0;
                  p :=p2;
                end ;
                p^.bal := 0; h:= false;
              end
          end
      end
      else begin
        p^.count := p^.count + 1; h :=false;
      end
end;


const
  n = 7;
  arr: array[1 .. n] of integer =
    (1, 2, 3, 4, 5, 6, 7);

var
  root: ref;
  i: integer;
  h: boolean;

  p: ref;
  cr, cl: integer;
begin
  root := nil;

  for i := 1 to n do
    search(arr[i], root, h);

  { ну и проверяем глубину }
  writeln('right branch');
  p := root; cr := 0;
  while p <> nil do begin
    inc(cr);
    writeln(p^.key);
    p := p^.right
  end;

  writeln('left branch');
  p := root; cl := 0;
  while p <> nil do begin
    inc(cl);
    writeln(p^.key);
    p := p^.left
  end;

  if cl > cr then writeln('min is deeper')
  else if cl < cr then writeln('max is deeper')
       else writeln('deepths are equal');
end.

[FENIX]

Thx, сейчас почитаю.
З.Ы. Всегда ли сбалансированное дерево является деревом поиска?

Сообщение отредактировано: FENIX - 22.04.2005 12:16

[Atos]

Только если оно упорядоченное.