이진 트리란?

이진 트리는 각각의 노드가 있고 각 노드는 최대 2개의 자식 노드를 가질수 있다. 맨위 의 노드는 루트(root)라고 불리고각 노드들은 유티크한 값을 가진다.

가장 흔하게 쓰이는 이진 트리는 이진 탐색 트리로 왼쪽에는 노드보다 작은 숫자 오른쪽에는 노드보다 큰 숫자가 온다.

https://www.baeldung.com/java-binary-tree

 

노드를 넣는 과정 :

private Node addRecursive(Node current, int value) {
    if (current == null) {
        return new Node(value);
    }
 
    if (value < current.value) {
        current.left = addRecursive(current.left, value);
    } else if (value > current.value) {
        current.right = addRecursive(current.right, value);
    } else {
        // value already exists
        return current;
    }
 
    return current;
}

- 현재의 노드의 값이 비어있으면 해당 새로운 노드의 값을 넣고 리턴한다.

- 새로운 노드가 현재 노드의 값보다 낮을경우 현재 노드의 왼쪽 값을 현재의 값으로 매개변수로넣고 재귀 함수를 호출한다.

- 그 반대의 경우 오른쪽 값을 넣는다.

 

노드를 찾는 과정 :

private boolean containsNodeRecursive(Node current, int value) {
    if (current == null) {
        return false;
    } 
    if (value == current.value) {
        return true;
    } 
    return value < current.value
      ? containsNodeRecursive(current.left, value)
      : containsNodeRecursive(current.right, value);
}

- 찾는 값이 현재 노드의 값과 같은 경우 true를 리턴

- 찾는 값이 현재의 노드의 값보다 작을 경우 재귀함수를 호출하여 현재 노드의 왼쪽의 값과 다시 비교하게 끔한다.

- 그 반대의 경우 재귀 함수를 호출하여 현재 노드의 오른쪽의 값과 비교하게 끔 한다.

 

노드를 삭제하는 과정 :

노드를 삭제할때 가정할수 있는 상황은 총 3가지가 있다. :

https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/

첫번째는 노드가 자식이 없을때 이다. 이때는 간단하게 해당 노드만 삭제하면 된다.

두번째는 노드가 하나의 자식이 있을때 이다. 해당 노드를 삭제하고 해당 노드의 자식을 해당 노드의 자리를 차지하게 끔 하면된다.

세번째는 노드가 두개의 자식 모두 가지고 있을때 이다. 이럴 경우 해당 노드를 계승할수 있는 노드를 찾아야한다.

void deleteKey(int key) 
    { 
//해당 값을 찾으면 해당 값의 자리를 자식 값이 대채하게 됨
        root = deleteRec(root, key); 
    } 
  
    
    Node deleteRec(Node root, int key) 
    { 
        //트리가 비어있을경우 그냥 리턴
        if (root == null)  return root; 
  
     //재귀를 하면서 계속 타고 내려감
        if (key < root.key) 
            root.left = deleteRec(root.left, key); 
        else if (key > root.key) 
            root.right = deleteRec(root.right, key); 
  
        //키와 똑같은 노드를 발견했을 경우
        else
        { 
            //노드가 자식이 없거나 자식이 하나인경우
            if (root.left == null) 
                return root.right; 
            else if (root.right == null) 
                return root.left; 
  
            //노드가 자식이 두개인 경우 해당 노드의 대신 할 수 있는 계승값를 찾으러감
            root.key = minValue(root.right); 
  
            // 계승값과 똑같은 값이 있을씨 지움
            root.right = deleteRec(root.right, root.key); 
        } 
  
        return root; 

 

 int minValue(Node root) 
    { 
        int minv = root.key; 
        while (root.left != null) 
        { 
            minv = root.left.key; 
            root = root.left; 
        } 
        return minv; 
    }