트립 구현해보기

2025년 6월 6일

#problem-solving #computer-science #ruby #c #cpp

트립을 써보자

트립(Treap)은 이진 탐색 트리(BST)와 힙(Heap)의 특성을 결합한 자료구조입니다.
사실 태생적으로는 힙이지만, 이진 탐색 트리처럼 동작하도록 만든 짝퉁에 가깝습니다.

일반적으로 이진 탐색 트리는 그나마 만만한 스플레이 트리(Splay Tree)나 레드-블랙 트리(Red-Black Tree)조차도
구현이 복잡한데, 트립은 급하게 이런 것들이 필요할 때 사용할 수 있는 간단한 대안입니다.

트립의 특징

트립은 다음과 같은 특징을 가지고 있습니다:

이진 탐색 트리: 왼쪽 서브트리는 루트보다 작은 값, 오른쪽 서브트리는 큰 값을 가집니다.
힙: 각 노드는 자식 노드보다 우선순위가 높습니다. 즉, 부모 노드의 우선순위가 자식 노드의 우선순위보다 큽니다.
랜덤성: 노드의 우선순위는 랜덤하게 할당되어, 트립의 구조가 균형을 이루도록 합니다.
삽입, 삭제, 검색: O(log n)의 시간복잡도로 수행할 수 있습니다.

트립의 구현

간단한 트립의 구현을 C++로 짜면 다음과 같습니다:

template<typename T>
class treap {
    struct _node {
        T key;
        size_t priority, size;
        _node *left, *right;
        
        _node(T k) : key(k), priority(rand()), size(1), left(nullptr), right(nullptr) {}
 
        void update() {
            size = 1 + (left ? left->size : 0) + (right ? right->size : 0);
        }
 
        void set_left(_node *l) {
            left = l;
            update();
        }
 
        void set_right(_node *r) {
            right = r;
            update();
        }
    }
 
    _node *root;
    typedef ::std::pair<_node*, _node*> _split_result;
 
    _split_result _split(_node *node, T key) { // 노드를 key를 기준으로 분할
        if (!node) return {nullptr, nullptr};
        if (node->key < key) {
            auto [l, r] = split(node->right, key);
            node->set_right(l);
            return {node, r};
        }
        auto [l, r] = split(node->left, key);
        node->set_left(r);
        return {l, node};
    }
 
    _node* _merge(_node *left, _node *right) { // 두 노드를 병합, left 서브트리는 모든 노드가 right 서브트리보다 작음
        if (!left || !right) return left ? left : right;
        if (left->priority < right->priority) {
            right->set_left(_merge(left, right->left));
            return right;
        }
        left->set_right(_merge(left->right, right));
        return left;
    }
 
    _node* _insert(_node *parent, _node *node) {
        if (!parent) return node;
        if (node->priority > parent->priority) {
            auto [l, r] = _split(parent, node->key);
            node->set_left(l);
            node->set_right(r);
            return node;
        }
        if (node->key < parent->key) {
            parent->set_left(_insert(parent->left, node));
        } else {
            parent->set_right(_insert(parent->right, node));
        }
        return parent;
    }
 
    _node* _erase(_node *parent, T key) {
        if (!parent) return nullptr;
        if (key < parent->key) {
            parent->set_left(_erase(parent->left, key));
        } else if (key > parent->key) {
            parent->set_right(_erase(parent->right, key));
        } else {
            _node *merged = _merge(parent->left, parent->right);
            delete parent;
            return merged;
        }
        return parent;
    }
 
    _node* _kth(_node *node, size_t k) {
        if (!node || k >= node->size) return nullptr;
        size_t left_size = node->left ? node->left->size : 0;
        if (k < left_size) {
            return _kth(node->left, k);
        } else if (k > left_size) {
            return _kth(node->right, k - left_size - 1);
        }
        return node;
    }
 
    size_t _count_less(_node *node, T key) {
        if (!node) return 0;
        if (key <= node->key) {
            return _count_less(node->left, key);
        }
        return (node->left ? node->left->size : 0) + 1 + _count_less(node->right, key);
    }
 
public:
    treap<T>() : root(nullptr) {}
 
    bool empty() const {
        return root == nullptr;
    }
 
    size_t size() const {
        return root ? root->size : 0;
    }
 
    void insert(const T &key) {
        _node *new_node = new _node(key);
        root = _insert(root, new_node);
    }
 
    void erase(const T &key) {
        root = _erase(root, key);
    }
    
    _node* find(const T &key) {
        _node *current = root;
        while (current) {
            if (key < current->key) {
                current = current->left;
            } else if (key > current->key) {
                current = current->right;
            } else {
                return current;
            }
        }
        return nullptr;
    }
 
    _node* kth(size_t k) {
        return _kth(root, k);
    }
 
    size_t count_less(const T &key) {
        return _count_less(root, key);
    }
}

생각해보니 C++은 std::set을 쓰면 되니까 굳이 트립을 구현할 필요는 없겠네요.
그래서 C에서 매크로를 이용한 트립 구현과, Ruby의 클래스로 구현한 트립입니다.

#define DEFINE_TREAP(TypeName, KeyType) \
    typedef struct treap_node_##TypeName { \
        KeyType key; \
        int priority; \
        int size; \
        struct treap_node_##TypeName *left, *right; \
    } treap_node_##TypeName; \
    \
    typedef struct treap_##TypeName { \
        treap_node_##TypeName *root; \
    } treap_##TypeName; \
    \
    typedef struct treap_split_result_##TypeName { \
        treap_node_##TypeName *first; \
        treap_node_##TypeName *second; \
    } treap_split_result_##TypeName; \
    \
    /* Forward declarations for internal static functions */ \
    static treap_node_##TypeName* _treap_node_new_##TypeName(KeyType k); \
    static void _treap_node_update_##TypeName(treap_node_##TypeName *node); \
    static void _treap_node_set_left_##TypeName(treap_node_##TypeName *node, treap_node_##TypeName *l); \
    static void _treap_node_set_right_##TypeName(treap_node_##TypeName *node, treap_node_##TypeName *r); \
    static treap_split_result_##TypeName _treap_split_##TypeName(treap_node_##TypeName *node, KeyType key); \
    static treap_node_##TypeName* _treap_merge_##TypeName(treap_node_##TypeName *left_node, treap_node_##TypeName *right_node); \
    static treap_node_##TypeName* _treap_insert_internal_##TypeName(treap_node_##TypeName *parent, treap_node_##TypeName *new_node_to_insert); \
    static treap_node_##TypeName* _treap_erase_internal_##TypeName(treap_node_##TypeName *parent, KeyType key); \
    static treap_node_##TypeName* _treap_kth_internal_##TypeName(treap_node_##TypeName *node, int k); \
    static int _treap_count_less_internal_##TypeName(treap_node_##TypeName *node, KeyType key); \
    \
    /* Function implementations */ \
    static treap_node_##TypeName* _treap_node_new_##TypeName(KeyType k) { \
        treap_node_##TypeName *new_node = (treap_node_##TypeName*)malloc(sizeof(treap_node_##TypeName)); \
        if (!new_node) { \
            /* fprintf(stderr, "Memory allocation failed for new treap node\n"); */ \
            return NULL; \
        } \
        new_node->key = k; \
        new_node->priority = rand(); \
        new_node->size = 1; \
        new_node->left = NULL; \
        new_node->right = NULL; \
        return new_node; \
    } \
    \
    static void _treap_node_update_##TypeName(treap_node_##TypeName *node) { \
        if (!node) return; \
        node->size = 1 + (node->left ? node->left->size : 0) + (node->right ? node->right->size : 0); \
    } \
    \
    static void _treap_node_set_left_##TypeName(treap_node_##TypeName *node, treap_node_##TypeName *l) { \
        if (!node) return; \
        node->left = l; \
        _treap_node_update_##TypeName(node); \
    } \
    \
    static void _treap_node_set_right_##TypeName(treap_node_##TypeName *node, treap_node_##TypeName *r) { \
        if (!node) return; \
        node->right = r; \
        _treap_node_update_##TypeName(node); \
    } \
    \
    static treap_split_result_##TypeName _treap_split_##TypeName(treap_node_##TypeName *node, KeyType key) { \
        if (!node) return (treap_split_result_##TypeName){NULL, NULL}; \
        if (node->key < key) { \
            treap_split_result_##TypeName res = _treap_split_##TypeName(node->right, key); \
            _treap_node_set_right_##TypeName(node, res.first); \
            return (treap_split_result_##TypeName){node, res.second}; \
        } \
        treap_split_result_##TypeName res = _treap_split_##TypeName(node->left, key); \
        _treap_node_set_left_##TypeName(node, res.second); \
        return (treap_split_result_##TypeName){res.first, node}; \
    } \
    \
    static treap_node_##TypeName* _treap_merge_##TypeName(treap_node_##TypeName *left_node, treap_node_##TypeName *right_node) { \
        if (!left_node || !right_node) return left_node ? left_node : right_node; \
        if (left_node->priority < right_node->priority) { \
            _treap_node_set_left_##TypeName(right_node, _treap_merge_##TypeName(left_node, right_node->left)); \
            return right_node; \
        } \
        _treap_node_set_right_##TypeName(left_node, _treap_merge_##TypeName(left_node->right, right_node)); \
        return left_node; \
    } \
    \
    static treap_node_##TypeName* _treap_insert_internal_##TypeName(treap_node_##TypeName *parent, treap_node_##TypeName *new_node_to_insert) { \
        if (!parent) return new_node_to_insert; \
        if (new_node_to_insert->priority > parent->priority) { \
            treap_split_result_##TypeName res = _treap_split_##TypeName(parent, new_node_to_insert->key); \
            _treap_node_set_left_##TypeName(new_node_to_insert, res.first); \
            _treap_node_set_right_##TypeName(new_node_to_insert, res.second); \
            return new_node_to_insert; \
        } \
        if (new_node_to_insert->key < parent->key) { \
            _treap_node_set_left_##TypeName(parent, _treap_insert_internal_##TypeName(parent->left, new_node_to_insert)); \
        } else { \
            _treap_node_set_right_##TypeName(parent, _treap_insert_internal_##TypeName(parent->right, new_node_to_insert)); \
        } \
        return parent; \
    } \
    \
    static treap_node_##TypeName* _treap_erase_internal_##TypeName(treap_node_##TypeName *parent, KeyType key) { \
        if (!parent) return NULL; \
        if (key < parent->key) { \
            _treap_node_set_left_##TypeName(parent, _treap_erase_internal_##TypeName(parent->left, key)); \
        } else if (key > parent->key) { \
            _treap_node_set_right_##TypeName(parent, _treap_erase_internal_##TypeName(parent->right, key)); \
        } else { \
            treap_node_##TypeName *merged_children = _treap_merge_##TypeName(parent->left, parent->right); \
            free(parent); \
            return merged_children; \
        } \
        return parent; \
    } \
    \
    static treap_node_##TypeName* _treap_kth_internal_##TypeName(treap_node_##TypeName *node, int k) { \
        if (!node || k >= node->size) return NULL; \
        int left_size = node->left ? node->left->size : 0; \
        if (k < left_size) { \
            return _treap_kth_internal_##TypeName(node->left, k); \
        } else if (k > left_size) { \
            return _treap_kth_internal_##TypeName(node->right, k - left_size - 1); \
        } \
        return node; \
    } \
    \
    static int _treap_count_less_internal_##TypeName(treap_node_##TypeName *node, KeyType key) { \
        if (!node) return 0; \
        if (key <= node->key) { \
            return _treap_count_less_internal_##TypeName(node->left, key); \
        } \
        return (node->left ? node->left->size : 0) + 1 + _treap_count_less_internal_##TypeName(node->right, key); \
    } \
    \
    static void _treap_node_free_##TypeName(treap_node_##TypeName *node) { \
        if (!node) return; \
        _treap_node_free_##TypeName(node->left); \
        _treap_node_free_##TypeName(node->right); \
        free(node); \
    } \
    /* Public interface functions */ \
    static void treap_destroy_##TypeName(treap_##TypeName *t) { \
        if (!t) return; \
        _treap_node_free_##TypeName(t->root); \
        t->root = NULL; \
    } \
    \
    static void treap_init_##TypeName(treap_##TypeName *t) { \
        if (t) t->root = NULL; \
    } \
    \
    static int treap_empty_##TypeName(const treap_##TypeName *t) { \
        return !t || t->root == NULL; \
    } \
    \
    static int treap_size_##TypeName(const treap_##TypeName *t) { \
        return (t && t->root) ? t->root->size : 0; \
    } \
    \
    static void treap_insert_##TypeName(treap_##TypeName *t, KeyType key) { \
        if (!t) return; \
        treap_node_##TypeName *new_node = _treap_node_new_##TypeName(key); \
        if (!new_node) return; /* Allocation failed, _treap_node_new_ handles message */ \
        t->root = _treap_insert_internal_##TypeName(t->root, new_node); \
    } \
    \
    static void treap_erase_##TypeName(treap_##TypeName *t, KeyType key) { \
        if (!t) return; \
        t->root = _treap_erase_internal_##TypeName(t->root, key); \
    } \
    \
    static treap_node_##TypeName* treap_find_##TypeName(treap_##TypeName *t, KeyType key) { \
        if (!t) return NULL; \
        treap_node_##TypeName *current = t->root; \
        while (current) { \
            if (key < current->key) { \
                current = current->left; \
            } else if (key > current->key) { \
                current = current->right; \
            } else { \
                return current; \
            } \
        } \
        return NULL; \
    } \
    \
    static treap_node_##TypeName* treap_kth_##TypeName(treap_##TypeName *t, int k) { \
        if (!t) return NULL; \
        return _treap_kth_internal_##TypeName(t->root, k); \
    } \
    \
    static int treap_count_less_##TypeName(treap_##TypeName *t, KeyType key) { \
        if (!t) return 0; \
        return _treap_count_less_internal_##TypeName(t->root, key); \
    }

class Treap
  class Node
    attr_accessor :key, :priority, :size, :left, :right
 
    def initialize(key)
      @key = key
      @priority = rand(0..1_000_000_000) # Large range for priorities
      @size = 1
      @left = nil
      @right = nil
    end
 
    def update_size
      @size = 1 + (@left ? @left.size : 0) + (@right ? @right.size : 0)
    end
 
    # Helper to avoid direct access and ensure size update
    def set_left(node)
      @left = node
      update_size
    end
 
    def set_right(node)
      @right = node
      update_size
    end
  end
 
  attr_accessor :root
 
  def initialize
    @root = nil
  end
 
  def empty?
    @root.nil?
  end
 
  def size
    @root ? @root.size : 0
  end
 
  def insert(key)
    new_node = Node.new(key)
    @root = _insert(@root, new_node)
  end
 
  def erase(key)
    @root = _erase(@root, key)
  end
 
  def find(key)
    current = @root
    while current
      if key < current.key
        current = current.left
      elsif key > current.key
        current = current.right
      else
        return current # Or current.key if you just want the value
      end
    end
    nil
  end
 
  def kth(k) # 0-indexed
    _kth(@root, k)
  end
 
  def count_less(key)
    _count_less(@root, key)
  end
 
  private
 
  # Returns [left_subtree, right_subtree]
  def _split(node, key)
    return [nil, nil] unless node
 
    if node.key < key
      left_subtree, right_subtree = _split(node.right, key)
      node.set_right(left_subtree)
      [node, right_subtree]
    else
      left_subtree, right_subtree = _split(node.left, key)
      node.set_left(right_subtree)
      [left_subtree, node]
    end
  end
 
  def _merge(left_node, right_node)
    return right_node unless left_node
    return left_node unless right_node
 
    if left_node.priority < right_node.priority
      right_node.set_left(_merge(left_node, right_node.left))
      right_node
    else
      left_node.set_right(_merge(left_node.right, right_node))
      left_node
    end
  end
 
  def _insert(parent, node_to_insert)
    return node_to_insert unless parent
 
    if node_to_insert.priority > parent.priority
      left_subtree, right_subtree = _split(parent, node_to_insert.key)
      node_to_insert.set_left(left_subtree)
      node_to_insert.set_right(right_subtree)
      node_to_insert
    elsif node_to_insert.key < parent.key
      parent.set_left(_insert(parent.left, node_to_insert))
      parent
    else # node_to_insert.key >= parent.key (handle duplicates by inserting to the right, or disallow)
      parent.set_right(_insert(parent.right, node_to_insert))
      parent
    end
  end
 
  def _erase(parent, key)
    return nil unless parent
 
    if key < parent.key
      parent.set_left(_erase(parent.left, key))
    elsif key > parent.key
      parent.set_right(_erase(parent.right, key))
    else # key == parent.key
      merged_children = _merge(parent.left, parent.right)
      return merged_children
    end
    parent # Return parent if key was not found in this branch or after updating children
  end
 
  def _kth(node, k) # 0-indexed
    return nil if !node || k >= node.size
 
    left_size = node.left ? node.left.size : 0
 
    if k < left_size
      _kth(node.left, k)
    elsif k > left_size
      _kth(node.right, k - left_size - 1)
    else # k == left_size
      node
    end
  end
 
  def _count_less(node, key)
    return 0 unless node
 
    if key <= node.key 
      _count_less(node.left, key)
    else
      (node.left ? node.left.size : 0) + 1 + _count_less(node.right, key)
    end
  end
end

구현의 포인트

우선순위: 트립의 핵심은 각 노드에 우선순위를 부여하여 힙의 특성을 유지하는 것입니다.
이 우선순위는 삽입 시 랜덤하게 할당됩니다.
분할과 병합: 트립은 노드를 분할하고 병합하는 연산을 통해 삽입과 삭제를 수행합니다.
크기 관리: 각 노드는 자신의 서브트리의 크기를 관리하여, k번째 원소를 찾거나 특정 값보다 작은 원소의 개수를 계산할 수 있습니다.

여러 기능을 추가할 수 있지만, 삽입, 삭제, 검색, k번째 원소 찾기, 특정 값보다 작은 원소의 개수 세기 등의 기능만 구현했습니다.

사용 예시

위의 Ruby 구현체를 예시로 들자면 다음과 같습니다.

treap = Treap.new
treap.insert(5)
treap.insert(3)
treap.insert(8)
puts treap.find(3).key # 3
puts treap.kth(1).key # 5 (0-indexed, 1번째 원소)
puts treap.count_less(6) # 2 (5보다 작은 원소의 개수)
treap.erase(3)
puts treap.find(3) # nil (3은 삭제되었으므로)

이렇게 트립을 사용해서, 가짜지만 이진 탐색 트리처럼 동작하는 자료구조를 구현할 수 있습니다.

트립의 문제점

트립은 이진 탐색 트리보다야 간단한 구현이지만, 랜덤성이라는 태생적인 문제를 안고 있습니다.
삽입 시 우선순위를 랜덤하게 할당하기 때문에, 최악의 경우 트립이 편향된 구조로 변할 수 있습니다.
이런 경우에는 삽입, 삭제, 검색의 시간복잡도가 O(n)으로 증가할 수 있습니다.

따라서, 최악의 경우를 상정해야 하는 상황이라면 복잡해도 울며 겨자 먹기로 스플레이 트리나 레드-블랙 트리, AVL 트리 등을 사용하는 것이 좋습니다.

결론

그나마 간단?한 이진 탐색 트리인 트립은 급하게 이진 탐색 트리가 필요할 때 사용할 수 있는 자료구조입니다.

그렇다고 해서 만능인 것은 아니며, 최악의 경우를 고려해야 하는 상황에서는 사용을 피하는 것이 좋습니다. 또 상대적으로 간단하기야 하지만 구현이 복잡한 편이므로, 자신이 사용하는 언어의 표준 라이브러리에서 제공하는 이진 탐색 트리를 사용하는 것이 더 나을 수 있습니다.

결국 간단하게 커스텀하여 사용할 수 있는 이진 탐색 트리의 대안 정도로 생각하면 될 것 같습니다.