이진트리

Full vs Complete Binary Tree

이진트리에 full 하고 complete binary tree라는 개념이 있다. 

full binary tree(완전이진트리) 는 모든 level의 Node들이 꽉 차있는 형태이고, 

complete binary tree는 마지막 level의 노드 중 왼쪽을 순서대로 제외하고 채워져있는 이진트리이다.

 

https://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html

 

 

 

일반적으로 이진트리를 구현할 때는 연결리스트를 활용한다.

 연결리스트를 택했을 때  Insert, Search, Delete 중, Serach의 시간복잡도는 O(N)이다. 배열이든, 연결리스트이든 시간 복잡도가 O(N)이 되는 구조이다. 따라서 시간 복잡도를 줄이기 위해, 다양한 알고리즘이 나온다.   

 이진트리의 경우에도, 최악의 경우에는 시간복잡도가 O(N)이 된다.

 이진트리의 종류 중 하나인 Binary Search Tree는 부모노드가 왼쪽 자식보다는 크고 오른쪽 자식보다는 작다는 특징이 있다. 이진트리 구현에 있어서 자기보다 큰 값들 중 가장 작은 값(successor)와 자기보다 작은 값들 중 가장 큰 값(predecessor)를 활용해 Delete 기능을 구현하는 것이 다소 까다로웠다.

 아래는 binary search tree에서 insert, search, delete 기능을 자바스크립트로 구현한 코드이다. 이진트리를 visualize하는 코드가 있지만 아직 미완성이다.

function Node()
{
    this.data = null
    this.left = null
    this.right = null
    this.parent = null
    this.x = null
    this.y = null
}

function BinaryTree(data)
{
    this.root =new Node()
    this.root.data = data
    this.root.x = 500
    this.root.y = 0
    this.root.parent = null
}

function pix(data)
{
    return String(data)+'px'
}

function draw(node)
{
    var tree =document.createElement('span')
    tree.style.top = pix(node.y)
    tree.style.left = pix(node.x)
    tree.textContent = node.data
    document.body.appendChild(tree)
}

BinaryTree.prototype.visualize = function()
{

    document.body.innerHTML='';//init

    var queue = [this.root]

    while(queue.length!==0)
    {
        var cur = queue.shift()
        draw(cur)
        if(cur.right)
        {
            queue.push(cur.right)
        }
        if(cur.left)
        { 
          queue.push(cur.left)
        }

    }
    
}

BinaryTree.prototype.insert = function(data)
{
    var cur = this.root
    var bef = this.root
    var chg = 20;
    var toinsert = new Node()
    toinsert.data = data
    var tmp;
  

    while(cur!==null)
    {   
        bef = cur
        if(cur.data>data)
        {            
            cur = cur.left
            tmp = 'left'
        }
        else{
            cur = cur.right
            tmp='right'
        }
 
    }

    bef[tmp] = toinsert
    chg = tmp==='left'?-chg:chg;
    toinsert.x = bef.x + chg;
    toinsert.y = bef.y + Math.abs(chg)
    toinsert.parent = bef
}

BinaryTree.prototype.search = function(data)
{
    var cur = this.root
    var bef = this.root

    while(cur!==null)
    {   if(cur.data ===data)
        {
            return cur
        }
        
        if(cur.data>data)
        {   
            cur = cur.left
 
        
        }
        else if(cur.data<data){
            
            cur = cur.right
        }

        bef = cur
 
    }
    return false
}

BinaryTree.prototype.successor = function(data)
{
    var cur = this.search(data)
    var bef;

    if(!cur)
    {
        return 'Given Data Not Found'
    }
    //오른쪽 자식이 있다면
    if(cur.right!==null)
    {   
        cur = cur.right;
        //왼쪽 자식 끝에 도달할 때까지
        while(cur.left!==null)
        {   
            cur = cur.left
        }
        return cur
    }
    //오른쪽 자식이 없다면 부모 노드로 올라가다가
    else{
        while(cur.parent!==null)
        {   
            if(cur===cur.parent.left)
            {
                return cur.parent
            }
            else{
                cur = cur.parent
            }
        }
        return 'Not Found'
    }
}

BinaryTree.prototype.delete = function(data)
{   
    var cur  = this.search(data)
    //자식이 없는 경우
    if(!cur.right&&!cur.left)
    {
        var tmp = cur===cur.parent.left?'left':'right'
        cur.parent[tmp]=null
    }//자식이 둘다 있는 경우
    else if(cur.right&&cur.left)
    {
        var suc = this.successor(cur.data)
        cur.data = suc.data
        //successor의 오른쪽 자식이있다면
        if(suc.right)
        {   
            var tmp = suc===suc.parent.left?'left':'right'
            suc.parent[tmp]  = suc.right;
            suc.right.parent =  suc.parent[tmp] 
        }//없다면
        else{
            var tmp = suc===suc.parent.left?'left':'right'
            suc.parent[tmp]=null;
        }

    }//자식이 하나인 경우
    else{
        //오른쪽 자식인 경우
        var tmp = cur===cur.parent.left?'left':'right'
        if(cur.right)
        {
            cur.parent[tmp] = cur.right
            cur.right.parent = cur.parent

        }//왼쪽 자식인 경우
        else{
            cur.parent[tmp] = cur.left
            cur.left.parent = cur.parent

        }

    }
}


var bst = new BinaryTree(3)


bst.insert(6)
bst.insert(7)
bst.insert(4)
bst.insert(5)
bst.insert(2)

bst.visualize()
var num= 7
var suc = bst.successor(num)
console.log(`${num}succesor`,suc)
setTimeout(function()
{bst.delete(6)
bst.visualize()
},1000);

// var result = bst.search(5)`
// var suc = bst.successor(3)
// bst.delete(3)
// bst.delete(4)
// //bst.delete(4)
// var result = bst.search(4)
// console.log(result)