Common Lisp: Բալանսավորված բինար ծառեր

Գրառումներից մեկում ես ներկայացրեցի բինար որոնման ծառի իրականացումը որպես չփոփոխվող տվյալների կառուցվածք։ Այս անգամ էլ բալանսավորված բինար ծառերը ներկայացնելու համար ընտրել եմ այդ եղանակը, բայց որպես ցուցադրման համար ընտրել եմ Common Lisp լեզուն (Scheme լեզվի փոխարեն)։

ՈՒզում եմ հատկապես շեշտել, որ այս գրառման նպատակը բալանսավորված ծառերի հետ կապված ալգորիթմների ցուցադրությունը չէ։ Միակ նպատակը, որ ես դրել եմ իմ առաջ, դա Common Lisp լեզվով հայալեզու նյութերի ստեղծումն ու տարածումն է։ Նաև նկատելի է, որ բոլոր ներկայացված ալգորիթմներն արդյունավետությամբ չեն առանձնանում։

* * * Սահմանումներ։ Common Lisp լեզվով ներկայացված բինար ծառի հանգույցն ունի երեք անդամ, որոնցից առաջինն ատոմ է և հանդիսանում է հանգույցում գրված արժեքը։ Երկրորդ ու երրորդ տարրերը ցուցակներ են, որոնք ներկայացնում են հանգույցի համապատասխանաբար ձախ և աջ ենթածառերը։ node-p պրեդիկատը ստուգում է, որ տրված ցուցակը ծառի հանգույց է․

(defun node-p (tree)
  (and (= 3 (list-length tree))
       (atom (car tree))
       (listp (cadr tree))
       (listp (caddr tree))))

Ծառի տերևը նույնպես հանգույց է, որի ենթածառերի փոխարեն nil արժեքն է։ leaf-p պրեդիկատը ստուգում է, որ տրված ցուցակը ծառի տերև է․

(defun leaf-p (tree)
  (and (node-p tree)
       (null (cadr tree))
       (null (caddr tree))))

Ծառի բարձրությունը նրա արմատից մինչև տերևներն ընկած ճանապարհներից ամենաերկարի երկարությունն է։ Այդ արժեքը կարելի է հաշվել tree-height ռեկուրսիվ ֆունկցիայով։

(defun tree-height (tree)
  (if tree
      (1+ (max (tree-height (cadr tree))
          (tree-height (caddr tree))))
      0))

Մոտավորապես նույն եղանակով կարելի է հաշվել ծառի բոլոր տարրերի քանակը.

(defun count-nodes (tree)
  (if tree
      (+ 1 (count-nodes (cadr tree))
           (count-nodes (caddr tree)))
      0))

Հանգույցի ձախ (L) ու աջ (R) ենթածառերի բարձրությունների տարբերությունը` h(L)-h(R), կանվանենք տվյալ հանգույցի բանլանսավորվածության գործակից.

(defun balance-factor (tree)
  (- (tree-height (cadr tree))
     (tree-height (caddr tree))))

Այս գրառման համատեքստում կասենք, որ բինար որոնման ծառը բալանսավորված է, երբ նրա յուրաքանչյուր հանգույցի աջ ու ձախ ենթածառերի բարձրությունները տարբերվում են ամենաշատը մեկով՝ բալանսավորվածության գործակիցը -1, 0 կամ 1 է (տես. AVL ծառեր)։ balanced-p պրեդիկատը ռեկուրսիվ եղանակով ստուգում է ամբողջ ծառի բալանսավորվածությունը․

(defun balanced-p (tree)
  (if (leaf-p tree)
      T
      (and (balanced-p (cadr tree)) 
    (balanced-p (caddr tree))
    (member (balance-factor tree) '(-1 0 1)))))

* * * Գործողություններ։ Շատ հետաքրքիր գործողություն է բալանսավորված ծառում նոր արժեքի ավելացումը։ Դրա համար պետք է նախ որոնել և ավելացնել տրված արժեքը ծառում այնպես, ինչպես դա արվում է սովորական բինար որոնման ծառում։ Հետևյալ add-value ֆունկցիան բնար որոնման ծառում ավելացնում է նոր տերև՝ տրված արժեքով։

(defun add-value (tree val)
  (if tree
      (destructuring-bind (d l r)
          tree
        (cond ((< val d) (list d (add-value l val) r))
       ((> val d) (list d l (add-value r val)))
       (t tree)))
      (list val nil nil)))

Այնուհետև հետ գնալ որոնման ճանապարհով և ամեն մի հանգույցում ստուգել բալանսավորվածությունը։ Եթե այն խախտված է, ապա՝ վերականգնել։ Հայտնի է, որ հանգույցում կարող է հանդիպել բալանսավորվածության խախտման չորս դեպքերից որևէ մեկը (իրականում դեպքերը երկուսն են, իսկ մյուս երկուսը պարզապես սիմետրիկ տարբերակներ են)։ Տվյալների կառուցվածքներին նվիրված համարյա բոլոր գրքերում որտեղ պատմվում է AVL ծառերի մասին, այս չորս դեպքերը մանրամասնորեն նկարագրված են։ Ես պարզապես օրինակներով ցույց կտամ, թե ինչպես է ոչ բալանսավորված ծառը ձևափոխվում բալանսավորվածի։

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

	A գագաթը պտտել դեպի աջ։
	Պտտել B գագաթը դեպի ձախ, ապա A գագաթը՝ դեպի աջ։
	A գագաթը պտտել դեպի ձախ։
	Պտտել B գագաթը դեպի աջ, ապա A գագաթը՝ դեպի ձախ։

Դեպի աջ ու ձախ պտույտների գործողությունները ծրագրավորված են համապատասխանաբար rotate-right և rotate-left ֆունկցիաներով։

(defun rotate-right (tree)
  (destructuring-bind ((h l r) (lh ll lr)) 
      (list tree (cadr tree))
    (declare (ignore l))
    (list lh ll (list h lr r))))
(defun rotate-left (tree)
  (destructuring-bind ((h l r) (rh rl rr))
      (list tree (caddr tree))
    (declare (ignore r))
    (list rh (list h l rl) rr)))

Այս երկու ֆունկցիաների համադրմամբ պատրաստել եմ ևս երկու օգնական ֆունկցիաներ։ rotate-right-left ֆունկցիան դեպի աջ պտույտ է կատարում տրված ծառի աջ ենթածառում, ապա դեպի ձախ պտույտ է կատարում ծառի արմատում։ Իսկ rotate-left-right ֆունկցիան դեպի ձախ պտույտ է կատարում տրված ծառի ձախ ենթածառում, ապա դեպի աջ պտույտ է կատարում ծառի արմատում։

(defun rotate-right-left (tree)
  (destructuring-bind (h l r)
      tree
    (rotate-left (list h l (rotate-right r)))))
(defun rotate-left-right (tree)
  (destructuring-bind (h l r)
      tree
    (rotate-right (list h (rotate-left l) r))))

Հիմա պետք է ծրագրավորել մի ֆունկցիա, անվանենք այն add-value-to-avl, որը տրված ծառում կավելացնի տրված արժեքը և միաժամանակ կշտկի խախտված բալանսավորվածության դեպքերը։ Ձևափոխեմ քիչ վերևում բերված add-value ֆունկցիան այնպես, որ այն իր ձախ ու աջ ենթածառերում արժեքի ռեկուրսիվ ավելացման ժամանակ օգտագործի add-value-to-avl ֆունկցիան։ Թող այս նոր ֆունկցիան ստանա add-value-to-bst անունը։

(defun add-value-to-bst (tree val)
  (if tree
      (destructuring-bind (d l r)
          tree
        (cond ((< val d)
               (list d (add-value-to-avl l val) r))
              ((> val d)
               (list d l (add-value-to-avl r val)))
              (t tree)))
      (list val nil nil)))

Հիմնական add-value-to-avl ֆունկցիան տրված tree ծառում ավելացնում է տրված val արժեքը, ը նոր ստեղծված ծառը կապում է nw լեքսիկական փոփոխականին։ Այնուհետև հաշվում է nw ծառի բալանսավորվածության գործակիցը՝ bl։ Բալանսավորվածության խախտման չորս դեպքերը ստուգվում են cond կառուցվածքում, որի առաձին չորս ճյուղերի պայմանները ճշտորեն համընկնում են վերը բերված սխեմաների A գագաթում բալանսավորվածության խախտման դեպքերին։

(defun add-value-to-avl (tree val)
  (let* ((nw (add-value-to-bst tree val))
         (bl (balance-factor nw))
         (dl (caadr nw))
         (dr (caaddr nw)))
    (cond ((and (> bl 1) (< val dl))
            (rotate-right nw))
          ((and (> bl 1) (> val dl))
            (rotate-left-right nw))
          ((and (< bl -1) (< val dr))
            (rotate-right-left nw))
          ((and (< bl -1) (> val dr))
            (rotate-left nw))
          (t nw))))

Եվ վերջում մի մակրոս, որը հնարավորություն է տալիս մեկ տողով կառուցել AVL-ծառ՝ տրված արժեքներով։

(defmacro build-avl-tree (&body elems)
  (let ((result (gensym)))
    `(let ((,result '()))
       (dolist (e ',elems)
        (setf ,result (add-value-to-avl ,result e)))
       ,result)))

Առայժմ այսքանը Common Lisp լեզվով բալանսավորված բինար որոնման ծառերի իրականացման մասին։ * * * Օգտագործված գրականություն։

1. Guy Steele, Common LISP. The Language. Second Edition.
2. Robert Sedgewick, Algorithms in Java, Parts 1-4 (3rd Edition).
3. Robert Sedgewick, Kevin Wayne, Algorithms (4th Edition).
4. Donald Knukth, Art of Computer Programming, Volume 3: Sorting and Searching (2nd Edition).
5. Niklaus Wirth, Algorithms and Data Structures.
6. Alfred Aho, Jeffrey Ullman, John Hopcroft, Data Structures and Algorithms.