[자료구조] 이진탐색트리 구현 - 기본 뼈대, insert 메소드

기본 뼈대 작성

class Node{

    constructor(key){

        this.key = key;

        this.left = null;

        this.right = null;

    }

}

class BinarySearchTree{

    constuctor(){

        this.root = null;

    }

}

우선 이진탐색트리 안에 들어가는 노드는 key, left, right로 구성된다.

이진탐색트리 안에는 루트노드가 있다.

 

insert 메소드

class Node{

    constructor(key){

        this.key = key;

        this.left = null;

        this.right = null;

    }

}

class BinarySearchTree{

    constuctor(){

        this.root = null;

    }



    insert(key){

        let newNode = new Node(key);

        if(this.root === null){

            this.root = newNode;

        }else{

            this.insertNode(this.root,newNode);

        }

    }

    insertNode(node, newNode){

        if(newNode.key < node.key){

            if(node.left === null){

                node.left = newNode;

            }else{

                this.insertNode(node.left, newNode);

            }

        }else{

            if(node.right === null){

                node.right = newNode;

            }else{

                this.insertNode(node.right, newNode);

            }

        }

    }

}

insert(key)

우선 newNode로 새 Node를 만든다.

그리고 현재 트리 안에 root노드가 존재하지 않으면 newNode를 root노드로 지정한다.

현재 트리 안에 root노드가 이미 있으면 insertNode메소드를 호출한다.

 

insertNode(node, newNode)

insertNode에서 node는 비교대상 노드, newNode는 새롭게 추가할 노드라고 생각하면 되겠다.

앞서 insert메소드에서 현재 트리 안에 root노드가 이미 존재할 때 this.insertNode(root, newNode)를 이용해서 insertNode를 호출했기 때문에 현재 비교대상 노드는 루트노드와 새롭게 추가할 노드이다.

• newNode의 key가 비교대상 노드의 key보다 작은 경우
• 비교대상 노드의 왼쪽 자리가 비어 있으면 그 자리에 newNode를 넣는다.
• 비교대상 노드의 왼쪽 자리가 이미 차 있으면 다시 insertNode를 재귀함수로 호출하고 이 때 비교대상 노드는 지금 비교했던 노드의 왼쪽 노드로 변경된다.
• newNode의 key가 비교대상 노드의 key보다 큰 경우
• 비교대상 노드의 오른쪽 자리가 비어있으면 그 자리에 newNode를 넣는다.
• 비교대상 노드의 오른쪽 자리가 이미 차 있으면 다시 insertNode를 재귀함수로 호출하고 이 때 비교대상 노드는 지금 비교했던 노드의 오른쪽 노드로 변경된다.