방앗간

※ 재귀 add 메소드 - 재귀로 호출하는 add 메소드는 다음 코드 예시와 같다 public void add(Node parent, Node new Node){ // newNode의 data가 parent의 data보다 크면 트리의 오른쪽에 추가하면 된다 if (((Comparable)newNode.data.compareTo(parent.data)>0{ if (parent.right == null){ parent.right = newNode; newNode.parent = parent; currentSize++; } else add(parent.right, newNode); // newNode의 data가 parent의 data보다 작거나 같으면 트리의 왼쪽에 추가하면 된다 else{ if (paren..

※ add 메소드 - AVL 트리의 클래스 생성자, add 메소드에 대한 코드이다. 클래스 생성 후, 트리가 비어있으면 노드 추가 비어있지 않다면 add 메소드를 재귀로 호출한다. // AVL 클래스의 생성자 public AVLTree(){ root = null; currentSize = 0; } // add 메소드 public void add(E obj){ Node node = new Node(obj); // 트리가 비어있을 경우 if (root == null){ root = node; currentSize++; return; } // 트리에 노드가 있을 경우 add 메소드를 재귀로 호출 add(root, node); }

※ 노드 - AVL 트리의 노드를 만드는 코드는 다음과 같다. left, right 노드만이 아니라, 기능을 간단히 구현하기 위해 부모 노드에 대한 포인터도 있다. class Node{ T data; Node left; Node right; Node parent; // 생성자 public Node(T obj){ data = obj; parent = left = right = null; } }

※ AVL 트리 - AVL 트리는 스스로 균형을 잡는 이진 탐색 트리로 AVL 트리에서는 좌측과 우측의 높이 차가 항상 1보다 작거나 같아야 함 상단 그림의 좌측 트리는 AVL 트리의 규칙을 위반하였기 때문에 AVL 트리가 아니지만 우측 트리는 AVL 트리의 규칙을 만족하여 AVL 트리라고 볼 수 있다.

※ 트리:회전 - 다음과 같이 임시 포인터를 사용해 좌측 회전, 우측 회전 구현한다 // 좌측 회전: 조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮깁니다. public Node leftRotate (Node node){ Node tmp = node.right; // set temp=grandparents right child node.right = tmp.left; // set grandparents right child=temp left child tmp.left = node; // set temp left child=grandparent return tmp; // use temp instead of grandparent } // 우측 회전: 조부모 노드를 부모 노드의 오른쪽 자식 노드 위치로 ..

※ 트리: 회전 - 트리가 한 쪽으로 치우치지 않은 경우는 우측 회전과 좌측 회전을 모두 사용해 불균형을 해소한다. 1. 불균형이 우측 자식의 좌측 서브 트리에서 나타나는 경우 - 크기 관계는 (부모 노드) > (자식 노드) > (조부모 노드)이다. 자식 노드에 대해 부모 노드를 우측 회전 후 좌측 회전을 해 조부모 노드를 부모 노드의 좌측 자식 노드 위치로 옮겨준다. 2. 불균형이 좌측 자식의 우측 서브트리에서 나타나는 경우 - 크기 관계는 (부모 노드) > (조부모 노드) > (자식 노드)이다. 자식 노드에 대해 부모 노드를 좌측 회전 후 우측 회전을 해 조부모 노드를 부모 노드의 우측 자식 노드 위치로 옮겨준다.

※ 트리: 회전 소개 - 균형 잡힌 트리를 만들기 위해 트리의 노드 위치를 바꾸는 과정을 회전이라고 한다. 연결 리스트처럼 한 방향으로 나열된 트리는 균형 잡혀 있지 않다고 표현을 하는데 균현 잡힌 트리에서는 특정 요소를 탐색하는 시간 복잡도가 O(logn) 이지만 균형 잡히지 않은 트리에서는 연결 리스트와 같은 O(n)이 된다. 따라서, 데이터를 효율적으로 관리하기 위해서는 트리를 균형 있게 만드는 것이 중요하다. 조부모 노드, 부모 노드, 자식 노드의 크기 관계에 따라 우측 회전이나 좌측 회전을 한다. 트리를 재정렬하면 항상 중간 크기의 요소가 가장 상단에 있는 루트가 된다. 1. 불균형이 좌측 서브트리에서 나타나는 경우 - 크기 관계는 (조부모 노드) > (부모 노드) > (자식 노드)이다. 우측 ..

※ 트리:제거 - 자식 노드 개수에 따라 트리의 특정 요소를 제거하는 방법은 다음과 같다. 1. 잎 노드를 제거할 경우 그 노드의 부모 노드 포인터를 null로 설정한다 2. 자식 노드가 하나인 노드를 제거할 경우 그 노드의 부모 노드의 포인터를 자식 노드로 향하게 하면 된다. 주의해야 할 점은 부모 노드에서 사용했던 포인터와 같은 포인터(left, right, 중 하나)를 사용해야 한다. 3. 자식 노드가 2개인 노드를 제거할 경우 중위 후속자와 중위 선임자 중 하나와 자리를 바꾼 뒤 해당 잎 노드를 제거한다. 중위 후속자(in order successor): 제거하고자 하는 노드에서 시작해 좌측으로 한번 내려갔다가 계속 오른쪽으로 내려간 곳의 잎 노드이다. 중위 후속자는 제거하고자 하는 노드보다 작은..

※ 트리: Contains - 특정 요소가 트리에 포함되어 있는지 확인하는 함수를 구현하고자 한다면 트리에 새로운 데이터를 추가하는 과정과 유사하게 동작한다. 우선 루트에서 시작하여 트리의 규칙을 따라 내려간 뒤 해당 요소를 찾으면 True 반환하고 null 노드에 도달하면 False를 반환한다 이 과정을 코드로 구현하면 다음과 같은데 재귀 함수를 이용해 트리의 규칙을 따라 내려가는 기능을 구현하였다 public boolean contains (E obj, Node node){ // 트리의 끝에 도달했는데 null if(node == null) return false; // node의 data와 일치 if(((Comparable)obj).compareTo(node.data)==0) return true;..

※ 트리: 재귀 함수 - 트리에 새로운 데이터를 추가 하는 과정은 우선 루트에서 시작하고 트리의 규칙을 따라 내려간 뒤 null 부분을 찾은 경우 해당 구역에 새로운 노드를 추가한다. 위 과정을 코드로 작성하면 아래 예시와 같은데 재귀 함수를 이용해 트리의 규칙에 따라 내려가는 기능을 구현한 것 이다. public void add (E obj, Node node){ if (((Comparable) obj).compareTo(node.data) > ){ // go to the right if(node.right == null){//3 node.right = new Node(obj); return; } return add(obj, node.right); // 2 } // go to the left if(no..