Tree Data Structure (Binray Search Tree)

About Tree

 

• 계층적인 데이터를 저장할때 사용한다. ex)회사 조직도
• 엣지(Edge)로 연결(Connect)된 노드(Node)의 집합(Group)이다.
• 노드의 분류
  • Root : 최상위 노드
  • Parent : 상위 노드
  • Child : 자식 노드
  • left : 자식 노드가 없는 노드

More About Binary Search Tree

• 자식의 노드수가 두개 이하인 트리를 의미한다.
• BST 는 작은 값을 왼쪽 노드에 큰값을 오른쪽 노드에 저장한다.
• 구현방법
  1. 루트 노드를 current 노드로 설정한다.
  2. 삽입할 노드의 값이 current 노드의 값보다 작으면 current 노드를 왼쪽으로 설정한다.
  3. 삽입할 노드의 값이 current 노드의 값보다 크다면 6번 과정을 진행한다.
  4. current 노드의 왼쪽값이 null 이면 삽입할 노드를 왼쪽에 삽입한뒤 루프를 종료한다.
  5. current 노드의 왼쪽값이 null 이 아니면 다음 루프를 진행 한다.
  6. current 노드를 오른쪽으로 설정한다.
  7. current 노드의 오른쪽값이 null 이면 새로운 노드를 오른쪽에 삽입한뒤 루프를 종료한다.
  8. current 노드의 오른쪽값이 null 이 아니면 다음 루프를 진행한다.

Traversal

• 순회는 재귀 호출로 이해될 수 있다.
• 트리는 비선형이기때문에 모든 노드를 거쳐가기 위한 방법이 필요하다.
• 순회 방법
  • 전위 순회(Pre-order) : Root - left - right
  • 중위 순회(in-order) : left - Root - right
  • 후위 순회(Post-order) : left - right - Root

ADT

Method Name	contents
insert	데이터 삽입
inOrder	중위 순회
preOrder	전위 순회
postOrder	후위 순회
min	최소값 반환
max	최대값 반환
getCount	노드 갯수 반환
getEdge	엣지 갯수 반환

Implementation

//ES6
class Node {
    constructor(data, left, right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    show() {
        return this.data
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
        this.count = 0; //used exam1
        this.edge = 0; //used exam1
    }

    insert(data) {
        let newNode = new Node(data)

        if(this.root === null) {
            this.root = newNode
            ++this.count;
        } else {
            this.insertNode(this.root, newNode)
        }
    }

    insertNode(node, newNode) {
        if (newNode.data < node.data) {
            if (node.left === undefined) {
                node.left = newNode;
                ++this.count;
                ++this.edge;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right === undefined) {
                node.right = newNode;
                ++this.count;
                ++this.edge;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }
    /* 트리 순회 */
    inOrder(node) {
        if(node !== undefined) {
            this.inOrder(node.left);
            console.log(node.show());
            this.inOrder(node.right);
        }
    }
    preOrder(node) {
           if(node !== undefined) {
            console.log(node.show());
            this.inOrder(node.left);
            this.inOrder(node.right);
        }
    }

    postOrder(node) {
           if(node !== undefined) {
            this.inOrder(node.left);
            this.inOrder(node.right);
            console.log(node.show());
        }
    }
    /*노드 갯수 엣지 갯수 */
    getCount() {
        return this.count;
    }

    getEdge() {
        return this.edge;
    }

    /*최대값 최소값 */
    min() {
        return this.minNode(this.root);
    }

    minNode(node) {
        if (node) {
            while (node && node.left !== undefined) {
                node = node.left
            }
            return node.data;
        }
        return null;
    }   

    max() {
        return this.maxNode(this.root);
    }

    maxNode(node) {
        if (node) {
            while (node && node.right !== undefined) {
                node = node.right;
            }
            return node.data;
        }
        return null;
    }

}

Test

//test code
var tree = new BinarySearchTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);

tree.inOrder(tree.root);
tree.preOrder(tree.root);
tree.postOrder(tree.root);

tree.min();
tree.max();
tree.getCount();
tree.getEdge();

삭제는 따로 구현 하지 않았습니다. 예제 풀이 하면서 업데이트 시킬 계획 입니다.