Tree | 트리

Github logo Edit on GitHub

트리는 비순차적 자료구조이며 정보를 쉽게 검색하기 위해 저장할 때 유용하다.

트리는 계층 구조를 추상화한 모델이다.

트리 용어

트리는 부모-자식 관계를 가진 다수의 노드로 구성된다.

최상위 노드를 제외하고 각 노드는 부모 노드를 가지며 다수 자식 노드를 가질 수 있고 하나도 없을 수도 있다.

트리에서 최상위 노드는 루트라고 하며 부모가 없는 노드다.

트리의 온소는 노드라고 부르며 내부 노드, 외부 노드가 있다.

1개 이상의 자식을 가진 노드가 내부 노드이며 자식이 하나도 없는 노드를 외부 노드 또는 리프라고 한다.

노드는 조상과 후손을 가질 수 있다.

조상은 부모, 조부모, 증조부모 등 상위 계층의 노드를, 후손은 자식, 손자, 증손자 등 하위 계층의 노드를 각각 가리킨다.

서브 트리는 노드와 후손으로 구성된다.

노드의 깊이란 조상의 개수다.

트리의 높이는 깊이의 최대치이다. 트리를 레벨이라고 부르기도 한다.

이진 트리와 이진 탐색 트리

이진 트리는에서 노드는 좌, 우측에 각각 하나씩, 최대 2개의 자식 노드를 가진다.

따라서 노드의 삽입, 조회,삭제를 효과적으로 수행할수 있다.

이진 탐색 트리는 이진 트리의 변형으로 좌측 자식 노드에는 더 작은 값을, 우측 자식 노드에는 더 큰 값을 들고 있다는 차이점이 있다.

BinarySearchTree 클래스 만들기

function BinarySearchTree() {
  var Node = function(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  };
  var root = null;
}

연결 리스트와 마찬가지로 노드간 연결은 포인터로 나타낸다.

트리는 2개의 포인터를 가지는데 각각 좌측, 우측 자식 노드를 가리킨다.

따라서 우선 트리 노드를 표현하는 Node 클래스를 선언한다.

트리에서는 키로 노드를 식별한다.

연결 리스트의 LinkedList 클래스에서 사용했던 패턴과 비슷하다.

자료 구조의 첫 번째 노드를 변수로 선언해서 제어하는 식으로 진행된다.

하지만 트리에서 헤드가 아닌 루트라는 점이 다르다.

insert(키) : 새 키를 삽입한다.

search(키) : 해당 키를 가진 노드가 존재하는지 true/false로 반환

inOrderTraverse: 중위 순회 방식으로 트리의 전체 노드를 방문

preOrderTraverse: 전위 순회 방식으로 트리 전체 노드를 방문

postOrderTaverse: 후위 순회 방식으로 트리의 전체 노드를 방문

min: 트리의 최소 값/키를 반환

max: 트리의 최대 값/키를 반환

remove(키) : 키를 삭제

트리에 키 삽입하기

this.insert = function(key) {
  var newNode = new Node(key);
  if (root === null) {
    root = newNode;
  } else {
    insertNode(root, newNode);
  }
};

트리에 새 노드를 삽입할때는 세 단계 작업이 필요하다.

첫쨰, 새 노드에 해당하는 Node 인스턴스를 생성한다. 생성자에는 트리에 추가할 값을 인자로 넘겨주며, left, right 포인터는 null로 초기화한다.

둘쨰, 추가할 노드가 트리의 최초 노드일 경우, 즉 트리가 비어 있을 때는 이 노드를 루트로 세팅한다.

셋쨰, 루트를 제외한 다른 위체에 추가하는 일반적인 경우, 다음의 프라이빗 헬퍼 함수를 insertNode를 호출한다.

var insertNode = function(node, newNode) {
  if (newNode.key < node.key) {
    if (node.left === null) {
      node.left = newNode;
    } else {
      insertNode(node.left, newNode);
    }
  } else {
    if (node.right === null) {
      node.right = newNode;
    } else {
      insertNode(node.right, newNode);
    }
  }
};

insertNode 함수는 새 노드를 추가할 위치를 정확히 찾는 것이다.

insertNode 함수에 루트와 새 노들르 인자로 호출해서 새 노드를 어디에 추가할지 결정한다.

새 노드의 키가 현재 노드의 키보다 작으면 노드의 좌측 자식 노드를 확인한다.

만약 좌측 노드가 없으면 새 노드를 넣고 아니면 insertNode 함수를 재귀 호출해서 하위 레벨로 내려간다.

새 노드의 키가 현재 노드의 키보다 크고 우측 자식 노드가 없으면 새 노드를 넣는다. 그렇지 않으면 재귀 호출을 한다.

트리 순회

트리의 모든 노드를 방문해서 각 노드마다 어떤 작업을 수행하는 것을 트리 순회라고 한다.

트리의 최상단에서 시작해서 하위 레벨로 내려가는 방법, 최하위부터 상위 레벨로 가는 방법, 좌,우 중에서 어느 쪽을 우선하는 방법

에 따라 순회 방법은 중위, 전위, 후위 세가지로 분류된다.

중위 순회

중위 순회는 BST의 노드를 오름차순, 즉 작은 값에서 큰 값 방향으로 방문한다.

트리 정렬시 사용되는 방법이다.

inOrderTraverse 메서드가 인자로 취하는 콜백 함수에는 노드 방문시 수행할 작업을 기술한다. 이러한 것을 방문자 패턴이라고 한다.

BST 구현 알고리즘은 대부분 재귀 호출을 사용하므로 프라이빗 헬퍼 함수를 만들어 node와 callback을 전달한다.

this.inOrderTraverseNode = function(node, callback) {
  if (node !== null) {
    inOrderTraverse(node.left, callback);
    callback(node.key);
    inOrderTraverse(node.right, callback);
  }
};

일단 인자 node가 null인지 확인한다.

그 다음 자기 자신의 재귀 호출해서 좌측 자식 노드를 방문하고 방문한 노드에서 어떤 작업을 수행하고 우측 자식 노드를 방문한다.

전위 순회

전위 순회에서는 자식 노드 보다 노드 자신을 먼저 방문한다. 구조화된 문서를 출력할때 많이 이용한다.

var preOrderTraverseNode = function(node, callback) {
  if (node !== null) {
    callback(node.key);
    preOrderTraverseNode(node.left, callback);
    preOrderTraverseNode(node.right, callback);
  }
};

전위 순회는 일단 노드를 먼저 방문한 후 좌측 노드와 우측 노드를 방문한다는 점에서 중위 순회와 순서 차이가 있다.

후위 순회

후위 순회는 자식 노드를 노드 자신보다 먼저 방문한다. 디렉토리와 서브 디렉토리의 파일 용량을 계산할때 쓰는 방법이다.

var postOrderTraverseNode = funcion(node, callback) {
    if(node !== null) {
        postOrderTraverseNode(node.left, callback);
        postOrderTraverseNode(node.right, callback);
        callback(node.key);
    }
}

후위 순회는 좌측 노드를 가장 먼저 방문하고 그 다음 우측 노드, 마지막으로 노드 자신을 방문한다.

중위, 전위, 후위 세가지 순회 알고리즘은 비슷하다. 다만 코드의 실행 순서가 다를 뿐이다.

트리 노드 검색

트리에서 노드를 검색하는 세 가지 유형이다.

최소값 찾기

최대값 찾기

특정 값 찾기

최소/최대 값 찾기

this.min = function() {
  return minNode(root);
};
var minNode = function(node) {
  if (node) {
    while (node && node.left !== null) {
      node = node.left;
    }
    return node.key;
  }
  return null;
};

minNode 메서드는 서브트리 또는 트리 전체에서 최소값을 찾는다. 그리고 트리의 마지막 레벨에 위치한 노드에 도달할 때까지 트리의 left 간선을 따라 순회한다.

max 메서드도 비슷하다

this.max = function() {
  return maxNode(root);
};
var maxNode = function(node) {
  if (node) {
    while (node && node.right !== null) {
      node = node.right;
    }
    return node.key;
  }
  return null;
};

언제나 최소값은 트리 좌측, 최대값은 트리 우측을 따라 쭉 내려가면 찾을 수 있다.

특정 값 찾기

this.search = function(key) {
  return searchNode(root, key);
};
var searchNode = function(node, key) {
  if (node === null) {
    return false;
  }
  if (key < node.key) {
    return searchNode(node.left, key);
  } else if (node.key < key) {
    return searchNode(node.right, key);
  } else {
    return true;
  }
};

searchNode 메서드는 서브트리 또는 전체 트리에서 특정 노드를 찾는다.

node 인자가 null 이면 유효하지 않은 값이므로 false를 처리한다.

node가 null이 아니면 이후에 또 다른 분기가 이루어진다.

찾는 키가 현재 노드의 키보다 작다면 좌측 자식 노드 쪽 서브트리를 따라서 검색을 계속하고 반대로 더 크다면 우측 자식 노드 쪽 서브트리를 따라서 검색을 계속한다.

두 가지가 아니라면 현재 노드의 키가 바로 찾는 키이므로 검색이 완료된것이므로 true를 반환한다.

노드 삭제

삭제할 노드의 키를 인자로 받고 안에서 다시 root와 key를 인자로 removeNode 메서드를 호출한다.

여기서 removeNode의 반환 값을 root로 다시 세팅하는 것이 중요하다.

var removeNode = function(node, key) {
  if (node === null) {
    return null;
  }
  if (key < node.key) {
    node.left = removeNode(node.left, key);
    return node;
  } else if (key > node.key) {
    node.right = removeNode(node.right, key);
    return node;
  } else {
    if (node.left === null && node.right === null) {
      node = null;
      return node;
    }
    if (node.left === null) {
      node = node.right;
      return node;
    } else if (node.right === null) {
      node = node.left;
      return node;
    } else {
      var aux = findMinNode(node.right);
      node.key = aux.key;
      node.right = removeNode(node.right, aux.key);
      return node;
    }
  }
};

노드가 null 이면 이 트리에 해당 키가 없다는 뜻이므로 null을 먼저 반환한다.

null 이 아니라면 다음 코드로 넘어가 트리에서 노드를 찾아야 한다.

찾는 키가 현재 노드의 키보다 작다면 트리의 좌측 간선을 따라 다음 노드로 이동하고 그 반대라면 트리의 우측 간선을 따라 다음 노드로 흘러간다.

그 결과 키를 찾았다면 다음 세가지 경우에 따라 처리를 해야한다.

리프 노드인 경우

첫째 자식 노드가 없는 리프 노드인 경우

노드에 null을 대입하는게 아니라 연결 리스트 처럼 포인터를 처리해야한다.

리프 노드는 자식 노드는 없지만 부모 노드는 있는 부모 노드 또한 null로 만들어줘야 하는데 이것은 null을 반환하면 된다.

삭제할 노드는 이미 null 이므로 이 노드를 가리키는 부모 노드의 포인터 역시 null이 되어야 한다.

이러한 이유로 노드의 값을 함수에서 반환하는 것이미 부모 노드는 이 반환 값을 건네 받는다.

좌/우측 어느 한쪽에만 자식 노드가 있는 경우

둘쨰, 좌측 또는 우측 어느 한쪽에만 자식 노드를 갖고 있는 노드일 경우

이럴 때는 해당 노드를 건너뛰어 할아버지가 손주의 손을 직접 잡게 하면 된다.

좌측 자식 노드가 없을 경우 우측 자식 노드가 존재한다는 뜻이므로 우측 자식 노드를 가리키도록 바꾸고 수정된 노드를 반환한다.

반대의 경우 마찬가지로 좌측 자식 노드를 가리키게 바꾸고 수정된 노드를 반환한다.

두 자식을 모두 가진 노드일 경우

자식 노드와 함꼐 삭제하려면 다음 네 단계를 거쳐야 한다.

  1. 우측 서브트리로부터 최소 노드를 찾는다.

  2. 이렇게 찾은 최소 노드의 값으로 수정한다. 삭제할 노드의 키 자체가 교체되므로 결국 삭제가 되는 것이다.

  3. 하지만 동일 키를가진 노드가 생겨서 우측 서브트리의 최소 노드는 삭제해야 하는데 이 노드를 삭제한 노드 위치로 옮기면 된다.

  4. 마지막으로 수정된 노드를 반환한다.

findMinNode 메서드는 min 메서드와 동일한 기능이지만 노드 자체를 반환한다는 차이점이 있다.

이진 트리 내용 보충

BST는 노드의 개수에 따라 한쪽으로 아주 깊게 치우져 간선이 길게 늘어질수 있다.

이런 형태의 트리는 노드 추가/삭제 및 조회 시 간선에 따라 성능 문제가 발생할수 있다.

그래서 AVL트리라는 대안이 만들어 졌다.

AVL 트리는 스스로 균형을 잡는 BST 트리의 일종으로 어떤 노드의 좌/우측 서브트리의 높이가 1 이상 차이가나지 않도록 조정한다.

Previous
Sort | 정렬
Next
Graph | 그래프