是否可以组合对称代码段？

Question

我正在为我的学校项目实现 avl 树，发现自己为对称情况编写了两次几乎相同的代码。例如，此函数执行两个节点的旋转以平衡树。 if 子句处理低节点是高节点的左子节点的情况，else 子句处理相反的情况：

void avl<T>::rotate(node<T> *x, node<T> *y)
{
  if (x == y->l)
  {
    x->p = y->p;
    if (y->p != nullptr)
      if(y->p->l == y)
        y->p->l = x;
      else
        y->p->r = x;
    else
      this->setHead(x);
    y->p = x;
    y->l = x->r;
    if(x->r != nullptr)
      x->r->p = y;
    x->r = y;
    y->dl = y->calcd('l');
    x->dr = x->calcd('r');
    if(x->p != nullptr)
      if(x->p->l == x)
        x->p->dl = x->p->calcd('l');
      else
        x->p->dr = x->p->calcd('r');
  }
  else
  {
    x->p = y->p;
    if (y->p != nullptr)
      if(y->p->r == y)
        y->p->r = x;
      else
        y->p->l = x;
    else
      this->setHead(x);
    y->p = x;
    y->r = x->l;
    if(x->l != nullptr)
      x->l->p = y;
    x->l = y;
    y->dl = y->calcd('l');
    x->dr = x->calcd('r');
    if(x->p != nullptr)
      if(x->p->r == x)
        x->p->dr = x->p->calcd('r');
      else
        x->p->dl = x->p->calcd('l');

  }
}

如您所见，else 子句与 if 子句完全相似，但交换了 'l' 和 'r'。有没有办法将它们结合起来。我可以做些什么来改进它？我的代码中是否存在设计错误？

Answer 1

All problems in computer science can be solved by another level of indirection, except of course for the problem of too many indirections.
(David Wheeler)

你可以这样做（完全未经测试）：

node<T>** y_sibling_1 = x == y->l ? &y->p->l : &y->p->r;
node<T>** y_sibling_2 = x == y->l ? &y->p->r : &y->p->l;
node<T>** x_child = x == y->l ? &x->r : &x->l;
node<T>** y_child = x == y->l ? &y->l : &y->r;

x->p = y->p;
if (y->p != nullptr)
    if(*y_sibling_1 == y)
        *y_sibling_1 = x;
    else
        *y_sibling_2 = x;
else
    this->setHead(x);
y->p = x;
*y_child = *x_child;
if(*x_child != nullptr)
    (*x_child)->p = y;
*x_child = y;
y->dl = y->calcd('l');
x->dr = x->calcd('r');
if(x->p != nullptr)
    if(x->p->l == x)
        x->p->dl = x->p->calcd('l');
    else
        x->p->dr = x->p->calcd('r');

（请注意，您的最终条件在这两种情况下是等效的。）

这个是不是绕太多了，个人看法问题。

Answer 2

您可能需要此处的模板，因此您需要 calcd<true>() 和 calcd<false>()。

有了这个改变，你可以写

template<bool xChildy> 
void avl<T>::rotateImpl(node<T> *x, node<T> *y); 

void avl<T>::rotate(node<T> *x, node<T> *y)
{
  if (x == y->l)  {
    rotateImpl<true>(x,y);
  }
  else  {
    rotateImpl<false>(x,y);
  }
}

Answer 3

使用指向成员的指针。两个分支之间的唯一区别是您访问的是哪个成员，因此这是抽象出来的简单方法：

using Child = node<T> node<T>::*;

void rotate_impl(node<T>* x, node<T>* y, Child* left, Child* right)
{
    x->p = y->p;
    if (y->p != nullptr) {
      if(y->p->*left == y) {
        y->p->*left = x;
      }
      else {
        y->p->*right = x;
      }
    }
    else {
      this->setHead(x);
    }

    y->p = x;
    y->*left = x->*right;

    if(x->*right != nullptr) {
      (x->*right)->p = y;
    }

    x->*right = y;
    y->dl = y->calcd('l');
    x->dr = x->calcd('r');
    if(x->p != nullptr) {
      if(x->p->*left == x) {
        x->p->dl = x->p->calcd('l');
      }
      else {
        x->p->dr = x->p->calcd('r');
      }
   }
}

void avl<T>::rotate(node<T> *x, node<T> *y)
{
  if (x == y->l) {
    rotate_impl(x, y, &node<T>::l, &node<T>::r);
  }
  else {
    rotate_impl(x, y, &node<T>::r, &node<T>::l);
  }
}

我还冒昧地在您的代码中添加了大括号。你可以稍后再感谢我。

Answer 4

我喜欢 Mike 的模板方法。但为了记录，我在这里提出另一种选择。

首先，考虑每个节点有两个children。称他们为"left"和"right"只是一种心态。您也可以将它们放在一个数组中：

template <class T>
class node {
public: 
    ...
    enum side{ left,right,last};   // just to make clear my intent here
    node *p, *c[last], *d[last];   // no more l and r !!         
    node* calcd(enum side x) {}    // lets use our index here instead of char  
    ...
};

然后你可以分解出依赖于边的代码。我喜欢 lambda，所以这是第一个提议：

template <class T>
void avl<T>::rotate(node<T> *x, node<T> *y)
{
    // this lambda works directly with locals of rotate() thanks to [&]
    // so put in the side dependent code, and put the side as parameter
    // for easy switch.  For simplicity I used l and r to facilitate
    // transposition, but reafctoring it in a neutral side1 and sinde2 
    // could help readbility
    auto rt = [&](enum node<T>::side l, enum node<T>::side r)->void {
        x->p = y->p;
        if (y->p != nullptr)
            if(y->p->c[l] == y)   // l is a parameter here instead of member name
                y->p->c[l] = x;
            else
                y->p->c[r] = x;
        else
            this->setHead(x);
        y->p = x;
        y->c[l] = x->c[r];
        if (x == y->c[l])
        {
            if(x->c[r] != nullptr)
                x->c[r]->p = y;
            x->c[r] = y;
            y->d[l] = y->calcd(sd[l]);
            x->d[r] = x->calcd(sd[r]);
            if(x->p != nullptr)
                if(x->p->c[l] == x)
                    x->p->d[l] = x->p->calcd(sd[l]);
                else
                    x->p->d[r] = x->p->calcd(sd[r]);
        }
    }; // end of the definition of the lambda

  // the code of the function is then reduced to this:  
  if (x == y->c[node<T>::left])
     rt(node<T>::left,node<T>::right);
  else
     rt(node<T>::right, node<T>::left); 
}

是否可以组合对称代码段？

Is it possible combining symmetric code pieces?

c++

oop

tree

encapsulation

avl-tree