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

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

数值算法/人工智能

开发平台：

MultiPlatform

_rs_tree.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _rs_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/rs_tree.h>
  15. //----------------------------------------------------------------------------
  16. //  rs_tree:
  17. //
  18. //  rebalancing of randomized search trees
  19. //
  20. //----------------------------------------------------------------------------
  23. void rs_tree::insert_rebal(rs_tree_item v)
  24. {
  25.   rs_tree_item u = v->parent;
  27.   int prio = v->get_bal();
  29.   ROOT.set_bal(prio);
  31.   if (prio < u->get_bal())
  32.   {
  33.     int dir = (v == u->child[left]) ? left : right;
  35.     while (prio < u->get_bal())                /* rotate v up        */
  36.     {                                                /*       p            */
  37.       bin_tree_node* p = u->parent;                  /*       |            */
  38.       bin_tree_node* r = v->child[1-dir];            /*       |            */
  39.       u->child[dir] = r;                             /*       u            */
  40.       v->child[1-dir] = u;                           /*      /            */
  41.       u->parent = v;                                 /*     /             */
  42.       r->parent = u;                                 /*    *     v (prio)  */
  43.       propagate_modification(5,v,u);                 /*         /         */
  44.       propagate_modification(4,u,r);                 /*        /          */
  45.                                                      /*       r     *      */
  46.       dir = (u == p->child[left]) ? left : right;
  47.       u = p;
  48.      }
  49.   
  50.     // link to parent
  51.   
  52.     u->child[dir] = v;
  53.     v->parent = u;
  55.     if (u != &ROOT) 
  56.        propagate_modification(6,u,v);
  57.   }
  59. }
  61. void rs_tree::del_rebal(rs_tree_item, rs_tree_item) { }