이진 탐색 트리는 존재하는 모든 노드에 대해서 다음의 성질을 만족하는 이진트리다.

• 한 노드의 왼쪽 트리에 있는 모든 키값은 그 노드의 키값보다 작다.
• 한 노드의 오른쪽 트리에 있는 모든 키값은 그 노드의 키값보다 크다.
• 각 노드의 키값은 모두 유일해야 한다.

(1) 탐색

이진 탐색 트리에서의 탐색은 루트 노드에서부터 특정 키값을 갖는 원소를 찾아 나가는 방식이다.
부모 노드의 왼쪽 자식 노드의 키값은 부모노드의 키값보다 작고 오른쪽 자식 노드의 키값은 부모노드의 키값보다 크다는 특징을 이용한다.
위의 그림에서 26을 찾는 과정을 살펴보자.
먼저, 루트노드의 키값 20과 찾아야 하는 키값 26을 비교한다. 루트노드의 키값이 더 작으므로 우리가 찾는 노드는 루트노드보다 오른쪽에 있을 것이다.
다시 28과 26을 비교한다. 이번에는 찾아야 하는 키값 26이 더 작으므로 왼쪽으로 간다. 26과 26을 비교한다. 값이 일치하므로 탐색이 끝난다.

(2) 노드 추가

이진 탐색 트리에서 새로운 노드의 추가는 추가할 키값이 존재하는지 존재하지 않는지를 루트노드부터 탐색하다가 더 이상 비교할 노드가 없으면 그 위치에 새로운 노드를 만들어서 추가한다. 이미 트리에 해당 키값이 존재한다면 추가하지 않고 리턴한다.
위의 이진 탐색 트리에 27을 추가해보자.
루트노드와 비교했을때 27이 크므로 오른쪽으로 내려간다.
28과 비교했을때 27이 작으므로 왼쪽으로 내려간다.
26과 비교했을때 27이 크므로 오른쪽으로 내려가야 하지만, 더 이상 비교할 노드가 없으므로 26의 오른쪽 자식으로 노드를 생성하고 27을 추가한다.

(3) 노드 삭제

이진 탐색 트리에서 노드의 삭제는 삭제할 원소를 탐색한 후, 찾은 노드를 삭제하고 남은 노드들의 위치를 조절해서 이진 탐색 트리로 다시 만들면
된다. 삭제하려는 노드의 자식 노드의 개수에 따라서 세 가지 경우로 나뉘게 되는데, 삭제하고자 하는 노드의 자식 노드가 하나도 없는 경우, 한 개만 있는 경우, 두 개 모두 있는 경우가 있다.
삭제하고자 하는 노드의 자식 노드가 하나도 없을 경우 : 삭제할 노드는 리프 노드일 것이고 노드를 삭제한 다음 남은 노드의 위치 조절은 필요 없다. 예를 들어 위의 그림에서 키값이 4인 노드를 삭제하는 것이 이 경우에 해당된다.
삭제하고자 하는 노드의 자식 노드가 한 개만 있는 경우 : 노드를 삭제한 뒤 그 자식 노드를 삭제한 노드 위치로 옮기면서 부분 트리도 따라 올린다. 예를 들어 위의 그림에서 키값이 17인 노드를 삭제하는 것이 이 경우에 해당된다. 17 노드를 삭제한 뒤, 하나 있는 자식인 19노드를 17노드가 있던 자리로 옮기면 된다.
삭제하고자 하는 노드의 자식 노드가 두 개 모두 있는 경우 : 노드를 삭제한 다음, successor 노드를 삭제한 노드 위치로 옮기면서 successor 노드가 있던 자리에 successor 노드의 자식 노드를 옮기고 부분 트리도 따라 올린다. 위의 그림에서 예를 들면, 15 노드를 삭제하는 경우 자식이 두 개 모두 있으므로 우선 15 노드를 삭제한 뒤 successor 노드인 17 노드를 15 노드가 삭제된 자리로 옮기고, successor 노드의 자식노드와 부분트리를 successor 노드가 원래 있었던 자리로 끌어올려야하므로 19노드를 15노드 자리로 끌어 올린다.

* successor 노드란 삭제되는 노드의 다음 키값을 가지고 있는 노드를 의미하는데, 삭제 대상 노드의 왼쪽 서브트리의 가장 큰(오른쪽)값 또는 오른쪽 서브트리의 가장 작은(왼쪽)값이 successor 노드가 된다.

(4) 성능

리프 노드를 제외한 모든 노드가 자식을 두 개씩 가지고 있을 때, 즉, 포화 이진 탐색 트리일 때 최선의 탐색 성능을 낸다.

(5) 구현

class Node {
    constructor(_data) {
        this.data = _data;
        this.leftChild = null;
        this.rightChild = null;
    }
}

class BinarySearchTree {

    constructor(_data) {
        this.root = new Node(_data);
    }
    
    // 탐색
    search(data, node = this.root) {
        if (data === node.data) {
            return node;
        } else {
            return this.search(data, data > node.data ? node.rightChild : node.leftChild);
        }
    }
    
    // 노드 추가
    add(data, node = this.root) {
        if (data > node.data) {
            if (!node.rightChild) {
                node.rightChild = new Node(data);
            } else {
                this.add(data, node.rightChild);
            }
        } else if (data < node.data) {
            if (!node.leftChild) {
                node.leftChild = new Node(data);
            } else {
                this.add(data, node.leftChild);
            }
        }
    }
    
    // 노드 삭제
    remove(data) {
        /*
         successor 노드는 대상 노드의 왼쪽 서브 트리의 가장 큰 노드
         또는 오른쪽 서브트리의 가장 작은 노드이다.
         여기서는 오른쪽 서브트리의 가장 작은 노드를 선택하도록 하였다.
          */
        const getSuccessorNode = (targetNode) => {
            let successor = targetNode.rightChild;
            let successorParent = null;
            while (successor.leftChild) {
                successorParent = successor;
                successor = successor.leftChild;
            }

            successorParent.leftChild = successor.rightChild ? successor.rightChild : null;

            return successor;
        };

        let parent = null;
        let current = this.root;
        
        while (data !== current.data) {
            parent = current;
            if (data < current.data) {
                current = current.leftChild;
            } else if (current.data < data) {
                current = current.rightChild;
            }
        }
        
        if (!current.leftChild && !current.rightChild) { // 자식이 없을 경우
            parent.leftChild.data === current.data ? parent.leftChild = null : parent.rightChild = null;
        } else if (current.leftChild && !current.rightChild) { // 왼쪽 자식만 있을 경우
            current = current.leftChild;
            parent.leftChild.data === current.data ? parent.leftChild = current : parent.rightChild = current;
        } else if (!current.leftChild && current.rightChild) { // 오른쪽 자식만 있을 경우
            current = current.rightChild;
            parent.leftChild.data === current.data ? parent.leftChild = current : parent.rightChild = current;
        } else if (current.leftChild && current.rightChild) { // 양쪽 자식 모두 있을 경우
            const successorNode = getSuccessorNode(current);
            const currentLeftChildTemp = current.leftChild;
            const currentRightChildTemp = current.rightChild;
            current = successorNode;
            current.leftChild = currentLeftChildTemp;
            current.rightChild = currentRightChildTemp;
            if (!parent) {
                this.root = current;
            } else {
                console.log(parent)
            }
        }
    };

    // 전위 순회(TLR)
    preOrder(node = this.root) {
        if (node) {
            console.log(node.data);
            this.preOrder(node.leftChild);
            this.preOrder(node.rightChild);
        }
    }

    // 중위 순회(LTR)
    inOrder(node = this.root) {
        if (node) {
            this.inOrder(node.leftChild);
            console.log(node.data);
            this.inOrder(node.rightChild);
        }
    }

    // 후위 순회(LRT)
    postOrder(node = this.root) {
        if (node) {
            this.postOrder(node.leftChild);
            this.postOrder(node.rightChild);
            console.log(node.data);
        }
    }
}