开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
_avl_tree.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：3k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

_avl_tree.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _avl_tree.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #include <LEDA/impl/avl_tree.h>
  16. //----------------------------------------------------------------------------
  17. //  avl_tree:
  18. //
  19. //  rebalancing routines for AVL trees
  20. //
  21. //----------------------------------------------------------------------------
  24. void avl_tree::insert_rebal(avl_tree_item v)
  25. {
  26.   // preconditions:  v is new node created by insertion
  27.   //                 v != root
  28.   //                 height(v) == 1, bal(v) == 0;
  30.   // bal(v) == height(R) - height(L)           
  32.   //                    u
  33.   //                    |
  34.   //                    v
  35.   //                   / 
  36.   //                  L   R
  37.   //
  39.   
  40.   while ( v != root() )
  41.   {
  42.     avl_tree_item u = v->parent;
  44.     int dir = (v == u->child[left]) ? left : right;
  46.     int b = u->get_bal();
  48.     if (dir==left)   // insertion in left subtree of u 
  49.        b--;
  50.     else             // insertion in right subtree of u
  51.        b++; 
  53.     u->set_bal(b);
  55.     if (b==0)  break;   // height of u has not changed 
  57.     if (b != 1 && b != -1)
  58.     { 
  59.       // u is out of balance (-2 or + 2)
  61.       int d = (b < 0) ? -1 : +1;
  62.   
  63.       avl_tree_item w = u->child[dir];
  64.   
  65.       if (w->get_bal() == d)
  66.       { rotation(u,w,dir);
  67.         u->set_bal(0);
  68.         w->set_bal(0);
  69.        }
  70.       else
  71.       { avl_tree_item x = w->child[1-dir];
  72.         double_rotation(u,w,x,dir);
  74.         if (x->get_bal() == d)
  75.            u->set_bal(-d);
  76.         else
  77.            u->set_bal(0);
  78.   
  79.         if (x->get_bal() == -d)
  80.            w->set_bal(d);
  81.         else
  82.            w->set_bal(0);
  83.   
  84.         x->set_bal(0);
  85.        }
  86.   
  87.       break;
  88.     }
  90.     v = u;
  92.   }
  94. }
  97. void avl_tree::del_rebal(avl_tree_item v, avl_tree_item)
  98. {
  99.   // precondition:    p is removed inner node
  100.   //                  v is remaining child of p (already linked to parent u)
  101.   //                  v != root
  103.   
  104.   while ( v != root() )
  105.   {
  106.     avl_tree_item u = v->parent;
  108.     int dir = (v == u->child[left]) ? left : right;
  110.     int b = u->get_bal();
  112.     if (dir==left)  // deletion in left  subtree of u
  113.        b++;
  114.     else            // deletion in right subtree of u
  115.        b--;
  117.     u->set_bal(b);
  119.     if (b == 1 || b == -1) break;   // height of u has not changed
  121.     if (b != 0)
  122.     { 
  123.       // u is out of balance (-2 or + 2)
  125.       int d = (b < 0) ? -1 : +1;
  126.   
  127.       avl_tree_item w = u->child[1-dir];
  128.   
  129.       if (d * w->get_bal() >= 0)
  130.       { rotation(u,w,1-dir);
  131.         if (w->get_bal() == 0)
  132.           { u->set_bal(d);
  133.             w->set_bal(-d);
  134.             break;
  135.            }
  136.         else
  137.           { u->set_bal(0);
  138.             w->set_bal(0);
  139.            }
  140.         v = w;
  141.        }
  142.       else
  143.       { avl_tree_item x = w->child[dir];
  144.         double_rotation(u,w,x,1-dir);
  146.         if (x->get_bal() == d)
  147.            u->set_bal(-d);
  148.         else
  149.            u->set_bal(0);
  150.   
  151.         if (x->get_bal() == -d)
  152.            w->set_bal(d);
  153.         else
  154.            w->set_bal(0);
  155.   
  156.         x->set_bal(0);
  157.         v = x;
  158.        }
  159.     }
  161.     else v = u;
  163.   }
  164. }