[javascript] tree , 삽입과 삭제 (3)

포스팅 전 주저리 : 자스민도 슬슬 확장해보려는 마음이 생겨 에브리타임에 다시 가입했다. 그런데 수강신청기간이라 그런지 게시판은 수강신청에 대해서 활발하게 대화 중이였는데, 속이려는 놈, 동요하는 놈, 이상한 놈이 섞여서 혼돈의 도가니였다. 그중 가장 웃긴놈은 학교 근처에서 접속하면 3분 먼저 접속이 가능하다. 조금 더 접속이 잘된다. 이런 말 하는 놈이였는데 결국 못 참고 ppt로 헛 소문들 정리해줬다. 

 

tree에 삽입 

 

2부에서 설명 했듯이 배열로 이진트리를 만들면 왼쪽 자식노드의 인덱스 번호는 부모노드의 인덱스 * 2 이며, 오른쪽 자식노드는 부모의 (인덱스 * 2) +1 의 인덱스 번호를 가진다. 그렇기에 이진탐색트리에 새롭게 삽입될 인덱스 번호를 삽입하는 일은 현재 노드의 데이터를 삽입하려는 데이터와 비교 한 후 올바른 인덱스로 이동하는 작업을 해당 인덱스에 데이터가 없을 때 까지 반복하면 된다. 

 

삽입하는 방법은 반복문을 이용하거나 재귀문을 사용해서 해당 인덱스에 있는 데이터를 조사할 수 있다. 

 

순환적인 삽입함수

 

reclusiveInsert(i,item){
        if(i == null ) i = 1;
        if(this.array[i] < item){
            this.reclusiveInsert((i * 2 ) + 1, item);
        }else if(this.array[i] > item){
            this.reclusiveInsert(i*2, item)
        }else if(this.array[i] == item){
            console.log(`${item} 이 존재 합니다.`);
            return ;
        }else if(this.array[i] == null){
            this.array[i] = item;
            this.preorder();
        }
    }

 

함수의 인자로는 배열의 방을 탐색할 인덱스번호가 새롭게 부여된다. 그리고 해당 인덱스의 방이 비었다면 해당 인덱스에 해당하는 방에 삽입할 데이터를 넣고 중위 탐색을 한다. 

 

반복적인 삽입함수

 

  iterativeInsert(item){
        let i = 1;
        while(this.array[i] != null){
            if(this.array[i] < item){
                i = (i * 2) + 1;
            }else if(this.array[i] > item){
                i = i * 2;
            }else if(this.array[i] == item){
                console.log(`${item}이 존재합니다.`);
                return;
            }
        }        
        this.array[i] = item;
        this.preorder();
    }

 

반복적인 함수도 삽입함수랑 비슷하게 작동 한다. 

 

데이터의 삭제

데이터의 삭제는 삽입과는 달리 조금 더 복잡하다. 해당 노드가 잎(leap)이라면 크게 신경 쓰지 않아도 되지만 해당 노드에 자식노드가 한개 혹은 두개 있다면 삭제해야 할 노드의 자식 노드들과 부모노드간의 관계를 다시 정리해야한다. 

 

 

위 트리에서 노드 7을 없애면 어떤 자식노드를 해당 노드를 대신하여 후계자로 해야 할지 결정해야 한다 후보자는 6의 맨 오른쪽 노드와 9의 맨 왼쪽 노드가 후계자 후보가 된다. 어떤 후보를 현재 7 노드와 대치하여도 해당 트리는 이상하지 않다. 

 

삭제할 노드가 leap인 경우

 

 

해당 노드가 leap인 경우 그저 단순히 노드의 연결을 끊어 주면 된다. 나는 배열로 만들었기 때문에 해당 노드에 해당 하는 인덱스를 찾은뒤 해당 배열의 노드를 null 로 만들어 주었다. 

 

삭제할 노드가 두개의 자식노드를 가진 경우

 

해당 노드가 두개의 자식노드를 가지고 있을 때 삭제할 노드의 자식노드중 오른쪽 노드의 가장 왼쪽 노드의 데이터를 삭제할 노드 데이터의 바꾸기만 하면 된다. 그리고 옮긴 데이터는 null로 바꿔주기만 하면된다. 

 

삭제할 노드가 한개의 자식노드를 가진 경우

 

 

삭제할 노드가 한개의 자식노드를 가지고 있다면 해당 자식 노드의 모든 자식 노드들의 레벨을 한칸씩 위로 올려야 한다.  나는 배열로 이 트리를 만들었기 때문에 모든 노드들의 인덱스를 전부 바꿔야 했다. 만약 내가 연결리스트로 만들었다면 삭제할 노드의 자식노드 한개만 삭제할 노드의 부모노드와 연결해주기만 하면 됬었다. 

 

삭제할 노드의 인덱스를 반환하는 함수 

 

search(item){
        let i = 1;
        while(this.array[i] != null){
            if(this.array[i] < item){
                i = (i * 2) + 1;
            }else if(this.array[i] > item){
                i = i * 2;
            }else if(this.array[i] == item){
                return i;
            }
        }        
    }

 

삭제하는 함수

 

  delete(item){
        let removedIndex = this.search(item); // 삭제할 노드의 인덱스를 가지고 있다. 
        
        if(this.array[removedIndex * 2] == null && this.array[(removedIndex * 2)+1] == null){
            this.array[removedIndex] = null;
        }else if(this.array[removedIndex*2] != null && this.array[(removedIndex*2)+1] != null){
            let heirIndex = (removedIndex * 2) + 1; 
            while(this.array[heirIndex] == null){
                heirIndex *= 2;
            }
            this.array[removedIndex] = this.array[heirIndex]
            this.array[heirIndex] = null;
        }else{
            let childIndex = removedIndex;
            if(this.array[(removedIndex * 2)] == null){
                let heirIndex = (removedIndex * 2) + 1;
                this.array[childIndex] = this.array[heirIndex];
                this.move(childIndex,heirIndex);
            }else if(array[(removedIndex * 2) +1] == null){
                let heirIndex = (removedIndex * 2);
                this.array[childIndex] = this.array[heirIndex];
                this.move(childIndex,heirIndex);
            }
        }   
    }

 

삭제할 노드가 leap인 경우와 2개있는 노드는 어렵지 않다. 우리가 주목해야하는 점은 자식 노드가 1개 있는 노드를 삭제하는 부분이다. 

 

먼저 삭제할 노드의 왼쪽과 오른쪽 중 null이 아닌 노드를 알아야한다. 그리고 자식노드를 삭제할 노드자리에 넣는다. 

 

그리고 자식노드의 자식노드들의 레벨을 한 단계 씩 올리기 위해 재귀적인 함수를 호출 한다. 

 

자식 노드의 레벨을 올리는 함수

 

 move(movedIndex, heirIndex){
        if(this.array[heirIndex * 2] != null){
            this.array[movedIndex * 2] = this.array[heirIndex * 2];
            this.move(movedIndex * 2,heirIndex * 2);
        }else{
            this.array[heirIndex] = null;
        }

        if(this.array[(heirIndex * 2) +1 ] != null){
            this.array[(movedIndex * 2) + 1] = this.array[(heirIndex * 2) +1];
            this.move((movedIndex * 2) +1,(heirIndex * 2)+1);
        }else{
            this.array[heirIndex] = null;
        }
    }

 

전체 

class BinarySearchTree{
    constructor(){
         this.array = [null,20,11,30,8,14,25,38,4,null,null,null,null,null,null,42]
    }
    //중위 순회
    inorder(i){
        if(i == null) i = 1;
        if(this.array[i] != null){
            this.inorder(i * 2)
            console.log(this.array[i]);
            this.inorder((i * 2) +1);
        }
    }

    preorder(i){
        if(i == null) i = 1;
        if(this.array[i] != null){
            console.log(this.array[i]);
            this.preorder(i * 2)
            this.preorder((i * 2) +1);
        }
    }
    postorder(i){
        if(i == null) i = 1;
        if(this.array[i] != null){   
            this.postorder(i * 2)
            this.postorder((i * 2) +1);
            console.log(this.array[i]);
        }
    }

    reclusiveInsert(i,item){
        if(i == null ) i = 1;
        if(this.array[i] < item){
            this.reclusiveInsert((i * 2 ) + 1, item);
        }else if(this.array[i] > item){
            this.reclusiveInsert(i*2, item)
        }else if(this.array[i] == item){
            console.log(`${item} 이 존재 합니다.`);
            return ;
        }else if(this.array[i] == null){
            this.array[i] = item;
            this.preorder();
        }
    }
    
    iterativeInsert(item){
        let i = 1;
        while(this.array[i] != null){
            if(this.array[i] < item){
                i = (i * 2) + 1;
            }else if(this.array[i] > item){
                i = i * 2;
            }else if(this.array[i] == item){
                console.log(`${item}이 존재합니다.`);
                return;
            }
        }        
        this.array[i] = item;
        this.preorder();
        console.log(" ");

    }

    delete(item){
        let removedIndex = this.search(item); // 삭제할 노드의 인덱스를 가지고 있다. 
        
        if(this.array[removedIndex * 2] == null && this.array[(removedIndex * 2)+1] == null){
            this.array[removedIndex] = null;
        }else if(this.array[removedIndex*2] != null && this.array[(removedIndex*2)+1] != null){
            let heirIndex = (removedIndex * 2) + 1; 
            while(this.array[heirIndex] == null){
                heirIndex *= 2;
            }
            this.array[removedIndex] = this.array[heirIndex]
            this.array[heirIndex] = null;
        }else{
            let childIndex = removedIndex;
            if(this.array[(removedIndex * 2)] == null){
                let heirIndex = (removedIndex * 2) + 1;
                this.array[childIndex] = this.array[heirIndex];
                this.move(childIndex,heirIndex);
            }else if(array[(removedIndex * 2) +1] == null){
                let heirIndex = (removedIndex * 2);
                this.array[childIndex] = this.array[heirIndex];
                this.move(childIndex,heirIndex);
            }
        }   
    }
    move(movedIndex, heirIndex){
        if(this.array[heirIndex * 2] != null){
            this.array[movedIndex * 2] = this.array[heirIndex * 2];
            this.move(movedIndex * 2,heirIndex * 2);
        }else{
            this.array[heirIndex] = null;
        }

        if(this.array[(heirIndex * 2) +1 ] != null){
            this.array[(movedIndex * 2) + 1] = this.array[(heirIndex * 2) +1];
            this.move((movedIndex * 2) +1,(heirIndex * 2)+1);
        }else{
            this.array[heirIndex] = null;
        }
    }

    search(item){
        let i = 1;
        while(this.array[i] != null){
            if(this.array[i] < item){
                i = (i * 2) + 1;
            }else if(this.array[i] > item){
                i = i * 2;
            }else if(this.array[i] == item){
                return i;
            }
        }        
    }
}

const test = new BinarySearchTree();

// test.inorder();
// test.reclusiveInsert(null,45);
test.iterativeInsert(7)
test.iterativeInsert(46)
test.iterativeInsert(47)
test.iterativeInsert(45)
test.iterativeInsert(49)

test.delete(38);
test.inorder();

 

정리하며 

배열로 이진탐색트리를 정리한 글이 없어서 해당 예제를 만들어 본건데 안하는 이유가 있었다. 연결리스트에 비해서 많은 연산이 필요하고 배열에 빈공간이 많아진다.