// 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() 지원 (확장 가능)