두 갈래 트리 생성, 삽입, 삭제

두 갈래 나무가 뭐예요?

우리는 각 노드에 최대 두 개의 하위 노드가 있는 나무를 두 갈래 나무, 즉 영어의 Binary Tree라고 부른다.우리는 이 두 개의 노드를 각각 왼쪽 노드와 오른쪽 노드라고 부른다.일반적으로 두 갈래 나무의 노드는 다음과 같다.

데이터

왼쪽 하위 노드 참조/포인터

오른쪽 하위 노드 인용/포인터

다음 JavaScript 코드를 사용하여 두 갈래 트리의 노드를 나타낼 수 있습니다.

class BinaryTreeNode {
    constructor(data, leftChild, rightChild) {
        this.data = data;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }
};

두 갈래 나무의 정의에 따라 우리는 다음과 같은 두 가지 특성을 쉽게 얻을 수 있다.

두 갈래 나무의 n층은 최대 2n-1개의 노드가 있다
이 특성은 수학 귀납법으로 결론을 얻을 수 있다.

루트 노드는 1층이고 노드 수는 21-1=1이다

n층을 가정할 때 노드 수는 2n-1이다

두 갈래 나무는 노드마다 최대 두 개의 자노드가 있기 때문에 우리는 n+1층의 노드 수 2*2n-1, 즉 2(n+1)-1을 알 수 있기 때문에 위의 두 번째 가설이 성립되었다

높이가 h인 두 갈래 나무는 최대 2h-1개의 노드가 있다
이 결론은 두 갈래 나무의 각 노드가 가장 많은 노드 수를 가설할 수 있다. 2, 그러면 높이가 h인 두 갈래 나무의 총 노드 포인트는 1+2+4...+2h-1이다. 이것은 간단한 등비수열이기 때문에 2h-1과 같다

두 갈래 나무의 이 두 가지 기초 특성을 유연하게 활용하면 두 갈래 나무와 관련된 알고리즘 문제를 비교적 편리하게 해결할 수 있다.

두 갈래 트리 만들기

두 갈래 나무를 만드는 데는 여러 가지 방식이 있다. 우리는 여기서 이러한 전제 가설을 한다. 하나의 수조를 정하고 층 순서에 따라 완전한 두 갈래 나무를 만드는 것이다.
완전 두 갈래 나무: 두 갈래 나무 중 마지막 층을 제외한 모든 층을 완전히 채우고, 마지막 층은 가능한 한 왼쪽 나무를 채운다
두 갈래 트리 알고리즘을 만드는 핵심은 노드와 하위 노드의 대응 관계를 어떻게 확정하는가이다.완전 두 갈래 나무의 정의에 따르면 마지막 층의 모든 노드를 제외하고 두 개의 하위 노드가 있다는 결론을 얻을 수 있다.
수조에서 인덱스가 i인 원소의 왼쪽 노드는 수조에서 인덱스가 (2*i)+1인 원소이고, 오른쪽 노드는 인덱스가 (2*i)+2인 원소이다
두 갈래 트리를 만드는 알고리즘은 다음과 같이 JavaScript로 표시됩니다.

function createCompleteBinaryTreeFromArray(dataArray) {
    let treeNodeArray = dataArray.map(function(data){
        return new BinaryTreeNode(data, null, null);
    });
    for (let i = 0; i < treeNodeArray.length; ++i) {
        let node = treeNodeArray[i];
        node.leftChild = treeNodeArray[i * 2 + 1];
        node.rightChild = treeNodeArray[i * 2 + 2];
    }
    return treeNodeArray[0];
};

설명해야 할 것은 여기에서 먼저 Array의map 방법을 호출하여 데이터 수조를 이차수 노드 수조로 전환한 다음에 노드 수조에 노드와 하위 노드의 대응 관계를 설정하여 이차수를 만드는 목적을 달성한다. 이때 노드 수조의 첫 번째 요소는 이차수의 뿌리 노드이다.

두 갈래 트리 노드 삽입하기

기존의 두 갈래 나무에 새 노드를 삽입하는 관건은 삽입할 위치를 어떻게 찾느냐에 있다. 만약 삽입된 두 갈래 나무가 어떤 순서를 유지해야 한다면 추가 처리가 필요하다.여기서 우리는 간단한 상황을 고려한다. 데이터를 주고 층 순서에 따라 적당한 위치를 찾아 새 노드를 삽입하는 것이다.
이른바 층 순서란 넓이를 우선하는 방식에 따라 두 갈래 나무를 훑어보는 순서이다
넓이를 우선적으로 두 갈래 나무를 훑어보면 경험이 있는 프로그래머는 데이터 구조인 대기열을 떠올린다.대기열은 일종의 선입선출(FIFO) 데이터 구조로 우리는 순서대로 노드를 대기열에 넣고 방문할 때 노드를 대기열에서 제거하는 방식으로 광범위한 우선순위를 실현할 수 있다.방문할 때 첫 번째 왼쪽 노드나 오른쪽 노드가 비어 있는 노드만 찾으면 새 노드를 이 노드의 왼쪽 노드나 오른쪽 노드로 삽입할 수 있습니다.알고리즘에 대한 간단한 설명은 다음과 같습니다.

function insertInLevelOrder(root, data) {
    let visitNodeQueue = [];
    visitNodeQueue.push(root);
    while(visitNodeQueue.length != 0)
    {
        let currentNode = visitNodeQueue.shift();
        if (!currentNode.leftChild){
            currentNode.leftChild = new BinaryTreeNode(data, null, null);
            break;
        }
        else if (!currentNode.rightChild){
            currentNode.rightChild = new BinaryTreeNode(data, null, null);
            break;
        } else {
            visitNodeQueue.push(currentNode.leftChild);
            visitNodeQueue.push(currentNode.rightChild);
        }
    }
    return root;
}

두 갈래 트리 노드 삭제

두 갈래 나무의 노드를 삭제하려면 보통 두 가지 절차가 필요하다. 하나, 삭제할 노드를 찾아라.둘째, 노드를 삭제한 후 두 갈래 나무의 완전성을 확보해야 한다.첫 번째 단계는 이해하기 쉽다. 두 번째 단계는 삭제할 노드가 잎 노드가 아니라면 삭제한 후에 처리하지 않으면 두 갈래 나무 구조가 파괴되기 때문이다. 그래서 우리는 노드를 삭제한 후의 구조를 두 갈래 나무 구조라고 복원할 방법을 강구해야 한다.상대적으로 두 번째 절차의 실현은 좀 복잡하기 때문에 우리는 다른 방식으로 이 두 번째 절차를 회피하고 싶지만 노드를 삭제하는 조작을 실현할 수 있다.
우리는 만약 삭제된 노드가 잎 노드라면 별도의 처리를 하지 않아도 삭제된 두 갈래 나무인지 두 갈래 나무인지 보장할 수 있다는 것을 안다.그래서 우리는 삭제 조작을 잎 노드에 대한 삭제라고 바꿀 수 있다. 알고리즘은 문자로 다음과 같이 설명한다.

삭제할 노드를 찾습니다

적당한 잎 노드를 찾아 잎 노드의 데이터를 첫 번째 단계에서 삭제할 노드의 데이터로 덮어씁니다

두 번째 단계의 잎 노드를 삭제합니다

알고리즘 두 번째 단계에서 우리는 적당한 잎 노드가 마지막 층에서 가장 오른쪽에 있는 잎 노드라고 가정할 수 있다. 마찬가지로 우리는 넓이를 우선하는 방식으로 이 잎 노드를 찾을 수 있다.전체 삭제 알고리즘은 다음과 같이 Javascript로 설명됩니다.

function deleteTreeNode(root, data) {
    if (root == null) {
        return null;
    }
    if (root.leftChild == null && root.rightChild == null) {
        if (root.data === data) {
            return null;
        }
        return root;
    }

    let nodeToDeleted = null;
    let nodeDeepest = null;
    let visitNodeQueue = [root];
    while (visitNodeQueue.length != 0) {
        nodeDeepest = visitNodeQueue.shift();

        if (nodeDeepest.data == data) {
            nodeToDeleted = nodeDeepest;
        }

        if (nodeDeepest.leftChild) {
            visitNodeQueue.push(nodeDeepest.leftChild);
        }

        if (nodeDeepest.rightChild) {
            visitNodeQueue.push(nodeDeepest.rightChild);
        }
    }

    if (nodeToDeleted) {
        nodeToDeleted.data = nodeDeepest.data;
        deleteDeepestTreeNode(root, nodeDeepest);
    }

    return root;
}

위 코드에서 우리는 두 갈래 트리를 넓게 우선적으로 훑어보고 삭제할 노드 (node To Deleted) 와 교체할 잎 노드 (node Deepest) 를 지정합니다.이 두 노드를 포지셔닝한 후에 해야 할 일은 노드를 삭제할 데이터를 이 잎 노드라고 하는 데이터, 즉 이 줄 코드로 바꾸는 것이다.

nodeToDeleted.data = nodeDeepest.data;

그 다음에 잎 노드, 즉 이 줄 코드를 삭제합니다.

deleteDeepestTreeNode(root, nodeDeepest);

deleteDeepestTreeNode 이 함수는 잎 노드를 삭제하는 데 사용됩니다. 이 함수는 다음과 같습니다.

function deleteDeepestTreeNode(root, treeNode) {
    let visitNodeQueue = [];
    visitNodeQueue.push(root);
    while(visitNodeQueue.length != 0) {
        let currentNode = visitNodeQueue.shift();
        if (currentNode == treeNode) {
            // only one node in this tree, and this node is to be deleted
            return null;
        }

        if (currentNode.leftChild) {
            if (currentNode.leftChild == treeNode) {
                currentNode.leftChild = null;
                return root;
            } else {
                visitNodeQueue.push(currentNode.leftChild);
            }
        }
        if (currentNode.rightChild){
            if (currentNode.rightChild == treeNode) {
                currentNode.rightChild = null;
                return root;
            } else {
                visitNodeQueue.push(currentNode.rightChild);
            }
        }
    }

    return root;
}

delete Deepest TreeNode의 핵심도 두 갈래 나무를 우선적으로 훑어보고 삭제할 잎 노드의 부모 노드를 찾습니다. 잎 노드가 이 아버지 노드의 왼쪽 노드나 오른쪽 노드라면 왼쪽 노드나 오른쪽 노드를 인용하면 됩니다.

총결산

이상의 알고리즘을 실현함으로써 우리는 트리와 같은 비선형 구조를 반복할 때 대기열로 넓이를 우선하는 반복을 자주 실현하고 교묘한 알고리즘을 실현했다.유사한 것은 창고를 통해 깊이를 우선적으로 트리나 그림을 훑어보는 것도 있으니 나중에 소개해 드리겠습니다.