public class AVLTree> extends BinarySearchTree implements ITree, BinaryTree.INodeCreator{ private enum Balance { LEFT_LEFT, LEFT_RIGHT, RIGHT_LEFT, RIGHT_RIGHT }; public int height = 1; public AVLTree(){ this.creator = this; } @Override public boolean add(E data){ Node t = super.addAndGetNode(data); AVLNode addedNode = (AVLNode)t; while(addedNode != null){ addedNode.updateHeight(); balnaceAfterInsert(addedNode); addedNode = (AVLNode) addedNode.parent; } return true; } @Override public E remove(E data){ Node nodeToRemoved = this.getNode(data); if (nodeToRemoved != null) { Node replacementNode = this.getReplacementNode(nodeToRemoved); // 삭제후에 제조정 되어할 노드 AVLNode nodeToRefactor = null; if (replacementNode != null) // 부모부터 nodeToRefactor = (AVLNode) replacementNode.parent; if (nodeToRefactor == null) // 대체할 노드가 널인경우는 leaf 노드 이므로 삭제할 노드의 부모부터 제조정 nodeToRefactor = (AVLNode) nodeToRemoved.parent; // 재조정 노드가 삭제할 노드랑 같다면 부모부터가 아닌 대체할 노드부터 if (nodeToRefactor != null && nodeToRefactor.equals(nodeToRemoved)) nodeToRefactor = (AVLNode) replacementNode; replaceNodeWithNode(nodeToRemoved, replacementNode); if (nodeToRefactor != null) { while (nodeToRefactor != null) { nodeToRefactor.updateHeight(); balanceAfterDelete(nodeToRefactor); nodeToRefactor = (AVLNode) nodeToRefactor.parent; } } } return data; } private void balnaceAfterInsert(AVLNode node){ int balanceFactor = node.getBalanceFactor(); if(balanceFactor < -1 || balanceFactor > 1){ // 크기 차이가 2보다 커짐 AVLNode parent = null; AVLNode child = null; Balance balnace = null; if(balanceFactor < 0){ // 왼쪽에 추가됨 parent = (AVLNode)node.left; balanceFactor = parent.getBalanceFactor(); if(balanceFactor < 0){ // 추가된 노드가 부모의 왼쪽에 child = (AVLNode)parent.left; balnace = Balance.LEFT_LEFT; }else{ // 추가된 노드에 부모의 오른쪽에 child = (AVLNode)parent.right; balnace = Balance.LEFT_RIGHT; } }else{ // 오른쪽에 추가됨 parent = (AVLNode)node.right; balanceFactor = parent.getBalanceFactor(); if(balanceFactor < 0 ){ // 추가된 노드가 부모의 왼쪽에 child = (AVLNode)parent.left; balnace = Balance.RIGHT_LEFT; }else{ child = (AVLNode)parent.right; balnace = Balance.RIGHT_RIGHT; } } print(); if(balnace == Balance.LEFT_LEFT){ System.out.println("LL"); rotateRight(node); }else if(balnace == Balance.LEFT_RIGHT){ System.out.println("LR"); rotateLeft(parent); print(); rotateRight(node); print(); }else if(balnace == Balance.RIGHT_LEFT){ System.out.println("RL"); rotateRight(parent); rotateLeft(node); }else if(balnace == Balance.RIGHT_RIGHT){ System.out.println("RR"); rotateLeft(node); } print(); node.updateHeight(); child.updateHeight(); parent.updateHeight(); } } private void balanceAfterDelete(AVLNode node) { int balanceFactor = node.getBalanceFactor(); if (balanceFactor == -2 || balanceFactor == 2) { // TODO if (balanceFactor == -2) { // 왼쪽이 더 높이가 높다 // 1. (LL) 왼쪽 자식의 왼쪽이 높이가 더 높다면 => 오른쪽 회전(노드) => 노드, 노드의 부모 높이 재조정 // 2. (LR) 왼쪽 자식의 오른쪽이 높이가 더 높다면 => 왼쪽 회전(왼쪽자식),오른쪽회전(노드) => 노드의 부모, 노드의 양쪽자식 높이 재조정 } else if(balanceFactor == 2){ // 오른쪽이 더 높이가 높다. // 3. (RR) 오른쪽 자식의 오른쪽이 높이가 더 높다면 => 왼쪽 회전(노드) => 노드, 노드의 부모 높이 재조정 // 4. (RLL) 오른쪽 자식의 왼쪽이 높이가 더 높다면 => 오른쪽 회전(오른쪽),왼쪽회전(노드) => 노드의 부모, 노드의 양쪽자식 높이 재조정 } } } @Override public Node createNewNode(E element, Node parent) { return (new AVLNode(element, parent)); } protected static class AVLNode> extends Node{ public int height = 1; protected AVLNode(E element,Node parent) { super(element, parent); } protected void updateHeight() { int leftHeight = 0; int rightHeight = 0; if (left != null) { AVLNode leftNode = (AVLNode) left; leftHeight = leftNode.height; } if (right != null) { AVLNode rightNode = (AVLNode) right; rightHeight = rightNode.height; } if (leftHeight > rightHeight) { this.height = leftHeight + 1; } else { this.height = rightHeight + 1; } } protected int getBalanceFactor(){ int leftHeight = 0; int rightHeight = 0; if(this.left != null){ AVLNode avlNode = (AVLNode)left; leftHeight = avlNode.height; } if(this.right != null){ AVLNode avlNode = (AVLNode)right; rightHeight = avlNode.height; } return rightHeight-leftHeight; } @Override public String toString(){ return "element : " + element +" : height : "+ height+ " balanceFactor : " + getBalanceFactor(); } } }