자료구조 7주차

자료구조 7주차

linked list 처럼 쓰면서 중앙을 찍을 수 있도록 하기

Binary Search Tree

Contents

• Skip List Idea from Linked List
• Binary Search Tree Definition
• Search Algorithm, Insert Algorithm, Delete Alogrithm
• Proofs of Correctness and Performance

Skip List

Definition of Binary Search Tree

• 모든 곳에서 왼쪽은 전부 작고, 오른쪽은 전부 큰 구조 == Tree
• 지금 보는 BST는 루트에 중앙값이 오지 않아도 된다고 하자.
  • NODE contains KEY
  • One ROOT Node (unless empty BST) → 예외는 더미노드로 처리
  • Root Node may have two (LEFT_RIGHT) Child Node(s)
  • Each Child is the ROOT of its own SUBTREE
  • Each Subtree is itself a BST
    • We call them Left and Right Subtree(s)
  • The Key values in Left Subtree are all smaller than the Key in the Root Node
    • And Vice Versa
    • Holds recursively in each Subtree (of course)
• Code for Node

class Node{
    int key;
    Node *left, *right;
}

• Search Algorithm
  • Call Search(Root, X)
  • Search(Node, X)
  • Recursive Implementation
    • If no current Node then return FAIL (return NULL로 약속)
    • Compare K (Key at current Note) with X (alue to Search)
    • If EQUAL then return current Node (pointer to the Node)
    • If K<X then return Search(RIght Child, X)
    • If K>X then return Search(Left Child, X)
• Code for Search

• Search Correctness
  • To Prove : “If X equals key in a Node in the Tree whose root is R, Search(R,X) returns the pointer to the node, otherwise it will return FAIL”
  • Proof by cases
    • Case 0 : Trivial
    • Case 1 : Trivial
    • Case 2 : “K<X” means that X is not in the Left SubTree, so if X is in the Tree then X is in the Right Subtree. earch(Right Child, X) will return the pointer to the node if X is in the Right Subtree.
      • 오른쪽 child에서 search를 한 게 전체에서 search 한 것과 동일
    • Case 3 : Case 2 와 동일 (Ditto)
• Search Performance
  • Given a fixed Tree
    • Worst Case : O(Height)
    • Average Case : ???
  • Considering All Possible Trees
    • Wrost Case : O(n)
• Insert Algorithm
  • First Search(Root, X)
  • If Search() succeeds, then Insert() fails.
  • If Search() fails, then make a new Node at the last direction the Search() tired to go
    • == Search시 실패할 땐 NULL을 반환 → 그 자리에 Node를 만들기
• Assume Dummy Roots
  • Parent를 가지고 있어야 하기 때문에 더미 루트가 있다고 가정
  • 항상 새로운 노드를 만들 땐 부모가 있다고 가정
• Delete Algorithm
  • Child 0 case :
  • Child 1 case :
  • Child 2 case : 말로만 한다..?

#include <bits/stdc++.h>    

using namespace std;

class Node {
public:
    int key;
    Node* left, * right;
    Node(int x) {
        key = x;
        *left = *right = NULL;
    }
};

Node* Search(Node* N, int x) {
    if (N == NULL) {
        return NULL;
    }
    else {
        if (N->key > x) {
            Search(N->right, x);
        }
        else if (N->key < x) {
            Search(N->left, x);
        }
        else {
            return N;
        }
    }
}
Node* Insert(Node* N, int x, Node** RP) {
    Node* NN;
    if (N == NULL) {
        NN = new Node(x);
        *RP = NN;
        return NN;
    }
    else {
        if (N->key > x) {
            Insert(N->right, x, &(N->right));
        }
        else if (N->key < x) {
            Insert(N->left, x, &(N->left));
        }
        else {
            return NULL;
        }
    }
}
void Delete(Node* N, Node* p) {
    if (N == NULL) {
        return;
    }
    else if (N->right == NULL && N->left == NULL) {
        if (p->left == N) {
            p->left == NULL;
        }
        else {
            p->right == NULL;
        }
    }
    else if (N->right != NULL && N->left == NULL) {
        if (p->left == N) {
            p->left = N->right;
        }
        else {
            p->right = N->right;
        }

    }
    else if (N->right == NULL && N->left != NULL) {
        if (p->left == N) {
            p->left = N->left;
        }
        else {
            p->right = N->left;
        }
    }
    else {
        Node* NN, * PP;
        PP = NULL;
        NN = N;
        while (NN != NULL) {
            PP = NN;
            NN = NN->left;
        }
        N->key = NN->key;
        delete(NN, PP); 
    }
}