Tree to SplayTree

pengooseDev·2025년 2월 17일

기여하고 싶은 오픈소스가 있는데, 코드베이스가 말 그대로 어려웠다. (동시 편집을 위한 CRDT—conflict free replicated data type—가 splayTree기반으로 작성되어있음)
따라서, 이를 학습하고자 한다.

SplayTree의 자료구조 특성상 학습 입문자용 가이드가 전혀 없었다. 혹시, 필요한 사람들이 있을까하여 하나 남겨두고자 한다.

1. 트리(Tree)

트리의 구성요소는 아래와 같다.

node:
트리의 기본단위. 데이터와 자식 노드의 포인터를 가짐.

root:
트리 최상단 노드

leaf:
자식이 없는 노드

각 노드는 0개 이상의 자식을 가지며, 자식은 하나의 부모노드를 가짐.

class Node {
  children = [];

  constructor(value) {
    this.value = value;
  }
}

import { Node } from './tree/node';

const root = new Node(1); // root node
// root node의 자식 노드(2번째 노드) 추가
root.children.push(new Node(2));
// root node의 자식 노드(3번째 노드) 추가
root.children.push(new Node(3));
// root node의 자식 노드(2번째 노드)의 자식 노드(4번째 노드) 추가
root.children[0].children.push(new Node(4));


console.log(root);
/**
 *  Node {
 *    value: 1,
 *    children: [
 *      Node {
 *        value: 2,
 *        children: [ Node { value: 4, children: [] }
 *     },
 *     Node { value: 3, children: [] }
 *   ]
 * }
 */

노드는 여러 자식을 가질 수 있음.
다만, 보통 문제에선 이진트리를 많이 사용.

2. 이진트리(Binary Tree)

각 노드가 최대 2개의 자식(right, left)을 갖는 트리.

3. 이진 탐색 트리(Binary Search Tree)

거기서 검색을 빠르게 함. 근데 빠르게 검색하기 위해서 조건을 좀 붙임.

각각의 노드는 왼쪽 서브트리의 모든 값은 노드의 값보다 작고, 오른쪽 서브트리의 모든 값은 노드의 값보다 큼.

이러면 검색뿐 아니라 삽입, 삭제 연산을 O(logN)으로 땡길 수 있음.

class BSTNode {
  left = null; // 왼쪽 자식
  right = null; // 오른쪽 자식
  parent = null; // optional. 다만, 추후 splayTree 개념 확장을 위해 추가

  constructor(value) {
    this.value = value;
  }
}

class BinarySearchTree {
  root = null;

  // 삽입 O(logN)
  insert(value) {
    const newNode = new BSTNode(value);
    if (!this.root) {
      this.root = newNode;
      return newNode;
    }
    let cur = this.root;
    let parent = null;
    while (cur) {
      parent = cur;
      if (value < cur.value) cur = cur.left;
      else cur = cur.right;
    }
    newNode.parent = parent;
    if (value < parent.value) parent.left = newNode;
    else parent.right = newNode;
    return newNode;
  }

  // 탐색 O(logN)
  find(value) {
    let cur = this.root;
    while (cur) {
      if (cur.value === value) return cur;
      else if (value < cur.value) cur = cur.left;
      else cur = cur.right;
    }
    return null;
  }
}

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
console.log(bst.find(15));
/**
 * BSTNode {
 *  value: 15,
 *  left: null,
 *  right: null,
 *  parent: BSTNode {
 *   value: 10,
 *   left: BSTNode { value: 5, left: null, right: null, parent: [BSTNode] },
 *   right: BSTNode { value: 15, left: null, right: null, parent: [BSTNode] }
 *  }
 * }
 */

BST는 정렬된 순서로 데이터 저장. 이진탐색과 비슷하게 동작
부모 포인터가 왜 있는가? < SplayTree와 같은 자기 조정 트리에서 써야함.

4. 근데 막 회전함

회전(Rotation)은 두 노드 간의 관계를 재조정하는 연산임

좌측 회전: 오른쪽 자식을 루트로 끌어올림.
우측 회전: 왼쪽 자식을 루트로 끌어올림.

근데 얘 왜 돎?:

자주 접근하는 노드가 루트에 가깝게 조정되서, 접근시간 단축됨

const rotate = (x, dir) => {
  const p = x.parent;
  if (!p) return; // root node인 경우 회전 불가
  if (dir === 'right') {
    p.left = x.right;
    if (x.right) x.right.parent = p;
    x.right = p;
  } else {
    p.right = x.left;
    if (x.left) x.left.parent = p;
    x.left = p;
  }
  x.parent = p.parent;
  if (p.parent) {
    if (p.parent.left === p) p.parent.left = x;
    else p.parent.right = x;
  }
  p.parent = x;
};

그냥 차이점 개행으로 분리하자면


const Rotate = {
  right(x) {
    const p = x.parent;
    if (!p) return; // root node인 경우 회전 불가

    p.left = x.right;
    if (x.right) x.right.parent = p;
    x.right = p;

    x.parent = p.parent;
    if (p.parent) {
      if (p.parent.left === p) p.parent.left = x;
      else p.parent.right = x;
    }
    p.parent = x;
  },

  left(x) {
    const p = x.parent;
    if (!p) return; // root node인 경우 회전 불가

    p.right = x.left;
    if (x.left) x.left.parent = p;
    x.left = p;

    x.parent = p.parent;
    if (p.parent) {
      if (p.parent.left === p) p.parent.left = x;
      else p.parent.right = x;
    }
    p.parent = x;
  },
};

Splay Tree

이 친구는 특정 노드에 접근할 때마다 해당 노드를 루트로 끌어올림(자기 조정 트리)

splay 연산:

흥이 넘치는 연산이 3개 있음.

zig:
노드 부모가 루트일 때, 단순 회전.

zig-zig:
노드와 부모가 같은 방향일 때, 부모가 먼저 회전 > 이후 노드 회전.

zig-zag:
노드와 부모가 반대 방향일 때, 회전 2배 이벤트 (2번 연속 회전)

Impl

class SplayNode {
  left = null;
  right = null;
  parent = null;

  constructor(value) {
    this.value = value;
  }
}

노드는 아까 BST랑 동일.

class SplayTree {
  root = null;

  rotate(x) {
    const p = x.parent;
    if (!p) return; // 루트 노드는 회전할 수 없음
    const g = p.parent;
    if (p.left === x) {
      // 우측 회전
      p.left = x.right;
      if (x.right) x.right.parent = p;
      x.right = p;
    } else {
      // 좌측 회전
      p.right = x.left;
      if (x.left) x.left.parent = p;
      x.left = p;
    }
    p.parent = x;
    x.parent = g;
    if (g) {
      if (g.left === p) g.left = x;
      else g.right = x;
    } else {
      this.root = x;
    }
  }

  splay(x) {
    if (!x) return; // 노드가 없으면 종료
    while (x.parent) {
      const p = x.parent;
      const g = p.parent;

      const isZig = !g;
      const isZigZig =
        (g && g.left === p && p.left === x) || (g.right === p && p.right === x);

      // 3가지 회전 케이스
      if (isZig) {
        // zig
        this.rotate(x);
      } else if (isZigZig) {
        // zig-zig
        this.rotate(p);
        this.rotate(x);
      } else {
        // zig-zag
        this.rotate(x);
        this.rotate(x);
      }
    }
    this.root = x;
  }

  // 삽입: BST 삽입 후, 해당 노드 루트로 splay
  insert(value) {
    const newNode = new SplayNode(value);
    if (!this.root) {
      this.root = newNode;
      return newNode;
    }
    let cur = this.root;
    let parent = null;
    while (cur) {
      parent = cur;
      if (value < cur.value) cur = cur.left;
      else cur = cur.right;
    }
    newNode.parent = parent;
    if (value < parent.value) parent.left = newNode;
    else parent.right = newNode;
    this.splay(newNode);
    return newNode;
  }

  // 검색: value 찾고, 해당 노드 루트로 splay
  find(value) {
    let cur = this.root;
    while (cur) {
      if (cur.value === value) {
        this.splay(cur);
        return cur;
      } else if (value < cur.value) {
        cur = cur.left;
      } else {
        cur = cur.right;
      }
    }
    return null;
  }
}