#f արժեքը։ Օրինակ, (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-ին, դիտարկվում են հետևյալ դեպքերը.
- Եթե \(r=\varnothing \;\wedge\; l=\varnothing\), ապա վերադարձվում է
#f։ - Եթե \(r=\varnothing \;\vee\; l=\varnothing\), ապա վերադարձվում է համապատասխանաբար ձախ կամ աջ ենթածառը։
- Եթե \(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))))
