часть вторая алгоритмы

 

структуры

списки
  • односвязный список
  • реверсирование односвязного списка
  • skip list
  • стеки
  • стек курильщика
  • стек здорового человека
  • хеши
  • таблица с прямой адресацией
  • таблица с цепочками
  • универсальная таблица
  • кучи
  • куча на массиве
  • leftist heap на бинарном дереве
  • skew heap
  • binomial heap на списке бинарных деревьев
  • деревья
  • бинарное дерево
  • AVL дерево
  • splay дерево
  • черно-красное дерево

  • типы в "С" на самом деле не для программиста, а для компилятора. основная задача тамошней системы типов - сделать ваш код быстрее

    Kevin Mahoney

    сишная структура как произведение типов, и юнион - как сумма типов

    а также перечислимый тип, как частный случай суммы
    #include <stdio.h>
    
    #define NUM 10 
    
    int
    main (int argc , char* argv[] , char* env[])
    {
      enum color { RED = 1 , GREEN = 3 , YELLOW = 2 , BLACK = NUM } ; 
    
      union 
      { char* message
      ; int   count 
      ; } x ;
    
      struct 
      { int          field1 // signed int
      ; char*        field2 
      ; float        field3 
      ; double       field4 
      ; long double  field5 
      ; long         field6  // long int
      ; short        field7  // short int
      ; signed int   field8  // int
      ; unsigned int field9 
      ; } z ;
    
      x.message = "hello world!" ; puts (x.message) ;
    
      x.count = 42 ; printf ("%d\n" , x.count) ;
    
      x.count  = GREEN ; printf ("%d\n" , x.count) ;
      
      z.field1 = 0    ; z.field2 = "aaa" ; z.field3 = 34.5 ; 
      z.field4 = 45.6 ; z.field5 = 34.8  ; z.field6 = 1    ; 
      z.field7 = 2    ; z.field8 = 8     ; z.field9 = 1    ; 
    
      printf ("%f\n" , z.field4) ;
    
      return 0 ;
    }
    
    // gcc hello.c && valgrind --leak-check=full  ./a.out
    

    даже уже только с этими структурами данных можно свернуть горы

    списки

    "C" не имеет ссылок - только указатели. так что "C" не имеет механизма "pass-by-ref". но вы можете передавать указатель и насладиться

    карандашная надпись на обложке BlueBible

    односвязный список

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct elem Node ;
    
    struct elem { int val
                ; Node* next
                ; } ;
    
    int lookup (int) , insert (int) , delete (int)  ;
    
    Node *p ;               // pointer to the list
    Node *r ;               // pointer to the current position for insertion
    #define LEN 256         // initial lenght of the list
    
    int
    main (int argc , char** argv , char** envp)
    {
      r = p = malloc (LEN * sizeof (Node)) ;
      p->val = 0 ; p->next = NULL ;
    
      // some stuff here 
    
      free (p) ;
      return 0 ;
    }
    
    int 
    lookup (int val) 
    {
      Node* s = p ;
    
      while (s->val != val && s->next) s = s->next ; 
    
      if (s->val == val) return val ;
      else return 0 ;
    } ;
    
    int 
    insert (int val) 
    {
      if (r == p + LEN - 1) { printf ("overflow\n") ; return 1 ; } ;
    
      r->val = val ; r->next = NULL ;
      if (r != p) (r - 1)->next = r ;
      r += 1 ;
    
      return 0 ;
    } ;
    
    int 
    delete (int val) 
    {
      Node* s = p ;
    
      while (s->val != val && s->next) s = s->next ; 
    
      if (s->next && s->val == val)                // start gc
      {
        while (s->next) { s->val = s->next->val ; s += 1 ; } ;
        r = s ;
        return 0 ;
      }
      else if (s->next == NULL && s->val == val)  // just reset pointer to succ elem
      {
        if (s != p) (s - 1)->next = NULL ;
        r = s ;
        return 0 ;
      }
    
      else return 1;  // not found
    } ;
    

    реверсирование односвязного списка

    как задача на собеседовании

    #include <stdio.h>
    
    typedef struct elem Node ; struct elem { int val ; Node* next ; } ;
    
    void prn (Node*), rreverse (Node*), ireverse (Node*), trreverse (Node*, Node*) ;
    
    int 
    main (int argc, char** argv, char** envp)
    {
      Node a, b, c, d ;
    
      a.val = 10 ; a.next = &b ;
      b.val = 20 ; b.next = &c ;
      c.val = 30 ; c.next = &d ;
      d.val = 40 ; d.next = NULL ;
    
      // debug printing:
      prn (&a) ; rreverse (&a) ; prn (&d) ; ireverse (&d) ; prn (&a) ; trreverse (NULL, &a) ; prn (&d) ;
    
      return 0 ;
    }
    
    
    
    // recursive way:
    
    void 
    rreverse (Node* p) 
    {
      Node* r = p->next ;  // r - pointer to my current tail
      if (!r) return ;     // if no tail - r points on former last elem. it will not be changed anymore
      rreverse (r) ;
      p->next->next = p ;  // change pointer of my former succ to point on me now
      p->next = NULL ;     // change my new succ to NULL, but NULL will be buble up continiously
      p = r ;              // change pointer to point on former last elem (see line 02)
                           // any time it will be different p, but just the same r
                           // at last p will be the global pointer
    }
    // NB: no tail recursion here, so the stack will grow up
    
    
    
    // tail recursive way:
    
    void 
    trreverse (Node* a, Node* p) 
    {
      Node* r = p->next ;
      p->next = a ;
      if (r) trreverse (p, r) ; 
    }
    // if your compiler is TOC - you are win
    
    
    
    // iterative way:
    
    void 
    ireverse (Node* p) 
    {
      Node* iter ;
      Node* temp = NULL ;       // the first elem will put it in the next pointer
      Node* work = p ;          // for while loop only - pointer to the first elem
    
      while (work)             //           my pointer here
      {
        iter = work->next ;     // save      where to move on the next step
        work->next = temp ;     // rewrite   my own next-pointer
        temp = work ;           // remember  my adr 
        work = iter ;           // for while loop only - pointer to the next elem
      }
    
      p = temp ;                // change global pointer to former last elem 
    }
    
    
    // for debug output only
    void 
    prn (Node* h) 
    {
      while (h) { printf ("--> %i\t", h->val) ; h = h->next ; }
      printf ("\n") ;
    }
    

    skip list

    #include <stdio.h>
    #include <stdlib.h>
    
    #define SL_SIZE 17 
    
    typedef struct elem Node ; struct elem { int val ; Node* next ; } ;
    Node* p ; Node* r ;
    
    typedef struct supelem Node1 ; struct supelem { int val ; Node1* next ; Node* down ; } ;
    Node1* p1 ; Node1* r1 ;
    
    int minval () ;
    int coin (int s) { srandom (s) ; int x = random () ; return 1 & x ; }
    
    int 
    main (int argc, char** argv, char** envp)
    {
      // generating skip-list structure with size (SL_SIZE)
      p = malloc (SL_SIZE * sizeof (Node)) ;                        // for the first-level list
      p->next = p ;                                                 // create null-sentinel
      r = p + 1 ;                                                   // current pos 
      p1 = malloc ((3 * SL_SIZE / 4) * sizeof (Node1)) ;            // for the second-level list
      p1->next = p1 ;                                               // create null-sentinel
      r1 = p1 + 1 ;                                                 // current pos 
    
      // some stuff here
    
      free (p) ; free (p1) ; return 0 ;
    }
    
    
    int 
    insert1 (Node* x) 
    {
      if (r1 - p1 > (3 * SL_SIZE / 4)) { return 1; } ;
    
      Node1 y ; y.val = x->val ; y.down = x ;
    
      // the first element insertion
      if (r1 == p1) { y.next = r1 ; *r1 = y ; r1 += 1 ; return 0 ; }
    
      Node1 *s = p1 ;  // for list traversing 
      Node1 *t = p1 ; 
    
      // all except the first and the last elements insertion
      while (s != s->next) 
      {
        if (s->next->val > x->val)
        {
          y.next = s->next ;
          s->next = r1 ;
          *r1 = y ; r1 += 1 ; return 0 ;
        }
        t = s ;       // save as previos element pointer
        s = s->next ; // move to the next element
      };
    
      // the last element insertion
      if   (s->val < x->val) { s->next = r1 ; y.next  = r1 ; }
      else { y.next  = s ; t->next = r1 ; }
    
      *r1 = y ; r1 += 1 ; return 0 ;
    }
    
    
    int 
    delete (int x) 
    {
      if (x < minval ()) return 1 ;
    
      // at first in low-level list:
      Node *s = p ;  // for list traversing 
      Node *t = p ;  //
    
      while (s != s->next) 
      {
        if (s->val == x) { t->next = s->next ; return 0 ; }
        t = s; s = s->next ; // save previos pointer and increment 
      }
      if (s->val == x) { t->next = t->next ; }
    
      // now in high-level list:
      Node1 *s1 = p1 ;  // for list traversing 
      Node1 *t1 = p1 ;
    
      while (s1 != s1->next) 
      {
        if (s1->val == x) { t1->next = s1->next ; return 0 ; }
        t1 = s1 ; s1 = s1->next ; // save previos pointer and increment 
      }
      if (s1->val == x) { t1->next = t1->next ; return 0 ; }
    
      return 1 ;
    }
    
    
    int 
    lookup (int x) 
    {
      if (r == p + 1) return 0 ; 
      if (x < minval ()) return 0 ;  
    
      Node1* s1 = p1 ;
      Node1* t1 = p1 ;
      while (s1->next->val < x && s1->next != s1) s1 = s1->next ; 
      if (s1->val == x) return 1 ; 
      Node* s = s1->down ;
      while (s->next != s) 
      {
        if (s->val == x) return 1 ; 
        s = s->next ; 
      } ;
    
      return 0 ;
    }
    
    
    int minval () { return p->next->val ; }
    
    
    int 
    maxval () 
    {
      if (r == p + 1) return r->val ; 
      Node1* s1 = p1 ;
      while (s1->next != s1) s1 = s1->next ; 
      Node* s = s1->down;
      while (s->next != s) s = s->next ;
    
      return s->val ;
    }
    
    
    int 
    insert (int x) 
    {
      if (r - p > SL_SIZE) return 1 ;
    
      Node y ; y.val = x ;
    
      // the first element insertion
      if (r == p) 
      {
        if (!x) return 1 ;
        else
        {
          y.next = r ; *r = y ;
          if (coin (x)) insert1 (r) ;
          r += 1 ; return 0 ;
        }
      }
    
      // the next element insertion
      Node *s = p ;  // for list traversing 
      Node *t = p ;
    
      // all except the first and the last elements insertion
      while (s != s->next) 
      {
        if (s->next->val > x) 
        {
          if (s->val != x) 
          {
            y.next = s->next ; s->next = r ; *r = y ; 
            if (coin (x)) insert1 (r) ;
            r += 1 ;  return 0 ;
          }
          else return 1 ; 
        };
        t = s ;       // save as previos element pointer
        s = s->next ; // move to the next element
      };
    
      // the last element insertion
      if (s->val  < x) { s->next = r ; y.next  = r ; }
      else if (s->val == x) return 1 ; 
      else { y.next  = s ; t->next = r ; }
    
      *r = y ; r += 1 ; return 0 ;
    }
    

     

    стек

      
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    #define LEN 128
    
    int isEmpty (void) ;
    int push    (int) ;
    int pull    (void) ;
    
    int* p ;    // stack pointer
    int* r ;    // current position
    
    int
    main (int argc , char** argv , char** envp)
    {
      p = r = malloc (LEN  * sizeof (int)) ;
    
      // assert (isEmpty ()) ;
      assert (push (100)) ; assert (isEmpty()) ; assert (push (200)) ;
      int x = pull () ; assert (200 == x) ; assert (isEmpty ()) ;
      x = pull () ; assert (100 == x) ;
      // assert (pull ()) ;
    
      free (p) ;
      return 0 ;
    }
    
    int
    isEmpty (void)
    {
      if (p == r) return 0 ; else return 1 ;
    } ;
    
    int
    push (int x)
    {
      if (r == p + LEN - 1) { puts ("overflow\t") ; }
      else { r = r + 1 ; *r = x ; } ;
      return r - p ;  
    } ;
    
    int
    pull ()
    {
      int x ;
      if (r == p) { puts ("empty\t") ; return r - p ; }
      else { x = *r ; r = r - 1 ; return x ; }
    } ;
    

    ocaml (fm Okasaki "PFDS"):

    module type Stack = 
    sig
      type t
      type a 
    
      val empty : a 
      val isEmpty : a -> bool
      val push : t * a -> a 
      val pull : a -> t 
    end
    
    module C : Stack = 
    struct
      type t = int
      type a = Nil | Cons of t * a
    
      let empty = Nil
      let isEmpty xs = match xs with | Nil -> true | _ -> false
      let push (x , s) = Cons (x , s)
      let pull s = match s with Nil -> 0 | Cons (x , s) -> x
    end
    

     

    хеш-таблицы

    указатели "С" страдают тем, что их можно присвоить переменной с временем жизни большим, чем запись активации функции, где эта переменная находится - и здравствуй segfault

    Антон Москаль

    таблица с прямой адресацией

    #include <stdio.h>
    #include <stdlib.h>
    
    #define KEY_NUM 16                             // size
    #define ALL_BUSY ((1 << KEY_NUM) - 1)          // for flags
    
    typedef struct vals Vals;
    struct vals { int key; int val; };
    
    int  ukeys[KEY_NUM];       // keyspace
    Vals tvals[KEY_NUM];       // table with key-value objects
    unsigned int flags = 0;    // busy|free keystatus
    
    Vals lookup (int) ;
    int  insert (int) , delete (int) ;
    
    
    int 
    main (int argc, char** argv, char** envp) 
    {
      // initialize keyspace with sequence from 0 to KEY_NUM - 1:
      int i = 0 ; while (i < KEY_NUM) { ukeys[i] = i ; i++ ; }
    
      return 0 ;
    }
    
    
    Vals 
    lookup (int key) 
    {
      if (key < 0 || key > KEY_NUM - 1) { printf ("nonexist elem: key=%i\n", key) ; exit (1) ; } ;
      return tvals[key] ;
    }
    
    
    int 
    insert (int val) 
    {
      if (flags == ALL_BUSY) { printf ("overflow. val=%i\n", val) ; return 1 ; } ;
    
      // find the first free key in keyspace:
      int i, k ; for ( i = 0, k = flags; i < 8; i++, k >>= 1 ) { if (k & 1) continue ; else break ; } ;
    
      // store value in the table:
      tvals[ukeys[i]].key = i; tvals[ukeys[i]].val = val;
    
      // re-arrange flags
      flags |= (1 << i) ;   // to indicate that this key is in use now
      if (flags == ALL_BUSY) printf ("table is full now.\n") ;
    
      return 0 ;
    }
    
    
    int 
    delete (int key) 
    {
      if (key < 0 || key > KEY_NUM - 1) { printf ("nonexist key=%i\n", key) ; return 1;  } ;
    
      int k = (1 << key) ;     // is the key in use?
      if (k & flags) { tvals[key].val = 0 ; } else { return 1 ; } ;
    
      // re-arrange flags
      flags = ~k & flags ;        // to indicate that this key is free now
    
      return 0 ;
    }
    

    таблица с цепочками

    // keys : natural nums, vals : natural nums > 0
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define PRIME 11
    #define MAX 5
    
    typedef struct elem Elem;
    
    struct elem
            { int    key ;
              int    val ;
              Elem*  next ;
              Elem*  prev ;
            } ;
    Elem* table[PRIME] ;           // table with lists of key-value objects
    Elem *r, *p ;                  // current position , init position
    
    int lookup (int) , insert (int, int) , delete (int) , hash_func (int) ;
    
    int 
    main (int argc, char** argv, char** envp) 
    {
      // initialization
      r = p = malloc (MAX * sizeof (Elem)) ;
      int i ; for (i = 0 ; i < PRIME ; i++) table[i] = NULL ; 
    
      // some stuff here
    
      // finalization
      free (p) ; return 0 ;
    }
    
    
    int 
    lookup (int key) 
    {
      int h = hash_func (key) ; Elem* s = table[h] ;
    
      while (s) 
      {
        if (s->key == key) return s->val ;
        s = s->next ;
      } ;
    
      return 0 ;
    }
    
    
    int 
    insert (int key, int val) 
    {
      if (r - p > MAX - 1) { printf ("overflow\n") ; return -1 ; } ;
    
      int h = hash_func (key) ; Elem* s = table[h] ;
      Elem x ; x.key = key ; x.val = val ;
    
      if (!s) 
      {
        x.prev = r ; x.next = NULL ;
        *r = x ;
        table[h] = r ;
      }
      else 
      {
        while (s->val < val && s->next) s = s->next ; 
        if (s->next) 
        {
          x.prev = s->prev ; x.next = s ;
          *r = x ;
          s->prev->next = r ; s->prev = r ;
        }
        else 
        {
          x.prev = s ; x.next = NULL ;
          *r = x ;
          s->next = r ;
        } ;
      } ;
      r += 1 ;
    
      return h ;
    }
    
    
    int 
    delete (int key) 
    {
      int h = hash_func (key) ; Elem* s = table[h] ;
    
      while (s) 
      {
        if (s->key == key) 
        {
          if (s->prev) s->prev->next = s->next ; 
          else table[h] = s->next ; 
          s->val = 0 ;
          return 0 ;
        } ;
        s = s->next ;
      } ;
    
      return 1 ;
    }
    
    
    int
    hash_func (int key)
    { return key % PRIME; }
    
    
    // naive garbage collector
    void 
    gc (void) 
    {
      Elem* g = p ;
    
      while (g < r) 
      {
        if (!g->val) 
        {
          while (!r->val) { r -= 1; } ;
          r->prev->next = g ;
          *g = *r ;
          r->val = 0 ;
        } ;
        g += 1 ;
      } ;
    }
    

    универсальная таблица

    // universal hash  for m * 2 elements
    // p    : prime number
    // keys : natural nums [0, p - 1]
    //
    // hash function in the form: (((a * key + b) mod p) mod m)
    // restrictions : 0 < a < p - 1;     0 < b < p - 1;   m < p;     key < p
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define MSIZE 31   // size of the main key table m < p
    #define PRIME 283  // primary number p > m
    
    typedef struct elem Elem;
    
    struct elem
            { int    a ;
              int    b ;
              int    tv[4] ;
            } ;
    
    Elem table[MSIZE] ;
    
    int coin (void) , hash_func (int, int, int, int) , lookup (int) , insert (int) , delete (int) ;
    
    
    int 
    main (int argc, char** argv, char** envp) 
    {
      // initialization. size of all secondary tables is 4
      int i = 0 ; while (i < MSIZE) { Elem x = { x.a = 0, x.b = 0 } ; table[i] = x ; i++ ; } ;
      srandom ((long int) &table) ;  // seed the gen for 'coin flip' proc
    
      // some stuff here
    
      return 0 ;
    }
    
    
    int
    hash_func (int a, int b, int m, int key)
    { return (a * key + b) % PRIME % m; }
    
    
    int 
    insert (int key) 
    {
      int h1, h2, h0 = hash_func (1, 0, MSIZE, key) ;
      Elem* s = &table[h0] ;
    
      h1 = hash_func (s->a, s->b, 4, key) ;
    
      if ( ! s->tv[h1] ) s->tv[h1] = key ;                 // ok 
      else 
      {                                                    // key collision 
        lb1:  s->a = coin () ;                             // change coef "a" randomly
              s->b = coin () ;                             // change coef "b" randomly
              h1 = hash_func (s->a , s->b , 4 , key) ;
              h2 = hash_func (s->a , s->b , 4 , *s->tv) ;
              if (h2 == h1) goto lb1 ;                     // yes-yes, I know...
        s->tv[h2] = *s->tv ;
        s->tv[h1] = key ;
      } ;
    
      return 0 ;
    }
    
    
    int 
    lookup (int key) 
    {
      int h0 = hash_func (1, 0, MSIZE, key) ;
      Elem s = table[h0] ;
      int h1 = hash_func (s.a, s.b, 4, key) ;
    
      return s.tv[h1] ;
    }
    
    
    int 
    delete (int key) 
    {
      int h0 = hash_func (1, 0, MSIZE, key) ;
      Elem *s = &table[h0] ;
      int h1 = hash_func (s->a, s->b, 4, key) ;
      s->tv[h1] = 0 ;
    
      return 0 ;
    }
    
    
    int 
    coin ()
    {
      int y = random () ;
      srandom (y) ;
      return y % PRIME ;
    }
    

     

    кучи

    куча на массиве

    #include <stdlib.h>
    #include <stdio.h>
    #define INIT 15   // max heap size
    
    int p[INIT];
    int k;
    
    void 
    max_health (int i) 
    {
      int cl = (i << 1) | 1;   // left child 
      int cr = (i << 1) + 2;   // right child
       
      if      (p[cl] > p[cr] && p[i] < p[cl]) { p[i] ^= p[cl] ^= p[i] ^= p[cl]; }
      else if (p[cl] < p[cr] && p[i] < p[cr]) { p[i] ^= p[cr] ^= p[i] ^= p[cr]; };
    
      if (i <= k/2 - 2) { max_health (cl); max_health (cr); };
    }
    
    int 
    insert (int x) 
    {
      if (k == INIT) return 0;
      p[k] = x;
      max_health (0); 
      k += 1;
      return k;
    }
    
    int 
    extract () 
    {
      int m = *p;
      *p = 0; 
      max_health (0); 
      k -= 1;
      return m;
    }
    
    int count (void) { return k; }
    
    int 
    main (int argc, char** argv, char** envp) 
    {
      int i = 0; while (i < INIT) { p[i] = 0; i++; };
      k = 0;
    
      return 0;
    }
    

     

    leftist heap на бинарном дереве

    (Окасаки)

    как правило, множества и хеш-таблицы поддерживают эффективный доступ к произвольным элементам. однако иногда требуется эффективный доступ только к минимальному элементу. структура данных, поддерживающая такой режим доступа, называется priority queue или heap

    отношение порядка играет важную роль в семантике кучи. часто кучи реализуются через деревья с порядком кучи (heap-ordered), т.е. в которых элемент при каждой вершине не больше элементов в поддеревьях. при таком упорядочении минимальный элемент дерева всегда находится в корне

    левоориентированные кучи представляют собой двоичные деревья с порядком кучи, обладающие свойством: ранг любого левого поддерева не меньше ранга его сестринской правой вершины. ранг узла определяется как длина его right spine (т.е. самого правого пути от данного узла до пустого). простым следствием свойства левоориентированности является то, что правая периферия любого узла - кратчайший путь от него к пустому узлу

    если у нас есть некоторая структура упорядоченных элементов, мы можем представить левоориентированные кучи как двоичные деревья, снабженные информацией о ранге:

    type 'a heap = E | T of int * 'a * 'a heap * 'a heap

    заметим, что элементы правой периферии левоориентированной кучи (да и любого дерева с порядком кучи) расположены в порядке возрастания

    главная идея левоориентированной кучи заключается в том, что для слияния двух куч достаточно слить их правые периферии как упорядоченные списки, а затем вдоль полученного пути обменивать местами поддеревья при вершинах, чтобы восстановить свойство левоориентированности

    реализация левоориентированной кучи для целых:

    module type Heap =
      sig
        type e
        type h
    
        val empty     : h
        val isEmpty   : h -> bool
        val insert    : e  *  h -> h
        val merge     : h  *  h -> h
        val findMin   : h -> e          (* бросает исключение Empty_heap при пустой куче *)
        val deleteMin : h -> h          (* бросает исключение Empty_heap при пустой куче *)
      end 
    
    type 'a heap = E | T of int  *  'a  *  'a heap  *  'a heap                     
    
    module IntLeftHeap : Heap = 
      struct  
    
        exception Empty_heap ;;
      
        type e    = int
        type h    = int heap
        let empty = E
     
    
        let rank xs = match xs with | E -> 0 | T (r , _ , _ , _) -> r
     
    
        let makeT (x, a, b) =
          if (rank a) >= (rank b)
          then T (rank b + 1, x, a, b)
          else T (rank a + 1, x, b, a)
     
    
        let rec merge (xs , ys) = match (xs , ys) with
          | (E , h) | (h , E) -> h
          | ((T(_ , x , a1 , b1) as h1) , (T(_ , y , a2 , b2) as h2)) ->
              if x <= y
              then makeT (x , a1 , merge (b1 , h2))
              else makeT (y , a2 , merge (h1 , b2))
    
    
        let isEmpty xs = match xs with | E -> true | _ -> false
                                                                
        let insert (x , xs) = merge (T(1, x , E, E) , xs)
    
    
        let deleteMin xs = match xs with
          | E -> raise Empty_heap
          | (T(_ , x , a , b)) -> merge (a , b)
     
    
        let findMin xs = match xs with
          | E -> raise Empty_heap
          | (T(_ , x , a , b)) -> x
                                    
      end                        
    


    Сергей Копелиович

    skew heap

    // TODO
    

    binomial heap

    (Окасаки)

    биномиальные очереди, которые мы, чтобы избежать путаницы с очередями FIFO, будем называть биномиальными кучами - ещё одна распространенная реализация куч. биномиальные кучи устроены сложнее, чем левоориентированные, и, на первый взгляд, не возмещают эту сложность никакими преимуществами. однако в различных вариантах биномиальных куч можно заставить insert и merge выполняться за время O(1)

    биномиальные кучи строятся из более простых объектов, называемых биномиальными деревьями

    биномиальные деревья индуктивно определяются так:

  • -- биномиальное дерево ранга 0 представляет собой одиночный узел
  • -- биномиальное дерево ранга r+1 получается путем связывания двух биномиальных деревьев ранга r, так что одно из них становится самым левым потомком второго

    из этого определения видно, что биномиальное дерево ранга r содержит ровно 2^r элементов

    существует второе, эквивалентное первому, определение биномиальных деревьев, которым иногда удобнее пользоваться: биномиальное дерево ранга r представляет собой узел с r потомками t1, ..., tr, где каждое ti является биномиальным деревом ранга r-i

    мы представляем вершину биномиального дерева в виде элемента и списка его потомков. для удобства мы также помечаем каждый узел его рангом

    module type Ord =
      sig
        type t
        val compare : t -> t -> int
      end
        
    module BinomialHeap = functor (X : Ord) ->
      struct                      
    
        type 'a tree = Node of int  *  X.t  *  X.t tree list
        type 'a heap = X.t tree list
    
        exception Empty
                    
        let rank (Node (r , _ , _)) = r
    
        let root (Node (_ , x , _)) = x
    
    
    (*      function [link] deals with equial rank nodes only     *)
    
        let link ((Node (r, x1, lst1) as t1) , (Node (_, x2, lst2) as t2)) =
          if x1 < x2
          then Node (r + 1, x1, t2 :: lst1)
          else Node (r + 1, x2, t1 :: lst2)                                         
    
    
        let rec insTree = function (x) ->
          match x with
          | (t , []) -> [t]
          | (t , ((t' :: ts') as ts)) ->
             if rank t < rank t'
             then t :: ts
             else insTree (link (t , t') , ts')     (*  [link] deals with equial rank nodes only  *)
    
    
        let insert (x , ts) = insTree (Node (0 , x , []) , ts)                  
    
    
        let rec merge = function (x , y) ->
          match (x , y) with
          | (ts, []) | ([], ts) -> ts
          | ((t1 :: ts1 as a) , (t2 :: ts2 as b)) ->
             if   rank t1 < rank t2
             then t1 :: merge (ts1 , b)
             else if   rank t2 < rank t1
                  then t2 :: merge (a , ts2)
                  else insTree (link (t1 , t2) , merge (ts1, ts2))                              
    
    
        let rec removeMinTree = function (xs) ->
          match xs with
          | [] -> raise Empty                                 
          | [t] -> (t, [])
          | t :: ts ->
                let (t' , ts') = removeMinTree ts
                in if root t < root t' then (t , ts) else (t' , t :: ts')
    
    
        let findMin = function (ts) ->
          let (t , _) = removeMinTree ts in root t
    
    
        let deleteMin = function (ts) ->
          let (Node (_ , x , ts1) , ts2) = removeMinTree ts
          in merge (List.rev ts1 , ts2)                                                              
    
      end
     

     

    деревья

    бинарное дерево

    module type ORDERED =
    sig
      type t
    
      val eq  : t * t -> bool
      val lt  : t * t -> bool
      val leq : t * t -> bool
    end
    
    (* реализация двоичных деревьев поиска в виде функтора *)
    
    module Unbalanced = functor (Element: ORDERED) ->
    struct
      type e = Element.t
      type tree = E | T of tree * e * tree
    
      let empty = E
    
      let rec member (x, z) = match z with
        | E -> false
        | T (a, y, b) ->
           if Element.lt (x, y)
           then member (x, a)
           else if Element.lt (y, x) 
                then member (x, b)
                else true 
    
      let rec insert (x, z) = match z with
        | E -> T (E, x, E)
        | T (a, y, b) ->
           if Element.lt (x, y) 
           then T (insert (x, a), y, b)
           else if Element.lt (y, x) 
                then T (a, y, insert (x, b))
                else z
    end
    


    Александр Куликов

    AVL дерево

    // TODO
    


    Александр Куликов

    splay дерево

    // TODO
    


    Александр Куликов

    черно-красное дерево

    (Окасаки)

    двоичные деревья поиска хорошо ведут себя на случайных данных, однако на упорядоченных данных дерево становится "бамбуком"/"гребенкой" и каждая операция может занимать до O(n) времени

    решение состоит в том, чтобы каждое поддерево поддерживать в приблизительно сбалансированном состоянии, тогда каждая операция выполняется не хуже, чем за время O(log n)

    красно-чёрное дерево представляет собой двоичное дерево поиска, в котором каждый узел окрашен - добавляем поле цвета в тип двоичных деревьев поиска. все терминальные узлы считаются чёрными, поэтому конструктор E в поле цвета не нуждается

    мы требуем, чтобы всякое красно-чёрное дерево соблюдало два инварианта:
    1. y красного узла не может быть красного ребёнка
    2. каждый путь от любого подкорня дерева до терминального пустого узла содержит одинаковое количество чёрных узлов

    вместе эти два инварианта гарантируют, что самый длинный возможный путь по красно-чёрному дереву, где красные и чёрные узлы постоянно чередуются, не более чем вдвое длиннее самого короткого пути, состоящего только из чёрных узлов

    функция member для красно-чёрных деревьев не обращает внимания на цвета

    функция insert должна поддерживать два инварианта баланса:
    во-первых, когда мы создаем новый узел в ветке ins E, мы сначала окрашиваем его в красный цвет
    во-вторых, в окончательном результате мы корень всего дерева целиком всегда окрашиваем чёрным
    наконец, в ветках x < y и x > y мы вызовы конструктора T заменяем на обращения к функции balance

    функция balance действует подобно конструктору T, но она переупорядочивает свои аргументы, чтобы обеспечить инварианты

    если новый узел окрашен красным, все в порядке с Инвариант2, но если отец нового узла тоже красный, нарушается Инвариант1. мы временно позволяем существовать такому нарушению - balance обнаруживает и исправляет красно-красные нарушения тогда, когда обрабатывает чёрного родителя красного узла с красным ребёнком

    такая чёрно-красно-красная цепочка может возникнуть в четырёх различных конфигурациях, в зависимости от того, левым или правым ребёнком является каждая из красных вершин. однако в каждом из этих случаев решение одно и то же: нужно преобразовать чёрно-красно-красный путь в красную вершину с двумя чёрными детьми. нетрудно проверить, что в получающемся поддереве будут соблюдены оба инварианта красно-чёрного баланса

    после балансировки некоторого поддерева красный корень этого поддерева может оказаться ребёнком ещё одного красного узла. таким образом, балансировка продолжается до самого корня дерева. на самом верху дерева мы можем получить красную вершину с красным ребёнком, но без чёрного родителя. с этим вариантом мы справляемся, всегда перекрашивая корень в чёрное

    {-# LANGUAGE OverloadedStrings , MultiParamTypeClasses , FlexibleInstances #-}
    
    module RBTree (RBTree , empty , member , insert , delete, maxElem, minElem) where
    
    data Color = R | B deriving (Show)
    
    data RBTree a = E | T Color a (RBTree a) (RBTree a) deriving (Show)
    
    
    balance :: Color -> q -> RBTree q -> RBTree q -> RBTree q
    balance B z (T R y (T R x a b) c) d = T R y (T B x a b) (T B z c d)
    balance B z (T R x a (T R y b c)) d = T R y (T B x a b) (T B z c d)
    balance B x a (T R z (T R y b c) d) = T R y (T B x a b) (T B z c d)
    balance B x a (T R y b (T R z c d)) = T R y (T B x a b) (T B z c d)
    balance p x a b = T p x a b
    
    
    empty :: RBTree a
    empty = E
    
    
    member :: Ord a => a -> RBTree a -> Bool
    member _ E = False
    member x (T _ y a b) | x < y = member x a | x > y = member x b | otherwise =  True
    
    
    insert :: Ord a => a -> RBTree a -> RBTree a
    insert x ts = T B y a b where
      ins E = T R x E E
      ins q@(T p z g h) | x < z = balance p z (ins g) h
                        | x > z = balance p z g (ins h)
                        | otherwise = q
      T _ y a b = ins ts
    
    
    delete :: Ord a => a -> RBTree a -> RBTree a
    delete _ E = E
    delete x (T p y a b) | x < y     = balance p y (delete x a) b
                         | x > y     = balance p y a (delete x b)
                         | otherwise = merge a b
    
    
    merge :: Ord a => RBTree a -> RBTree a -> RBTree a
    merge E ys = ys
    merge xs E = xs
    merge (T p1 x1 a1 b1) (T p2 x2 a2 b2) 
      | x1 < x2   = balance p1 x2 (T p2 x1 a1 (merge a2 b1)) b2 
      | x1 > x2   = balance p2 x1 a1 (T p1 x2 (merge a2 b1) b2) 
      | otherwise = balance R  x1 (merge a1 a2) (merge b1 b2)
    
    
    minElem :: RBTree a -> a
    minElem (T _ x E _) = x
    minElem (T _ _ l _) = minElem l
    
    
    maxElem :: RBTree a -> a
    maxElem (T _ x _ E) = x
    maxElem (T _ _ _ r) = maxElem r
    

    -- | unit tests for RBTree
    {-# language ScopedTypeVariables #-}
    
    module Main where
    
    import RBTree as RB
    import Test.QuickCheck
    
    t1 = quickCheckWith (stdArgs { maxSuccess = 5000 }) 
      (\xs -> let ts = foldr (\x a -> insert x a) empty xs
              in if null xs then True else 
                 let ts1 = RB.delete (head xs) ts 
                 in if ts1 == RB.empty then True else 
                    not $ all (\x -> RB.member x ts1) (xs :: [(Double , String)]))
    
    t2 = quickCheckWith (stdArgs { maxSuccess = 5000 }) 
      (\xs -> let ts = foldr (\x a -> insert x a) empty xs
              in if null xs then True else 
                 let ts1 = RB.delete (head xs) ts 
                 in if ts1 == RB.empty then True else 
                    not $ all (\x -> RB.member x ts1) (xs :: [String]))
    
    t3 = quickCheckWith (stdArgs { maxSuccess = 5000 }) 
      (vector 100 >>= \xs -> return $ 
        let ts = foldr (\x a -> insert x a) empty xs
        in all (\x -> RB.member x ts) (xs :: [Int]))
    
    t4 = quickCheckWith (stdArgs { maxSuccess = 5000 }) 
      (vector 100 >>= \xs -> return $ 
        let ts = foldr (\x a -> insert x a) empty xs
        in  all (\x -> RB.member x ts) (xs :: [Char]))
    
    t5 = quickCheckWith (stdArgs { maxSuccess = 5000 }) 
      (vector 100 >>= \xs -> return $ 
        let ts = foldr (\x a -> RB.insert x a) empty (xs :: [Double])
        in all (\x -> RB.member x ts) xs)
    
    t6 = quickCheckWith (stdArgs { maxSuccess = 5000 }) 
      (vector 100 >>= \xs -> return $ 
        let ts = foldr (\x a -> RB.insert x a) empty (xs :: [Int])
        in RB.maxElem ts == maximum xs)
    
    t7 = quickCheckWith (stdArgs { maxSuccess = 5000 }) 
      (vector 100 >>= \xs -> return $ 
        let ts = foldr (\x a -> RB.insert x a) empty (xs :: [String])
        in RB.minElem ts == minimum xs)
         
    main :: IO ()
    main = t1 >> t2 >> t3 >> t4 >> t5 >> t6 >> t7