NIL в красно-черном дереве?

Question

[doublench21]

В Кормене, алгоритм добавления содержит значение NIL, а в алгоритме удаление говорится о sentinal(NIL);

class Node {
Node *left;
Node *right;
Node *parrent;
color color;
}

Как я понял, NIL: NULL, NULL, NULL, BLACK;
А что ж тогда sentinal(NIL) ?
И верно ли, что новый узел - это: NIL, NIL, NULL, RED ? (до самой собственно вставки)

Реализовал алгоритмы из Кормена, а программа ругается в различных местах именно на сравнениях с NIL. Bad addres 0x0...

Помогите пожалуйста. Исходник немного немаленький, но могу и его выложить.

Answer 1

[Mercury13]

Исходник, конечно, дай — посмотрим, что там можно сделать. Как вариант, можно сделать так.

Node nullNode = { NULL, NULL, NULL, BLACK };
class NodeHandle {
private:
  Node* data;
  Node* getData() const { return data ?data : &nullNode; }
public:
  NodeHandle() : data(&nullNode) {}
  NodeHandle(Node* x) : data(x) {}
  NodeHandle& operator=(Node* x) { data = x; return *this; }
  bool operator == (const Node* x) const { return (data == x); }
  bool operator != (const Node* x) const { return (data != x); }
  bool operator == (const NodeHandle& x) const { return (data == x.data); }
  bool operator != (const NodeHandle& x) const { return (data != x.data); }
  Node* operator ->() const { return getData(); }
  Node& operator *() const { return *getData(); }
  operator Node*() const { return getData(); }
}

Но, думаю, всё же где-то вкралась ошибка.

Answer 2

[doublench21]

Mercury13 , вообщем все и вправду было в этом NILL. Плюс я ни разу не использовал this, а видимо стоило, как я позже понял. Исходники:

//
//  rbtree.h
//  rbtreee
//
//  Created by Lutfullin Ruslan on 23.04.15.
//  Copyright (c) 2015 Ruslan Lutfullin. All rights reserved.
//

#ifndef __rbtreee__rbtree__
#define __rbtreee__rbtree__

#include <stdio.h>

enum color { RED, BLACK };

class Node {
public:
  int data;
  color color;
  Node *left;
  Node *right;
  Node *parrent;

public:
  Node(int data)
      : left(NULL), right(NULL), parrent(NULL), color(RED), data(data){};

  virtual ~Node(){};

public:
  friend class RBtree;
};

class RBtree {
public:
  Node *root;
  Node *NIL;

public:
  RBtree();
  virtual ~RBtree();

public:
  void tree_insert(Node *n);
  void left_rotate(Node *n);
  void right_rotate(Node *n);
  void rb_insert(Node *n);
  Node *rb_delete(Node *n);
  void rb_delete_fixup(Node *n);
  Node *tree_successor(Node *n);
  Node *tree_predecessor(Node *n);
  void inorder_tree_walk(Node *n);
  Node *iterative_tree_search(Node *n, int data);
  Node *tree_minimum(Node *n);
  Node *tree_maximum(Node *n);

  class Iterator {};
};

#endif /* defined(__rbtreee__rbtree__) */

//
//  rbtree.cpp
//  rbtreee
//
//  Created by Lutfullin Ruslan on 23.04.15.
//  Copyright (c) 2015 Ruslan Lutfullin. All rights reserved.
//

#include "rbtree.h"
#include <iostream>

RBtree::RBtree() {
  this->NIL = new Node(-1);
  this->NIL->color = BLACK;
  this->NIL->left = this->NIL->right = this->NIL->parrent = this->NIL;

  this->root = this->NIL;
  this->root->color = BLACK;
}

RBtree::~RBtree() { delete this->root; }

void RBtree::inorder_tree_walk(Node *n) {
  if (n != this->NIL) {
    this->inorder_tree_walk(n->left);
    std::cout << n->data << " ";
    this->inorder_tree_walk(n->right);
  }
}

Node *RBtree::iterative_tree_search(Node *n, int data) {
  while (n != this->NIL && data != n->data) {
    if (data < n->data) {
      n = n->left;
    } else {
      n = n->right;
    }
  }
  return n;
}

Node *RBtree::tree_minimum(Node *n) {
  while (n->left != this->NIL) {
    n = n->left;
  }
  return n;
}

Node *RBtree::tree_maximum(Node *n) {
  while (n->right != this->NIL) {
    n = n->right;
  }
  return n;
}

Node *RBtree::tree_successor(Node *n) {
  if (n->right != this->NIL) {
    return this->tree_minimum(n->right);
  }
  Node *y = n->parrent;
  while (y != this->NIL && n == y->right) {
    n = y;
    y = y->parrent;
  }
  return y;
}

Node *RBtree::tree_predecessor(Node *n) {
  if (n->left != this->NIL) {
    return this->tree_minimum(n->left);
  }
  Node *y = n->parrent;
  while (y != this->NIL && n == y->left) {
    n = y;
    y = y->parrent;
  }
  return y;
}

void RBtree::tree_insert(Node *z) {
  Node *y = this->NIL, *x = this->root;
  while (x != this->NIL) {
    y = x;
    if (z->data < x->data)
      x = x->left;
    else
      x = x->right;
  }
  z->parrent = y;
  if (y == this->NIL) {
    this->root = z;
  } else {
    if (z->data < y->data) {
      y->left = z;
    } else {
      y->right = z;
    }
  }
}

void RBtree::left_rotate(Node *x) {
  Node *y;
  y = x->right;
  x->right = y->left;
  if (y->left != this->NIL) {
    y->left->parrent = x;
  }
  y->parrent = x->parrent;
  if (x->parrent == this->NIL) {
    this->root = y;
  } else {
    if (x == x->parrent->left) {
      x->parrent->left = y;
    } else {
      x->parrent->right = y;
    }
  }
  y->left = x;
  x->parrent = y;
}

void RBtree::right_rotate(Node *y) {
  Node *x;
  x = y->left;
  y->left = x->right;
  if (x->right != this->NIL) {
    x->right->parrent = y;
  }
  x->parrent = y->parrent;
  if (y->parrent == this->NIL) {
    this->root = x;
  } else {
    if (y == y->parrent->left) {
      y->parrent->left = x;
    } else {
      y->parrent->right= x;
    }
  }
  x->right = y;
  y->parrent = x;
}

void RBtree::rb_insert(Node *z) {

  this->tree_insert(z);
  Node *y;
  z->left = z->right = this->NIL;
  z->color = RED;
  while (z != this->root && z->parrent->color == RED) {
    if (z->parrent == z->parrent->parrent->left) {
      y = z->parrent->parrent->right;
      if (y->color == RED) {
        z->parrent->color = BLACK;
        y->color = BLACK;
        z->parrent->parrent->color = RED;
        z = z->parrent->parrent;
      } else {
        if (z == z->parrent->right) {
          z = z->parrent;
          this->left_rotate(z);
        }
        z->parrent->color = BLACK;
        z->parrent->parrent->color = RED;
        this->right_rotate(z->parrent->parrent);
      }
    } else {
      y = z->parrent->parrent->left;
      if (y->color == RED) {
        z->parrent->color = BLACK;
        y->color = BLACK;
        z->parrent->parrent->color = RED;
        z = z->parrent->parrent;
      } else {
        if (z == z->parrent->left) {
          z = z->parrent;
          this->right_rotate(z);
        }
        z->parrent->color = BLACK;
        z->parrent->parrent->color = RED;
        this->left_rotate(z->parrent->parrent);
      }
    }
  }
  this->root->color = BLACK;
}

Node *RBtree::rb_delete(Node *z) {
  Node *x, *y;
  if (z->left == this->NIL || z->right == this->NIL) {
    y = z;
  } else {
    y = this->tree_successor(z);
  }
  if (y->left != this->NIL) {
    x = y->left;
  } else {
    x = y->right;
  }
  x->parrent = y->parrent;
  if (y->parrent == this->NIL) {
    this->root = x;
  } else {
    if (y == y->parrent->left) {
      y->parrent->left = x;
    } else {
      y->parrent->right = x;
    }
  }
  if (y != z) {
    z->data = y->data;
  }
  if (y->color == BLACK) {
    this->rb_delete_fixup(x);
  }
  return y;
}

void RBtree::rb_delete_fixup(Node *x) {
  Node *w;
  while (x != this->root && x->color == BLACK) {
    if (x == x->parrent->left) {
      w = x->parrent->right;
      if (w->color == RED) {
        w->color = BLACK;
        x->parrent->color = RED;
        this->left_rotate(x->parrent);
        w = x->parrent->right;
      }
      if (w->left->color == BLACK && w->right->color == BLACK) {
        w->color = RED;
        x = x->parrent;
      } else {
        if (w->right->color == BLACK) {
          w->left->color = BLACK;
          w->color = RED;
          this->right_rotate(w);
          w = x->parrent->right;
        }
        w->color = x->parrent->color;
        x->parrent->color = BLACK;
        w->right->color = BLACK;
        this->left_rotate(x->parrent);
        x = this->root;
      }
    } else {
      w = x->parrent->left;
      if (w->color == RED) {
        w->color = BLACK;
        x->parrent->color = RED;
        this->left_rotate(x->parrent);
        w = x->parrent->left;
      }
      if (w->right->color == BLACK && w->left->color == BLACK) {
        w->color = RED;
        x = x->parrent;
      } else {
        if (w->left->color == BLACK) {
          w->right->color = BLACK;
          w->color = RED;
          this->right_rotate(w);
          w = x->parrent->left;
        }
        w->color = x->parrent->color;
        x->parrent->color = BLACK;
        w->left->color = BLACK;
        this->left_rotate(x->parrent);
        x = this->root;
      }
    }
  }
  x->color = BLACK;
}

Comments

[Mercury13]

Я говорил про nullNode лишь как про попытку экстренно исправить код. Обычно так не делают, nil — это null, NULL или nullptr.

Вылетает именно на этом коде?