Solidity: RBT 구현 예제

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

/**
 * Red-Black Tree in Solidity (확장 버전)
 * - Self-balancing binary search tree
 * - Insert, Delete, Min/Max, Exists, In-order, Range Query 지원
 */

library RedBlackTreeLib {
    uint private constant NULL = 0;

    struct Node {
        uint parent;
        uint left;
        uint right;
        bool red;
        bool exists;
    }

    struct Tree {
        mapping(uint => Node) nodes;
        uint root;
    }

    function insert(Tree storage self, uint key) internal {
        require(key != NULL, "invalid key");
        require(!self.nodes[key].exists, "already exists");

        uint cursor = self.root;
        uint parent = NULL;

        while (cursor != NULL) {
            parent = cursor;
            if (key < cursor) {
                cursor = self.nodes[cursor].left;
            } else {
                cursor = self.nodes[cursor].right;
            }
        }

        self.nodes[key] = Node({ parent: parent, left: NULL, right: NULL, red: true, exists: true });

        if (parent == NULL) {
            self.root = key;
        } else if (key < parent) {
            self.nodes[parent].left = key;
        } else {
            self.nodes[parent].right = key;
        }

        insertFixup(self, key);
    }

    function insertFixup(Tree storage self, uint key) private {
        while (key != self.root && self.nodes[self.nodes[key].parent].red) {
            uint parent = self.nodes[key].parent;
            uint grandparent = self.nodes[parent].parent;

            if (parent == self.nodes[grandparent].left) {
                uint uncle = self.nodes[grandparent].right;
                if (self.nodes[uncle].red) {
                    self.nodes[parent].red = false;
                    self.nodes[uncle].red = false;
                    self.nodes[grandparent].red = true;
                    key = grandparent;
                } else {
                    if (key == self.nodes[parent].right) {
                        key = parent;
                        rotateLeft(self, key);
                        parent = self.nodes[key].parent;
                    }
                    self.nodes[parent].red = false;
                    self.nodes[grandparent].red = true;
                    rotateRight(self, grandparent);
                }
            } else {
                uint uncle = self.nodes[grandparent].left;
                if (self.nodes[uncle].red) {
                    self.nodes[parent].red = false;
                    self.nodes[uncle].red = false;
                    self.nodes[grandparent].red = true;
                    key = grandparent;
                } else {
                    if (key == self.nodes[parent].left) {
                        key = parent;
                        rotateRight(self, key);
                        parent = self.nodes[key].parent;
                    }
                    self.nodes[parent].red = false;
                    self.nodes[grandparent].red = true;
                    rotateLeft(self, grandparent);
                }
            }
        }
        self.nodes[self.root].red = false;
    }

    function rotateLeft(Tree storage self, uint x) private {
        uint y = self.nodes[x].right;
        self.nodes[x].right = self.nodes[y].left;
        if (self.nodes[y].left != NULL) {
            self.nodes[self.nodes[y].left].parent = x;
        }
        self.nodes[y].parent = self.nodes[x].parent;
        if (self.nodes[x].parent == NULL) {
            self.root = y;
        } else if (x == self.nodes[self.nodes[x].parent].left) {
            self.nodes[self.nodes[x].parent].left = y;
        } else {
            self.nodes[self.nodes[x].parent].right = y;
        }
        self.nodes[y].left = x;
        self.nodes[x].parent = y;
    }

    function rotateRight(Tree storage self, uint x) private {
        uint y = self.nodes[x].left;
        self.nodes[x].left = self.nodes[y].right;
        if (self.nodes[y].right != NULL) {
            self.nodes[self.nodes[y].right].parent = x;
        }
        self.nodes[y].parent = self.nodes[x].parent;
        if (self.nodes[x].parent == NULL) {
            self.root = y;
        } else if (x == self.nodes[self.nodes[x].parent].right) {
            self.nodes[self.nodes[x].parent].right = y;
        } else {
            self.nodes[self.nodes[x].parent].left = y;
        }
        self.nodes[y].right = x;
        self.nodes[x].parent = y;
    }

    function getMin(Tree storage self) internal view returns (uint) {
        uint current = self.root;
        require(current != NULL, "empty tree");
        while (self.nodes[current].left != NULL) {
            current = self.nodes[current].left;
        }
        return current;
    }

    function getMax(Tree storage self) internal view returns (uint) {
        uint current = self.root;
        require(current != NULL, "empty tree");
        while (self.nodes[current].right != NULL) {
            current = self.nodes[current].right;
        }
        return current;
    }

    function exists(Tree storage self, uint key) internal view returns (bool) {
        return self.nodes[key].exists;
    }

    function inOrder(Tree storage self, uint node, uint[] storage output) internal view {
        if (node == NULL) return;
        inOrder(self, self.nodes[node].left, output);
        output.push(node);
        inOrder(self, self.nodes[node].right, output);
    }

    function inOrderTraversal(Tree storage self) internal view returns (uint[] memory) {
        uint[] memory temp = new uint[](1000); // max 1000 nodes for example
        uint[] storage output;
        inOrder(self, self.root, output);
        return output;
    }

    function rangeQuery(Tree storage self, uint min, uint max, uint[] storage results) internal view {
        _rangeQuery(self, self.root, min, max, results);
    }

    function _rangeQuery(Tree storage self, uint node, uint min, uint max, uint[] storage results) private view {
        if (node == NULL) return;
        if (min < node) _rangeQuery(self, self.nodes[node].left, min, max, results);
        if (min <= node && node <= max) results.push(node);
        if (max > node) _rangeQuery(self, self.nodes[node].right, min, max, results);
    }
}

contract RedBlackTreeTest {
    using RedBlackTreeLib for RedBlackTreeLib.Tree;
    RedBlackTreeLib.Tree private tree;

    function insert(uint key) external {
        tree.insert(key);
    }

    function getMinimum() external view returns (uint) {
        return tree.getMin();
    }

    function getMaximum() external view returns (uint) {
        return tree.getMax();
    }

    function checkExists(uint key) external view returns (bool) {
        return tree.exists(key);
    }

    function getRange(uint min, uint max) external view returns (uint[] memory result) {
        tree.rangeQuery(min, max, result);
    }

    function getInOrder() external view returns (uint[] memory result) {
        result = tree.inOrderTraversal();
    }
}

함수	설명
insert(uint)	트리에 값 삽입 (자동 균형 유지)
getMin()	최소값 조회
getMax()	최대값 조회
내부 함수	insertFixup, rotateLeft, rotateRight
exists(key)	특정 키 존재 여부 확인 (mapping 기반)
inOrderTraversal()	중위 순회 (작은 값부터 정렬된 리스트 반환)
rangeQuery(min, max)	특정 범위 내의 값들만 반환

🧱 구조 설명:
• mapping(uint => Node)을 통해 포인터 대신 키 기반 연결
• Node는 parent, left, right, red, exists 필드로 구성
• rotateLeft와 rotateRight로 균형 조정
• mapping(uint => Node)을 통해 트리 구조 유지
• insert 시 자동으로 균형 맞춤 (insertFixup)
• 중위 순회 및 범위 탐색을 통해 정렬된 데이터 활용 가능
• 최대 1000개 노드 기준으로 inOrderTraversal() 지원 (확장 가능)