LL 이진탐색트리

이진탐색트리

int bcnt;
struct Node {
    int data;
    
    //왼 : 나보다 작은값
    //오른 : 나보다 큰값
    Node *lch, *rch;    
    Node *alloc(int nd) {
        data = nd, lch = rch = NULL;
        return this;
    }
}buf[SIZE];
 
// 트리에서 data 검색
Node* searchNode(Node* now, int tg) {
    // 데이터 검색되면 리턴
    if (now == NULL || now->data == tg) return now;
    
    // 검색값을 찾으러 이동
    if (tg < now->data)    return searchNode(now->lch, tg);
    else return searchNode(now->rch, tg);
}
 
// 트리에 값 추가
Node* insertNode(Node* now, int nd) {
    // 넣을 위치를 찾으면 값을 넣음
    if (now == NULL)    return buf[bcnt++].alloc(nd);
    
    // 빈자리가 아니면 넣을 위치를 찾아서 이동
    if (nd < now->data)    now->lch = insertNode(now->lch, nd);
    else now->rch = insertNode(now->rch, nd);
    
    // 값을 넣는게 아니면 이동한 위치를 리턴
    return now;
}
 
// 노드 하위의 가장 작은값 찾기
int findMin(Node*p) {
    // 작은값은 무조건 왼쪽에 있으니까
    for (; p->lch; p = p->lch);
    return p->data;
}
 
// 노드 삭제
Node* eraseNode(Node* now, int tg) {
    // 지워야 할 노드 위치라면
    if (now->data == tg) {
        // 해당노드의 left, right가 다 있으면
        // right의 가장 작은 값을 찾아서 해당노드 위치로 이동하고
        // 가장 작은 값이 있던 위치를 삭제 (이진탐색 트리 성질)
        if (now->lch && now->rch) {
            int minValue = findMin(now->rch);
            now->data = minValue;
            now->rch = eraseNode(now->rch, minValue);
            return now;
        }
 
        // 한쪽만 있다면 있는쪽을 리턴
        if (now->lch) return now->lch;
        return now->rch;
    }
 
    // 지울 위치를 찾아 이동
    if (tg < now->data)    now->lch = eraseNode(now->lch, tg);
    else now->rch = eraseNode(now->rch, tg);
 
    // 지운게 아니라면 이동한 위치를 리턴
    return now;
}
 
// tree를 순회한 결과를 arr에 담는다.
int* ap, idx, cmd;
void traverse(Node* now) {
    if (now == NULL) return;
    if (cmd == 4) ap[idx++] = now->data;
    traverse(now->lch);
    if (cmd == 5) ap[idx++] = now->data;
    traverse(now->rch);
    if (cmd == 6) ap[idx++] = now->data;
}

 

우선순위 큐

int n = 0;
int v[100010];
 
struct Heap
{
    void push(int value)    {
        n++;
        v[n] = value;
        update(n);
    }
    void update(int tg) {
        while (tg > 0)    {
            int parent = tg / 2;
            if (v[parent] > v[tg])    {
                int tmp = v[parent];
                v[parent] = v[tg];
                v[tg] = tmp;
                tg = parent;
            }
            else {
                break;
            }
        }
    }
    
    int pop()    {
        int ret = v[1];
        v[1] = v[n];
        n--;
 
        downdate(1);
 
        return ret;
    }
    void downdate(int tg)    {
        while (tg <= n)    {
            int lch = tg * 2;
            int rch = lch + 1;
            int child = lch;
 
            if (rch <= n)    {    // 자식이 둘다 있음
                if (v[child] > v[rch])    child = rch;
            }
            else if (lch <= n)    {    // 자식이 왼쪽만 있음
                child = lch;
            }
            else {
                break;
            }
 
            if (v[tg] > v[child])    {
                int tmp = v[child];
                v[child] = v[tg];
                v[tg] = tmp;
                tg = child;
            }
            else {
                break;
            }
        }
    }
 
    void update_direct(int i, int value)
    {
        v[i] = value;
        update(i);
        downdate(i);
    }
};