Scheme: Չփոփոխվող բինար ծառերի մասին

Շարունակելով իմ նախորդ գրառման բինար որոնման ծառերի թեման, ուզում եմ նույն այդ օրինակով ցույց տալ, թե ինչպես կարելի է ծրագրեր գրել օգտագործելով միայն չփոփոխվող (immutable) տվյալների կառուցվածքներ։ Այս անգամ բինար որոնման ծառերի վարքը ծրագրավորել եմ Scheme լեզվով (այն Lisp ընտանիքի թերևս ամենահայտնի ներկայացուցիչն է)։ Ծառը ներկայացված է ցուցակի տեսքով, որի առաջին տարրը արմատի արժեքն է, երկրորդը՝ ձախ ենթածառն է, իսկ երրորդը՝ աջ ենթածառը։ Տերևներն իրենց աջ ու ձախ ենթածառերի փոխարեն պարունակում են #f արժեքը։ Օրինակ, 23 արժեքով տերևը ներկայանում է (23 #f #f) ցուցակով։ Իսկ ստորև բերված նկարում պատկերված ծառը․

        10
       /  \
      6    20
     / \    \
    4   8    28
            /  \
          23    30
            \
             26

ցուցակային ներկայացմամբ կունենա ահա այսպիսի տեսք․

(10 (6 (4 #f #f) (8 #f #f)) (20 #f (28 (23 #f (26 #f #f)) (30 #f #f))))

(Իհարկե կարելի է տերևները ներկայացնել կա՛մ ատոմներով, կա՛մ մեկ տարր պարունակող ցուցակներով։ Բայց ես ընտրել եմ այս ներկայացումը։)

Նախ ծառում արժեք ավելացնելու օրինակով ցույց տամ փոփոխվող (mutable) և չփոփոխվող (immutable) ծրագրավորելու տարբերությունները։ Ենթադրենք C լեզվով որպես բինար որոնման ծառի հանգույց սահմանված է _node ստրուկտուրան, իր _new_node կոնստրուկտորով.

typedef struct _node {
  int data;
  struct _node* left;
  struct _node* right;
} node;
node* _new_node( int value, node* l, node* r )
{
  node* result = (node*)malloc(sizeof(node));
  result->data = value;
  result->left = l;
  result->right = r;
  return result;
}

Այս տիպի հանգույցներով ծառում արժեք ավելացնելու համար սահմանված է _add_value ռեկուրսիվ ֆունկցիան, որն արգումենտում ստանում է ծառի արմատի ցուցիչի ցուցիչը և ավելացվող արժեքը:

void _add_value( node** tree, int value )
{
  if( *tree == NULL )
    *tree = _new_node( value, NULL, NULL );
  if( value < (*tree)->data )
    _add_value( &((*tree)->left), value );
  if( value > (*tree)->data )
    _add_value( &((*tree)->right), value );
}

Այս ֆունկցիայի համար ծառը փոփոխվող օբյեկտ է։ Այն դեպքում, երբ *tree ցուցիչի արժեքը NULL է, ստեղծվում է նոր հանգույց, և այդ նոր հանգույցի ցուցչիը վերագրվում է *tree ցուցիչին։ Քանի որ tree փոփոխականը ֆունկցիայի արգումենտում հայտարարված է struct _node** tree տեսքով, ապա փոփոխությունը կատարվում է հենց ծառի մեջ։

Չփոփոխվող տվյալներով տարբերակում նոր ստեղծված հանգույցն ավելացվում է ոչ թե ծառի մեջ, այլ տրոհվում է ծառը, ավելացվում է հանգույցը պետք եղած տեղում, ապա ստեղծվում է նոր ծառ։

node* _add_value_i( node* tree, int value )
{
  // եթե ծառը դատարկ է, ապա ստեղծել ու վերադարձնել նոր հանգույց
  if( tree == NULL )
    return _new_node( value, NULL, NULL );

  // տրոհել ծառը արմատի արժեքի, ձախ ու աջ ենթածառերի
  int d = tree->data;
  node* l = tree->left;
  node* r = tree->right;
  // ազատել հանգույցի զբաղեցրած հիշողությունը
  free(tree);
  
  // եթե տրված արժեքը փոքր է արմատի արժեքից, ապա 
  // ապա այն ավելացնել ձախ ենթածառում
  if( value < d )
    l = _add_value_i( l, value );
  // եթե տրված արժեքը մեծ է արմատի արժեքից, ապա 
  // ապա այն ավելացնել աջ ենթածառում
  else if( value > d )
    r = _add_value_i( r, value );
  // ստեղծել նոր արմատ ու վերադարձնել նրա ցուցիչը
  return _new_node( d, l, r );
}

(Պարզ է, որ եթե տրված արժեքը հավասար է արմատի արժեքին, ապա հանգույցը քանդելու կարիք չկա, այլ պետք է այն նույնությամբ վերադարձնել։)

Ծառում արժեք ավելացնող add-value պրոցեդուրայի սահմանումը Scheme լեզվով բերված է ստորև։ Այն համարյա նույնությամբ կրկնում է C լեզվով գրված տարբերակը։

(define add-value
  (lambda (tree val)
    (if tree
        (let ([d (car tree)] [l (cadr tree)] [r (caddr tree)])
          (cond
             [(< val d) (list d (add-value l val) r)]
             [(> val d) (list d l (add-value r val))]
             [else (list d l r)]))
        (list val #f #f))))

Քանի որ Scheme լեզվում ներդրված է աղբի հավաքման մեխանիզմը, այս պրոցեդուրայում կարիք չկա C լեզվի free() ֆունկցիային համարժեք գործողություններ կատարելու։

Ֆունկցիաների սահմանման համար Scheme լեզվում նախաատեսված է նաև (define (function-mane arguments) ...) գրելաձևը։ Բայց ինձ ավելի է դուր գալիս lambda արտահայտությամբ սահմանված (define function-name (lambda (arguments) ...) տարբերակը։ Հաջորդ բոլոր ֆունկցիաները սահմանելիս նույնպես օգտագործել եմ այս վերջին գրելաձևը։

Նաև սահմանեմ մի պրոցեդուրա, որը ծառի մեջ ավելացնում է ոչ միայն մեկ տրված արժեքը, այլ արժեքների ցուցակը։ Սա հնարավորություն կտա հեշտ ու ակնառու եղանակով կառուցել մեծ ծառեր։

(define add-to-tree
  (lambda (tree values)
    (if (empty? values)
        tree
        (add-to-tree (add-value tree (car values)) 
                     (cdr values)))))

Օրինակ, վերևի նկարում պատկերված ծառը կարելի է սահմանել (և սահմանածում համոզվելու համար արտածել) հետևյալ արտահայտություններով.

(define *tr* (add-to-tree #f '(10 6 20 4 8 28 23 30 26)))
(displayln *tr*)

Ծառից որևէ տրված արժեքը պարունակող հանգույցը հեռացնելու համար նույնպես կիրառված է նույն մոտեցումը՝ տրոհվում է ծառը, ապա հետ է հավաքվում, բայց արդեն առանց հեռացվող արժեքի։ Այն դեպքում, երբ ծառը դատարկ չէ, արմատը տրոհվում է d, l և r բաղադրիչների։ Երբ որոնվող արժեքը հավասար է d-ին, դիտարկվում են հետևյալ դեպքերը.

1. Եթե \(r=\varnothing \;\wedge\; l=\varnothing\), ապա վերադարձվում է #f։
2. Եթե \(r=\varnothing \;\vee\; l=\varnothing\), ապա վերադարձվում է համապատասխանաբար ձախ կամ աջ ենթածառը։
3. Եթե \(r\ne\varnothing \;\wedge\; l\ne\varnothing\), ապա հեռացվում է աջ ենթածառի ամենափոքր արժեքը պարունակող հանգույցը, իսկ նրա արժեքը գրվում է արմատի արժեքի փոխարեն։

(define remove-value
  (lambda (tree val)
    (if tree
      (let ([d (car tree)] [l (cadr tree)] [r (caddr tree)])
        (cond
          [(< val d)
           (list d (remove-value l val) r)]
          [(> val d)
           (list d l (remove-value r val))]
          [else
           (cond
             [(and (not l) (not r)) #f]
             [(and l (not r)) l]
             [(and (not l) r) r]
             [else
              (let* ([h (minimum-value r)]
                     [t (remove-value r h)])
                (list h l t))])]))
      #f)))

minimum-value պրոցեդուրան, որ օգտագործված է remove-value պրոցեդուրայում, վերադարձնում է իրեն տրված ծառի ամենափոքր արժեքը, կամ, այլ կերպ ասած, ծառի ամենաձախ հանգույցի արժեքը։

(define minimum-value 
  (lambda (tree)
    (let ([l (cadr tree)])
      (if (not l)
          (car tree)
          (minimum-value l)))))

* * * ՈՒ, պարզապես հետաքրքրության համար սահմանեմ նաև ծառի հետ կատարվող մի քանի գործողություններ։ Առաջինը թող լինի մի պրոցեդուրա, որ պարզում է տրված արժեքի առկայությունը ծառում։

(define contains-value 
  (lambda (tree val)
    (if tree
        (let ([d (car tree)])
          (cond 
            [(= val d) #t]
            [(< val d) (contains-value (cadr tree) val)]
            [(> val d) (contains-value (caddr tree) val)]))
        #f)))

Իսկ inorder-traverse պրոցեդուրան կատարում է ծառի ձախ-արմատ-աջ անցում՝ արմատի արժեքի վրա կիրառելով տրված պրոցեդուրան։

(define inorder-traverse 
  (lambda (tree func)
    (when tree
      (inorder-traverse (cadr tree) func)
      (func (car tree))
      (inorder-traverse (caddr tree) func))))

inorder-modify պրոցեդուրան տրված ծառից կառուցում ու վերադարձնում է մի նոր ծառ, որի հանգույցների արժեքները ձևափոխվել են ըստ տրված գործողության։

(define inorder-modify
  (lambda (tree func)
    (if tree
        (let* ([l (inorder-modify (cadr tree) func)]
               [d (func (car tree))]
               [r (inorder-modify (caddr tree) func)])
          (list d l r))
        #f)))

Այս պրոցեդուրայի աշխատանքի արդյունքը ցուցադրելու համար, օրինակ, տրված ծառից կառուցենք և արտածենք մի նոր ծառ, որի հանգույցների \(x\) արքժեքները փոխարինված են \((x\; \sqrt{x})\) տեսքի զույգերով։

(define *tr* (add-to-tree #f '(10 6 20 4 8 28 23 30 26)))
(displayln *tr*)
(displayln (inorder-modify *tr* (lambda (e) (list e (sqrt e)))))

Ահա նաև արդյունքը.

(10 (6 (4 #f #f) (8 #f #f)) (20 #f (28 (23 #f (26 #f #f)) (30 #f #f))))
((10 3.1622776601683795) ((6 2.449489742783178) ((4 2) #f #f) ((8 2.8284271247461903) #f #f)) ((20 4.47213595499958) #f ((28 5.291502622129181) ((23 4.795831523312719) #f ((26 5.0990195135927845) #f #f)) ((30 5.477225575051661) #f #f))))