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

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

数值算法/人工智能

开发平台：

MultiPlatform

_bb_tree.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _bb_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. *******************************************************************************/
  14. #include <LEDA/impl/bb_tree.h>
  16. //----------------------------------------------------------------------------
  17. //  bb_tree:
  18. //
  19. //  rebalancing routines for BB[alpha] trees
  20. //
  21. //----------------------------------------------------------------------------
  24. void bb_tree::rebal(bb_tree_item v, int delta)
  25. {
  26.   while ( v != root() )
  27.   { 
  28.     bb_tree_item u = v->parent;
  29.     bb_tree_item l = u->child[left];
  30.     bb_tree_item r = u->child[right];
  32.     int bu  = u->get_bal() + delta;      // increase/decrease weight of u
  33.     int bl  = l->get_bal();
  34.     int br  = r->get_bal();
  36.     u->set_bal(bu);
  38.     if (64*bl < bu*alpha)
  39.        { int brl = r->child[left]->get_bal();
  40.          if (64*brl <=  d * br) 
  41.             { rotation(u,r,right);
  42.               r->set_bal(bu);
  43.               u->set_bal(bl + brl);
  44.               v = r;
  45.              }
  46.          else 
  47.             { bb_tree_item w = r->child[left];
  48.               int bwl = w->child[left]->get_bal();
  49.               double_rotation(u,r,w,right);
  50.               w->set_bal(bu);
  51.               u->set_bal(bl + bwl);
  52.               r->set_bal(br - bwl);
  53.               v = w;
  54.              }
  55.         }
  56.     else 
  57.        if (64*br < bu*alpha) 
  58.        { int bll = l->child[left]->get_bal();
  59.          if (64*bll >  d * bl) 
  60.               { rotation(u,l,left);
  61.                 l->set_bal(bu);
  62.                 u->set_bal(bu - bll);
  63.                 v = l;
  64.                }
  65.    else 
  66.               { bb_tree_item w = l->child[right];
  67.                 int bwr = w->child[right]->get_bal();
  68.                 double_rotation(u,l,w,left);
  69.                 w->set_bal(bu);
  70.                 u->set_bal(br + bwr);
  71.                 l->set_bal(bl - bwr);
  72.                 v = w;
  73.                }
  74.         }
  76.         else v = u;
  77.        
  78.    }
  80. }
  84. void bb_tree::insert_rebal(bb_tree_item v) { rebal(v,1); }
  86. void bb_tree::del_rebal(bb_tree_item v, bb_tree_item) { rebal(v,-1); }