Day-Stout-Warren algorithm

Day-Stout-Warren algorithm

このアルゴリズムを使うと木を balance させるタイミングを制御できるので、何か特殊用途に使えるんじゃないかと思って実装してみることに。C++ だと以下のような感じ。

#include <memory>
#include <cstdio>
#include <cinttypes>
#include <cmath>

template <typename T>
class Tree
{
public:
  struct Node {
    T value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;

    explicit Node(T value) : value(value), left(nullptr), right(nullptr) {}

    Node(T value, std::unique_ptr<Node>&& l, std::unique_ptr<Node>&& r)
        : value(value), left(std::move(l)), right(std::move(r)) {}
  };
  
  Tree() : root_(nullptr), size_(0) {}

  ~Tree() = default;

  Tree(const Tree& other)
      : root_(copy(other.root_))
      , size_(other.size_) {}

  Tree(Tree&& other)
      : root_(std::move(other.root_))
      , size_(std::move(other.size_)) {}

  Tree& operator=(const Tree& other)
  {
    Tree<T> t(other);
    std::swap(root_, t.root_);
    std::swap(size_, t.size_);
    return *this;
  }

  Tree& operator=(Tree&& other)
  {
    std::swap(root_, other.root_);
    std::swap(size_, other.size_);
    return *this;
  }

  std::size_t size() const
  {
    return size_;
  }

  void insert(T value)
  {
    root_ = insert(root_, value, &size_);
  }
  
  void balance()
  {
    std::unique_ptr<Node> t(new Node(T()));
    t->right = std::move(root_);
    toVine(t);
    toTree(t, size_ + 1);
    root_ = std::move(t->right);
  }

  std::size_t height() const
  {
    return height(root_, 0);
  }

  template<typename F>
  void walk(F&& f) const
  {
    walk(root_, f);
  }
  
private:
  std::unique_ptr<Node> copy(const std::unique_ptr<Node>& node)
  {
    if (!node) return nullptr;
    return std::make_unique<Node>(node->value, copy(node->left), copy(node->right));
  }
  
  std::size_t height(const std::unique_ptr<Node>& node, std::size_t h) const
  {
    if (node == nullptr)
      return h;
    
    return std::max(height(node->left, h + 1), height(node->right, h + 1));
  }
  
  template <typename F>
  void walk(const std::unique_ptr<Node>& node, F&& f) const
  {
    if (node == nullptr)
      return;
    
    if (node->left) {
      walk(node->left, f);
    }
    
    f(node->value);
    
    if (node->right) {
      walk(node->right, f);
    }
  }
  
  std::unique_ptr<Node> insert(std::unique_ptr<Node>& node, T value, std::size_t *size)
  {
    if (node == nullptr) {
      *size = *size + 1;
      return std::make_unique<Node>(value); 
    }
    
    if (node->value < value) {
      node->right = insert(node->right, value, size);
      return std::move(node);
    } else {
      node->left = insert(node->left, value, size);
      return std::move(node);
    }
  }
  
  void toVine(std::unique_ptr<Node>& root)
  {
    Node* tail = root.get();
    Node* rest = tail->right.get();
    
    while (rest != nullptr) {
      if (rest->left == nullptr) {
        tail = rest;
        rest = rest->right.get();
      } else {
        auto temp   = std::move(rest->left);
        rest->left  = std::move(temp->right);
        temp->right = std::move(tail->right);
        rest        = temp.get();
        tail->right = std::move(temp);
      }
    }
  }

  void toTree(std::unique_ptr<Node>& root, std::size_t size)
  {
    std::size_t leaves = size + 1 - std::pow(2, std::floor(std::log2(size + 1)));
    compress(root, leaves);
    size = size - leaves;
    while (size > 1) {
      compress(root, std::floor(size / 2));
      size = std::floor(size / 2);
    }
  }

  void compress(std::unique_ptr<Node>& root, std::size_t count)
  {
    auto scanner = root.get();
    for (std::size_t i = 0; i < count; ++i) {
      auto child = std::move(scanner->right);
      scanner->right = std::move(child->right);
      scanner = scanner->right.get();
      child->right = std::move(scanner->left);
      scanner->left = std::move(child);
    }
  }
  
  std::unique_ptr<Node> root_;
  std::size_t size_;
};

void setup(Tree<int>& tree)
{
  tree.insert(5);
  tree.insert(6);
  tree.insert(7);
  tree.insert(8);
  tree.insert(9);
  tree.insert(20);
  tree.insert(24);
  tree.insert(27);
  tree.insert(33);
}

int main( void )
{
  using namespace std;
  Tree<int> tree;
  auto dump = [](int n) { printf("%d ", n); };

  setup(tree);

  printf("Before balancing: size is %zu, height is %zu\n", tree.size(), tree.height());

  tree.walk(dump);

  printf("\n");

  // test copy constructor and move constructor here.
  Tree<int> tree2(std::move(tree));

  tree2.balance();

  printf("After balancing: size is %zu, height is %zu\n", tree2.size(), tree2.height());

  Tree<int>(tree2).walk(dump);

  printf("\n");

  return 0;
}

Comments

comments powered by Disqus