alpar@1: /* glpavl.c (binary search tree) */
alpar@1: 
alpar@1: /***********************************************************************
alpar@1: *  This code is part of GLPK (GNU Linear Programming Kit).
alpar@1: *
alpar@1: *  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@1: *  2009, 2010 Andrew Makhorin, Department for Applied Informatics,
alpar@1: *  Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@1: *  E-mail: <mao@gnu.org>.
alpar@1: *
alpar@1: *  GLPK is free software: you can redistribute it and/or modify it
alpar@1: *  under the terms of the GNU General Public License as published by
alpar@1: *  the Free Software Foundation, either version 3 of the License, or
alpar@1: *  (at your option) any later version.
alpar@1: *
alpar@1: *  GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@1: *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@1: *  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@1: *  License for more details.
alpar@1: *
alpar@1: *  You should have received a copy of the GNU General Public License
alpar@1: *  along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@1: ***********************************************************************/
alpar@1: 
alpar@1: #include "glpavl.h"
alpar@1: 
alpar@1: AVL *avl_create_tree(int (*fcmp)(void *info, const void *key1,
alpar@1:       const void *key2), void *info)
alpar@1: {     /* create AVL tree */
alpar@1:       AVL *tree;
alpar@1:       tree = xmalloc(sizeof(AVL));
alpar@1:       tree->pool = dmp_create_pool();
alpar@1:       tree->root = NULL;
alpar@1:       tree->fcmp = fcmp;
alpar@1:       tree->info = info;
alpar@1:       tree->size = 0;
alpar@1:       tree->height = 0;
alpar@1:       return tree;
alpar@1: }
alpar@1: 
alpar@1: int avl_strcmp(void *info, const void *key1, const void *key2)
alpar@1: {     /* compare character string keys */
alpar@1:       xassert(info == info);
alpar@1:       return strcmp(key1, key2);
alpar@1: }
alpar@1: 
alpar@1: static AVLNODE *rotate_subtree(AVL *tree, AVLNODE *node);
alpar@1: 
alpar@1: AVLNODE *avl_insert_node(AVL *tree, const void *key)
alpar@1: {     /* insert new node into AVL tree */
alpar@1:       AVLNODE *p, *q, *r;
alpar@1:       short int flag;
alpar@1:       /* find an appropriate point for insertion */
alpar@1:       p = NULL; q = tree->root;
alpar@1:       while (q != NULL)
alpar@1:       {  p = q;
alpar@1:          if (tree->fcmp(tree->info, key, p->key) <= 0)
alpar@1:          {  flag = 0;
alpar@1:             q = p->left;
alpar@1:             p->rank++;
alpar@1:          }
alpar@1:          else
alpar@1:          {  flag = 1;
alpar@1:             q = p->right;
alpar@1:          }
alpar@1:       }
alpar@1:       /* create new node and insert it into the tree */
alpar@1:       r = dmp_get_atom(tree->pool, sizeof(AVLNODE));
alpar@1:       r->key = key; r->type = 0; r->link = NULL;
alpar@1:       r->rank = 1; r->up = p;
alpar@1:       r->flag = (short int)(p == NULL ? 0 : flag);
alpar@1:       r->bal = 0; r->left = NULL; r->right = NULL;
alpar@1:       tree->size++;
alpar@1:       if (p == NULL)
alpar@1:          tree->root = r;
alpar@1:       else
alpar@1:          if (flag == 0) p->left = r; else p->right = r;
alpar@1:       /* go upstairs to the root and correct all subtrees affected by
alpar@1:          insertion */
alpar@1:       while (p != NULL)
alpar@1:       {  if (flag == 0)
alpar@1:          {  /* the height of the left subtree of [p] is increased */
alpar@1:             if (p->bal > 0)
alpar@1:             {  p->bal = 0;
alpar@1:                break;
alpar@1:             }
alpar@1:             if (p->bal < 0)
alpar@1:             {  rotate_subtree(tree, p);
alpar@1:                break;
alpar@1:             }
alpar@1:             p->bal = -1; flag = p->flag; p = p->up;
alpar@1:          }
alpar@1:          else
alpar@1:          {  /* the height of the right subtree of [p] is increased */
alpar@1:             if (p->bal < 0)
alpar@1:             {  p->bal = 0;
alpar@1:                break;
alpar@1:             }
alpar@1:             if (p->bal > 0)
alpar@1:             {  rotate_subtree(tree, p);
alpar@1:                break;
alpar@1:             }
alpar@1:             p->bal = +1; flag = p->flag; p = p->up;
alpar@1:          }
alpar@1:       }
alpar@1:       /* if the root has been reached, the height of the entire tree is
alpar@1:          increased */
alpar@1:       if (p == NULL) tree->height++;
alpar@1:       return r;
alpar@1: }
alpar@1: 
alpar@1: void avl_set_node_type(AVLNODE *node, int type)
alpar@1: {     /* assign the type field of specified node */
alpar@1:       node->type = type;
alpar@1:       return;
alpar@1: }
alpar@1: 
alpar@1: void avl_set_node_link(AVLNODE *node, void *link)
alpar@1: {     /* assign the link field of specified node */
alpar@1:       node->link = link;
alpar@1:       return;
alpar@1: }
alpar@1: 
alpar@1: AVLNODE *avl_find_node(AVL *tree, const void *key)
alpar@1: {     /* find node in AVL tree */
alpar@1:       AVLNODE *p;
alpar@1:       int c;
alpar@1:       p = tree->root;
alpar@1:       while (p != NULL)
alpar@1:       {  c = tree->fcmp(tree->info, key, p->key);
alpar@1:          if (c == 0) break;
alpar@1:          p = (c < 0 ? p->left : p->right);
alpar@1:       }
alpar@1:       return p;
alpar@1: }
alpar@1: 
alpar@1: int avl_get_node_type(AVLNODE *node)
alpar@1: {     /* retrieve the type field of specified node */
alpar@1:       return node->type;
alpar@1: }
alpar@1: 
alpar@1: void *avl_get_node_link(AVLNODE *node)
alpar@1: {     /* retrieve the link field of specified node */
alpar@1:       return node->link;
alpar@1: }
alpar@1: 
alpar@1: static AVLNODE *find_next_node(AVL *tree, AVLNODE *node)
alpar@1: {     /* find next node in AVL tree */
alpar@1:       AVLNODE *p, *q;
alpar@1:       if (tree->root == NULL) return NULL;
alpar@1:       p = node;
alpar@1:       q = (p == NULL ? tree->root : p->right);
alpar@1:       if (q == NULL)
alpar@1:       {  /* go upstairs from the left subtree */
alpar@1:          for (;;)
alpar@1:          {  q = p->up;
alpar@1:             if (q == NULL) break;
alpar@1:             if (p->flag == 0) break;
alpar@1:             p = q;
alpar@1:          }
alpar@1:       }
alpar@1:       else
alpar@1:       {  /* go downstairs into the right subtree */
alpar@1:          for (;;)
alpar@1:          {  p = q->left;
alpar@1:             if (p == NULL) break;
alpar@1:             q = p;
alpar@1:          }
alpar@1:       }
alpar@1:       return q;
alpar@1: }
alpar@1: 
alpar@1: void avl_delete_node(AVL *tree, AVLNODE *node)
alpar@1: {     /* delete specified node from AVL tree */
alpar@1:       AVLNODE *f, *p, *q, *r, *s, *x, *y;
alpar@1:       short int flag;
alpar@1:       p = node;
alpar@1:       /* if both subtrees of the specified node are non-empty, the node
alpar@1:          should be interchanged with the next one, at least one subtree
alpar@1:          of which is always empty */
alpar@1:       if (p->left == NULL || p->right == NULL) goto skip;
alpar@1:       f = p->up; q = p->left;
alpar@1:       r = find_next_node(tree, p); s = r->right;
alpar@1:       if (p->right == r)
alpar@1:       {  if (f == NULL)
alpar@1:             tree->root = r;
alpar@1:          else
alpar@1:             if (p->flag == 0) f->left = r; else f->right = r;
alpar@1:          r->rank = p->rank; r->up = f;
alpar@1:          r->flag = p->flag; r->bal = p->bal;
alpar@1:          r->left = q; r->right = p;
alpar@1:          q->up = r;
alpar@1:          p->rank = 1; p->up = r; p->flag = 1;
alpar@1:          p->bal = (short int)(s == NULL ? 0 : +1);
alpar@1:          p->left = NULL; p->right = s;
alpar@1:          if (s != NULL) s->up = p;
alpar@1:       }
alpar@1:       else
alpar@1:       {  x = p->right; y = r->up;
alpar@1:          if (f == NULL)
alpar@1:             tree->root = r;
alpar@1:          else
alpar@1:             if (p->flag == 0) f->left = r; else f->right = r;
alpar@1:          r->rank = p->rank; r->up = f;
alpar@1:          r->flag = p->flag; r->bal = p->bal;
alpar@1:          r->left = q; r->right = x;
alpar@1:          q->up = r; x->up = r; y->left = p;
alpar@1:          p->rank = 1; p->up = y; p->flag = 0;
alpar@1:          p->bal = (short int)(s == NULL ? 0 : +1);
alpar@1:          p->left = NULL; p->right = s;
alpar@1:          if (s != NULL) s->up = p;
alpar@1:       }
alpar@1: skip: /* now the specified node [p] has at least one empty subtree;
alpar@1:          go upstairs to the root and adjust the rank field of all nodes
alpar@1:          affected by deletion */
alpar@1:       q = p; f = q->up;
alpar@1:       while (f != NULL)
alpar@1:       {  if (q->flag == 0) f->rank--;
alpar@1:          q = f; f = q->up;
alpar@1:       }
alpar@1:       /* delete the specified node from the tree */
alpar@1:       f = p->up; flag = p->flag;
alpar@1:       q = p->left != NULL ? p->left : p->right;
alpar@1:       if (f == NULL)
alpar@1:          tree->root = q;
alpar@1:       else
alpar@1:          if (flag == 0) f->left = q; else f->right = q;
alpar@1:       if (q != NULL) q->up = f, q->flag = flag;
alpar@1:       tree->size--;
alpar@1:       /* go upstairs to the root and correct all subtrees affected by
alpar@1:          deletion */
alpar@1:       while (f != NULL)
alpar@1:       {  if (flag == 0)
alpar@1:          {  /* the height of the left subtree of [f] is decreased */
alpar@1:             if (f->bal == 0)
alpar@1:             {  f->bal = +1;
alpar@1:                break;
alpar@1:             }
alpar@1:             if (f->bal < 0)
alpar@1:                f->bal = 0;
alpar@1:             else
alpar@1:             {  f = rotate_subtree(tree, f);
alpar@1:                if (f->bal < 0) break;
alpar@1:             }
alpar@1:             flag = f->flag; f = f->up;
alpar@1:          }
alpar@1:          else
alpar@1:          {  /* the height of the right subtree of [f] is decreased */
alpar@1:             if (f->bal == 0)
alpar@1:             {  f->bal = -1;
alpar@1:                break;
alpar@1:             }
alpar@1:             if (f->bal > 0)
alpar@1:                f->bal = 0;
alpar@1:             else
alpar@1:             {  f = rotate_subtree(tree, f);
alpar@1:                if (f->bal > 0) break;
alpar@1:             }
alpar@1:             flag = f->flag; f = f->up;
alpar@1:          }
alpar@1:       }
alpar@1:       /* if the root has been reached, the height of the entire tree is
alpar@1:          decreased */
alpar@1:       if (f == NULL) tree->height--;
alpar@1:       /* returns the deleted node to the memory pool */
alpar@1:       dmp_free_atom(tree->pool, p, sizeof(AVLNODE));
alpar@1:       return;
alpar@1: }
alpar@1: 
alpar@1: static AVLNODE *rotate_subtree(AVL *tree, AVLNODE *node)
alpar@1: {     /* restore balance of AVL subtree */
alpar@1:       AVLNODE *f, *p, *q, *r, *x, *y;
alpar@1:       xassert(node != NULL);
alpar@1:       p = node;
alpar@1:       if (p->bal < 0)
alpar@1:       {  /* perform negative (left) rotation */
alpar@1:          f = p->up; q = p->left; r = q->right;
alpar@1:          if (q->bal <= 0)
alpar@1:          {  /* perform single negative rotation */
alpar@1:             if (f == NULL)
alpar@1:                tree->root = q;
alpar@1:             else
alpar@1:                if (p->flag == 0) f->left = q; else f->right = q;
alpar@1:             p->rank -= q->rank;
alpar@1:             q->up = f; q->flag = p->flag; q->bal++; q->right = p;
alpar@1:             p->up = q; p->flag = 1;
alpar@1:             p->bal = (short int)(-q->bal); p->left = r;
alpar@1:             if (r != NULL) r->up = p, r->flag = 0;
alpar@1:             node = q;
alpar@1:          }
alpar@1:          else
alpar@1:          {  /* perform double negative rotation */
alpar@1:             x = r->left; y = r->right;
alpar@1:             if (f == NULL)
alpar@1:                tree->root = r;
alpar@1:             else
alpar@1:                if (p->flag == 0) f->left = r; else f->right = r;
alpar@1:             p->rank -= (q->rank + r->rank);
alpar@1:             r->rank += q->rank;
alpar@1:             p->bal = (short int)(r->bal >= 0 ? 0 : +1);
alpar@1:             q->bal = (short int)(r->bal <= 0 ? 0 : -1);
alpar@1:             r->up = f; r->flag = p->flag; r->bal = 0;
alpar@1:             r->left = q; r->right = p;
alpar@1:             p->up = r; p->flag = 1; p->left = y;
alpar@1:             q->up = r; q->flag = 0; q->right = x;
alpar@1:             if (x != NULL) x->up = q, x->flag = 1;
alpar@1:             if (y != NULL) y->up = p, y->flag = 0;
alpar@1:             node = r;
alpar@1:          }
alpar@1:       }
alpar@1:       else
alpar@1:       {  /* perform positive (right) rotation */
alpar@1:          f = p->up; q = p->right; r = q->left;
alpar@1:          if (q->bal >= 0)
alpar@1:          {  /* perform single positive rotation */
alpar@1:             if (f == NULL)
alpar@1:                tree->root = q;
alpar@1:             else
alpar@1:                if (p->flag == 0) f->left = q; else f->right = q;
alpar@1:             q->rank += p->rank;
alpar@1:             q->up = f; q->flag = p->flag; q->bal--; q->left = p;
alpar@1:             p->up = q; p->flag = 0;
alpar@1:             p->bal = (short int)(-q->bal); p->right = r;
alpar@1:             if (r != NULL) r->up = p, r->flag = 1;
alpar@1:             node = q;
alpar@1:          }
alpar@1:          else
alpar@1:          {  /* perform double positive rotation */
alpar@1:             x = r->left; y = r->right;
alpar@1:             if (f == NULL)
alpar@1:                tree->root = r;
alpar@1:             else
alpar@1:                if (p->flag == 0) f->left = r; else f->right = r;
alpar@1:             q->rank -= r->rank;
alpar@1:             r->rank += p->rank;
alpar@1:             p->bal = (short int)(r->bal <= 0 ? 0 : -1);
alpar@1:             q->bal = (short int)(r->bal >= 0 ? 0 : +1);
alpar@1:             r->up = f; r->flag = p->flag; r->bal = 0;
alpar@1:             r->left = p; r->right = q;
alpar@1:             p->up = r; p->flag = 0; p->right = x;
alpar@1:             q->up = r; q->flag = 1; q->left = y;
alpar@1:             if (x != NULL) x->up = p, x->flag = 1;
alpar@1:             if (y != NULL) y->up = q, y->flag = 0;
alpar@1:             node = r;
alpar@1:          }
alpar@1:       }
alpar@1:       return node;
alpar@1: }
alpar@1: 
alpar@1: void avl_delete_tree(AVL *tree)
alpar@1: {     /* delete AVL tree */
alpar@1:       dmp_delete_pool(tree->pool);
alpar@1:       xfree(tree);
alpar@1:       return;
alpar@1: }
alpar@1: 
alpar@1: /* eof */