Բինար ծառեր նկարելու մասին

Մի քանի գրառումներիս մեջ ինձ հարկավոր էր պատկերել բինար ծառեր՝ որոշ ալգորիթմների աշխատանքը ցուցադրելու համար։ Սկզբում ես նկարում էի թղթի վրա, ապա, սկաների օգնությամբ թվայնացնելուց հետո, տեղադրում էի գրառման մեջ։ Բայց դա շատ անհարմար եղանակ է, մանավանդ երբ նկարները շատ են ու մատկերում են ալգորիթմի հաջորդական քայլեր։ Հետո որոշեցի գրել ծրագիր, որը ծառ պատկերը կարտածի որևէ գրաֆիկական ֆորմատով։ Postscript, MetaPost և SVG տարբերակներից ընտրեցի վերջինը, որովհետև․ ա) այն շատ պարզ կառուցվածք ունի, գրաֆիկական պրիմիտիվները ներկայացված են XML լեզվով, որում գեներացնելուց հետո կարելի շտկումներ կատարել, բ) նկարները կարելի է դիտել ժամանակակից կամայական բրաուզերի մեջ։

Երբ ինտերնետում փնտրում էի ծառ նկարելու ալգորիթմի մասին տեղեկություններ, գտա բազմաթիվ գրառումներ, սլայդներ, հոդվածներ, որոնցում դիտարկվում էին ծառերը նկարելու առանձնհատկություները (տարածքի օպտիմալ օգտագործում, կատարման արագություն և այլն)։ Բայց քանի որ այդպիսի փիլիսոփայություններն ինձ չեն հետաքրքրում, ընտրեցի ամենապարզ ալգորիթմը, որը, ինչքան հասկացա, առաջարկել է Դ․ Կնուտը։ Այդ ալգորիթմի կառուցվածքը շատ պարզ է.

1.  Let x = 0
2.  Procedure DrawTree( tree, y )
3.    If Left( tree ) <> Nil Then
4.      DrawTree( Left( tree ), y + 1 )
5.    DrawNode( Data( tree, x, y ) )
6.    Let x = x + 1
7.    If Right( tree ) <> Nil Then
8.      DrawTree( Right( tree ), y + 1 )
9.  End

Այստեղ իրականացված է բինար ծառի ձախ-արմատ-աջ տիպի անցում, որտեղ արմատը նկարվում է ընթացիկ մակարդակի` y, իր կարգին համապատասխան՝ x, դիրքում։ Ստորև բերված նկարում կապույտ գծերով նկարված ու համարակալված են ծառը նկարելու ժամանակ x փոփոխականի հաջորդական արժեքները, իսկ կարմիր գծերով՝ y փոփոխականինը (մակարդակները)։

Ես այս սխեման օգտագործել եմ Common Lisp լեզվով draw-tree փաթեթը սահմանելու համար, որը տրամադրում է ծառի ցուցակային ներկայացումից SVG պատկեր գեներացնող draw-as-svg ֆունկցիան և նկարող ալգորիթմի մի քանի պարամետրեր վերասահմանող setup ֆունկցիան։

(defpackage :draw-tree
  (:use :common-lisp)
  (:export :setup
           :draw-as-svg))

(in-package :draw-tree)

Հետո սահմանում եմ չորս պարամետրեր, որոնք օգտագործվում են ծառի հանգույցները և դրանք միացնող գծերը պատկերելու համար։

(defvar *node-radius* 12 "ծառի հանգույցը պատկերող օղակի շառավիղը")
(defvar *font-size* 12 "տառերի չափը")
(defvar *x-scale* 30 "մասշտաբը X-երի առանցքով")
(defvar *y-scale* 30 "մասշտաբը Y-ների առանցքով")

Նկարելուց առաջ կարելի է setup ֆունկցիայի անվանված արգումենտներով փոփոխել այս պարամետրերից մեկը կամ մի քանիսը։

(defun setup (&key (node-radius 12) (font-size 12) (x-scale 30) (y-scale 30))
  (setq *node-radius* node-radius
        *font-size* font-size
        *x-scale* x-scale
        *y-scale* y-scale))

Հետևյալ հաստատունները SVG ֆայլը գեներացնելու ժամանակ օգտագործվելու են որպես format ֆունկցիայի արգումենտներ։

(defconstant +svg-header+
  "<svg xmlns='http://www.w3.org/2000/svg' version='1.1' width='~d' height='~d'>~%")
(defconstant +svg-circle+
  "    <circle cx='~d' cy='~d' r='~d'/>~%")
(defconstant +svg-text+
  "    <text x='~d' y='~d'>~d</text>~%")
(defconstant +svg-line+
  "    <line x1='~d' y1='~d' x2='~d' y2='~d'/>~%")

Նկարելու ալգորիթմն իրականացված է այնպես, որ նախ հավաքվում են ֆայլը գեներացնելու համար անհրաժեշտ տվյալները, ապա դրանք խմբավորված գրվում են նպատակային ֆայլում։ Հետևյալ փոփոխականները ծառայում են միջանկյալ տվյալները պահելու համար։

(defparameter *edges* '() "հանգույցները միացնող գծերը")
(defparameter *nodes* '() "հանգույցները պատկերող շրջանակները")
(defparameter *texts* '() "շրջանակի մեջ գրված տեքստը")
(defparameter *max-x* 0 "ամենամեծ x կոորդինատը")
(defparameter *max-y* 0 "ամենամեծ y կոորդինատը")

node-svg ֆունկցիան ստեղծում է SVG պատկերի երկու թեգեր՝ circle և text, որոնք ներկայացնում են ծառի հանգույցը։ Այս ֆունկցիան հաշվում է նաև ամենամեղ x և y կոորդինատները։

(defun node-svg (xy text)
  (let ((x (* *x-scale* (car xy))) (y (* *y-scale* (cdr xy))))
    (push (format nil +svg-circle+ x y *node-radius*) *nodes*)
    (push (format nil +svg-text+ x (+ 4 y) text) *texts*)
    (setq *max-x* (max *max-x* x) *max-y* (max *max-y* y))))

edge-svg ֆունկցիան ստեղծում է SVG պատկերի line թեգը, որը ներկայացնում է երկու հանգույցները միացնող կողը։

(defun edge-svg (xyb xye)
  (let ((xb (* *x-scale* (car xyb))) (yb (* *y-scale* (cdr xyb)))
        (xe (* *x-scale* (car xye))) (ye (* *y-scale* (cdr xye))))
    (push (format nil +svg-line+ xb yb xe ye) *edges*)))

Եվ վերջապես, կնուտի ալգորիթմը։ calculate-coordinates ֆունկցիան անցնում է ծառի հանգույցներով և ամեն մի հանգույցում գրված տվյալը փոխարինում է (data (x . y)) տեսքի ցուցակի։ Այս ֆունկցիայի աշխատանքի արդյունքում ստացվում է նոր ծառ՝ կոորդինատներով հարստացված հանգույցներով։

(defparameter *pos* 0)

(defun calculate-coordinates (tree level)
  (when tree
    (let ((h (car tree)) (l (cadr tree)) (r (caddr tree)))
      (when l (setf l (calculate-coordinates l (1+ level))))
      (setf h (list (cons *pos* level) h))
      (incf *pos*)
      (when r (setf r (calculate-coordinates r (1+ level))))
      (list h l r))))

generate-svg-edges և generate-svg-nodes ֆունկցիաները նորից անցնում են ծառի վրայով ու խմբավորում են SVG ֆայլը գեներացնելու համար անհրաժեշտ տվյալները։ Երևի կարելի է այս երկու ֆունկցիաները կոմբինացնել calculate-coordinates ֆունկցիայի հետ, որով կնվազեն ալգորիթմի քայլերը, բայց այս պահին ես իրականացրել եմ այս եղանակով։

(defun generate-svg-edges (tree)
  (when tree
    (let ((h (car tree)) (l (cadr tree)) (r (caddr tree)))
      (when l
        (generate-svg-edges l)
        (edge-svg (car h) (caar l)))
      (when r
        (generate-svg-edges r)
        (edge-svg (car h) (caar r))))))

(defun generate-svg-nodes (tree)
  (when tree
    (let ((h (car tree)) (l (cadr tree)) (r (caddr tree)))
      (when l (generate-svg-nodes l))
      (node-svg (car h) (cadr h))
      (when r (generate-svg-nodes r)))))

draw-as-svg ֆունկցիան նախապատրաստում է ժամանակավոր փոփոխականները, հաշվարկում է ծառի գագաթների կոորդինատները, ապա հավաքած ինֆորմացիան արտածում է տրված անունով ֆայլի մեջ։

(defun draw-as-svg (tree out-file)
  (setq *pos* 1
        *edges* '()
        *nodes* '()
        *texts* '())
  (let ((antree (calculate-coordinates tree 1)))
        (generate-svg-edges antree)
        (generate-svg-nodes antree))
    (with-open-file (osvg out-file :direction :output :if-exists :supersede)
      (format osvg +svg-header+ (+ *max-x* *x-scale*) (+ *max-y* *y-scale*))
      (format osvg "  <g fill='white' stroke='black' stroke-width='2'>~%")
      (dolist (e *edges*) (princ e osvg))
      (dolist (n *nodes*) (princ n osvg))
      (format osvg "  </g>~%~%")
      (format osvg "  <g text-anchor='middle' font-size='~d' stroke-width='0'>~%" *font-size*)
      (dolist (x *texts*) (princ x osvg))
      (format osvg "  </g>~%")
      (format osvg "</svg>~%")))

* * * Վերջում մի օրինակ. պատահական տվյալներից կառուցված AVL ծառ՝ նկարված այս ծրագրով.

Նախապատվություններով հերթի իրականացումը

Հերթի այն տեսակը, որտեղ տարրերը կարող են ավելացվել կամայականորեն, բայց կարող են հեռացվել միայն ըստ նրանց մեջ սահմանված կարգի, կոչվում է նախապատվություններով հերթ։ Օրինակ, եթե որպես հերթի մեջ ավելացվող տարրեր դիտարկվում են թվերը, իսկ թվերի մեջ սահմանված կարգ է հանդիսանում "\(<\)" (փոքր է) գործողությունը, ապա ամեն անգամ հերթից որևէ տարր պահանջելով կստանանք այնտեղ եղած տարրերից ամենափոքրը (նույնը կարելի է ասել, իհարկե, "\(>\)" (մեծ է) գործողության նկատմամբ)։ Մեկ այլ օրինակում, եթե հերթի որպես տարրեր դիտարկվում են բառեր (տեքստ), իսկ որպես կարգի հարաբերությունը սահմանված է բառի երկարության նկատմամբ՝ \(|w_1| < |w_2|\), ապա ամեն անգամ հերթից տարր պահանջելով կստանանք այդ պահին հերթում մնացած ամենակարճ բառը։

Նախապատվություններով հերթն իրականացվում է մի տվյալների կառուցվածքի հիման վրա, որին գրականության մեջ տրված է heap (ռուս. куча) անունը։ Սա մի ծառ է (տվյալ դեպքում՝ բինար ծառ), որի ամեն մի հանգույցի արժեքն ավելի փոքր է (մեծ է) իր ժառանգների արժեքներից։ Բնականաբար ծառի արմատում գտնվում է ամենափոքր (կամ ամենամեծ) տարրը։ Այս ծառը նաև լրիվ (բինար) ծառ է։

Դասախոսությունների կամ այլ խոսակցությունների ժամանակ (քանի որ հայերեն գրականություն գործնականում չկա) ես հանդիպել եմ նաև heap տերմինի կույտ բառացի և, իմ կարծիքով, անհաջող թարգմանությանը։ Հանդիպել եմ նաև բուրգ տերմինը, և այս գրառման մեջ կօգտագործեմ հենց այս տարբերակը։

Ենթադրենք արդեն իրականացրել ենք Heap<T> շաբլոնային դասը որն ունի Add(T value) մեթոդը՝ հերթում տարրեր ավելացնելու համար, և T TakeMinimal() մեթոդը՝ հերթից ամենաբարձր նախապատվություն (տվյալ դեպքում՝ ամենափոքր արժեք) ունեցող տարրը հեռացնելու համար։ Ինչպես նաև նախատեսված է արժեքավորող ցուցակով կոնստրուկտոր։ Ստեղծենք int տիպի արժեքների հերթ և նրանում ավելացնենք {32, 9, 23, 14, 17, 2, 20, 17, 6} թվերը։

  Heap h {32, 9, 23, 14, 17, 2, 20, 17, 6};

Այս թվերով կառուցված ծառը կունենա ստորև բերված նկարի տեսքը, որում երևում է, որ ամեն մի հանգույցի արժեք ավելի փոքր է, քան իր ժառանգների արժեքները։ * * * Հիմա ներկայացնեմ իրականացումը։ Սովորաբար բուրգն իրականացվում է ոչ թե ցուցիչների վրա հիմնված դինամիկ կառուցվածքների միջոցով, այլ սովորական ինդեքսավորված վեկտորներով։ Բուրգի արմատի արժեքը գրվում է վեկտորի զրո ինդեքսով բջջում։ Իսկ ամեն մի k ինդեքսով հանգույցի աջ (R) ու ձախ (L) ժառանգների ինդեքսները հաշվվում են L=2k+1 և R=2k+2 բանաձևերով։ Օրինակ, նկարում բերված ծառը վեկտորի տեսքով կներկայանա հետևյալ կերպ.

 Value | 2 | 6 | 9 | 14| 17| 23| 20| 32| 17
-------+---+---+---+---+---+---+---+---+---
 Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8

Այս ներկայացումն արդյունավետ է շնորհիվ այն բանի, որ բուրգը լրիվ ծառ է և ամենաներքևի մակարդակը լրացված է ձախից աջ։
Եվ այսպես, C++11 լեզվով սահմանում եմ Heap դասը։ Այս դասի size ստատիկ հաստատունը ցույց է տալիս տարրերի վեկտորի նախնական չափը։ capacity դաշտը ցույց է տալիս բուրգի տարողությունը, իսկ count դաշտը ցույց է տալիս տվյալ պահին առկա տարրերի քանակը։ Տարրերը պահվում են դինամիկ ստեղծվող data զանգվածում։

template
class Heap {
protected:
  static const int size = 32;

  unsigned int capacity;
  unsigned int count;
  T* data;

Դասի կոնստրուկտորներից մեկը պարզապես ստեղծում է դատարկ օբյեկտ, իսկ մյուսը բուրգի մեջ է ավելացնում արժեքավորող ցուցակով տրված տարրերը։ Իսկ դեստրուկտորը պարզապես ազատում է տարրերի զանգվածի զբաղեցրած հիշողությունը։

public:
  Heap()
    : capacity(size), count(0)
  {
    data = new T[capacity];
  }
  
  Heap( std::initializer_list<T> elems )
    : Heap()
  {
    for( auto e : elems )
      Add( e );
  }
    
  virtual ~Heap()
  {
    delete[] data;
  }

Նախապատվություններով հերթում նոր տարր ավելացնելիս նախ այն ավելացվում է զանգված վերջում, ապա, heapify գործողության կիրառմամբ զանգվածի տարրերը վերադասավորվում են այնպես, որ շարունակեն բավարարել բուրգի վերը նշված պահանջներին։ Եթե հերթական տարրն ավելացնելուց հետո պարզվում է, որ զանգվածի տեղերը սպառվել են (count == capacity), ապա զանգվածի երկարությունը կրկնապատկվում է։

  void Add( T val )
  {
    data[count] = val;
    ++count;
    heapify();
    if( count == capacity )
      enlarge();
  }

heapify գործողության ժամանակ տարրը տեղաշարժվում է դեպի ձախ այնքան ժամանակ, քանի դեռ այն փոքր է ծնոսի արժեքից։ Ի դեպ, տրված k ինդեքսով տարրի ծնողի ինդեքսը որոշվում է (k - 1)/2 բանաձևով։

  void heapify()
  {
    unsigned int i(count - 1);
    unsigned int k((i - 1) / 2);
    while( i > 0 && data[i] < data[k] ) {
      auto temp(data[i]);
      data[i] = data[k];
      data[k] = temp;
      i = k;
      k = (i - 1) / 2;
    }
  }

Զանգվածն ընդլայնող enlarge մեթոդը համակարգից պահանջում է գոյություն ունեցողից երկու անգամ մեծ հիշողություն, տարրերն արտագրում է այդ նոր տիրույթում և համակարգին է վերադարձնում հին տարածքը։

  void enlarge()
  {
    T* temp(data);
    capacity *= 2;
    data = new T[capacity];
    for( unsigned int i = 0; i < count; ++i )
      data[i] = temp[i];
    delete[] temp;
  }

Նախապատվություններով հերթից ամենաբարձր նախապատվություն ունեցող տարրը հեռացնելու համար գրված է TakeMinimal մեթոդը։ Այն հեռացնում է բուրգի գագաթի տարրը, ապա մյուս տարրերը վերադասավորում է այնպես, որ նրանք շարունակեն բավարարել բուրգի պայմաններին և վերադարձնում է հեռացված արժեքը։ Այս մեթոդում վերադասավորման համար օգտագործված է heapify մեթոդը։ Բայց գաղափարն այն է, որ ամենաներքևի մակարդակի ամենաաջ տարրը տեղափոխվում է բուրգի գագաթը, ապա այն փոխատեղվում է իր ժառանգներից ամենափոքրի հետ այնքան ժամանակ, քանի դեռ չի հասել իր իսկական տեղին։

  T TakeMinimal()
  {
    auto result(data[0]);
    data[0] = data[--count];
    heapify();
    if( count * 2 == capacity )
      reduce();
    return result;
  }

TakeMinimal մեթոդով որևէ տարր հեռացնելուց հետո ստգուգվում է տարրերի զանգվածի վիճակը։ Եթե զանգվածի տարողությունը երկու անգամ մեծ է տարրերի իրական քանակից՝ count * 2 == capacity, ապա զանգվածի չափը կրճատվում է երկու անգամ։ reduce մեթոդը ստեղծում է երկու անգամ փոքր տիրույթ, տարրերն արտագրում է նրա մեջ, ապա համակարգին է վերադարձնում ին մեծ տիրույթը։

  void reduce()
  {
    if( capacity > size ) {
      capacity /= 2;
      auto temp(data);
      data = new T[capacity];
      for( unsigned int i = 0; i < count; ++i )
        data[i] = temp[i];
      delete[] temp;
    }
  }
};

* * * Առայժմ այսքանը նախապատվություններով հերթերի մասին։ Չնայած որ տեքստը մի քիչ կցկտուր ստացվեց, բայց, կարծում եմ, որ ընդհանուր առմամբ այն հասկանալի է։