public class BinarySearchTree> extends BinaryTree implements ITree{ protected enum Position { LEFT, RIGHT }; public BinarySearchTree(){ } public Node getNode(E data){ Node node = root; while(node != null){ if(data.compareTo(node.element) == 0){ return node; }else if(data.compareTo(node.element) < 0){ node = node.left; }else{ node = node.right; } } return null; } protected Node getLeafLeftNode(Node node){ Node tNode = node; if(tNode == null) return tNode; while(tNode.left != null){ tNode = tNode.left; } return tNode; } @SuppressWarnings("unchecked") @Override public boolean add(E data){ Node newNode = null; if(this.creator == null) newNode = new Node(data); else newNode = this.creator.createNewNode(data, null); if(root == null){ root = newNode; root.parent = null; }else{ Node parent; Node t = root; int cmp; do{ parent = t; cmp = data.compareTo(parent.element); if(cmp < 0){ t = t.left; }else if(cmp > 0){ t = t.right; }else{ // 얼레는 그냥 덮어씌우는게 일반적인듯..? System.out.println("데이터 중복안됨"); return false; } }while( t != null); if(cmp < 0){ parent.left = newNode; newNode.parent = parent; }else{ parent.right = newNode; newNode.parent = parent; } } return true; } @SuppressWarnings("unchecked") protected Node addAndGetNode(E data){ Node newNode = null; if(this.creator == null) newNode = new Node(data); else newNode = this.creator.createNewNode(data, null); if(root == null){ root = newNode; root.parent = null; } insertNode(root, newNode); return newNode; } // recursive add private Node insertNode(Node currentParent, Node newNode) { if (currentParent == null) return newNode; else if (newNode.element.compareTo(currentParent.element) > 0){ currentParent.right = insertNode(currentParent.right, newNode); currentParent.right.parent = currentParent; } else if (newNode.element.compareTo(currentParent.element) < 0 ){ currentParent.left = insertNode(currentParent.left, newNode); currentParent.left.parent = currentParent; } return currentParent; } @Override public E remove(E data){ Node removeNode = getNode(data); Node replaceNode = getReplacementNode(removeNode); replaceNodeWithNode(removeNode, replaceNode); return data; } public Node removeAndGetNode(E data){ Node removeNode = getNode(data); if(removeNode != null){ Node replaceNode = getReplacementNode(removeNode); replaceNodeWithNode(removeNode, replaceNode); } return removeNode; } protected Node getReplacementNode(Node nodeToRemoved) { Node replaceNode = null; if(nodeToRemoved.left != null && nodeToRemoved.right == null){ replaceNode = nodeToRemoved.left; }else if(nodeToRemoved.right != null && nodeToRemoved.left == null){ replaceNode = nodeToRemoved.right; }else if(nodeToRemoved.left != null && nodeToRemoved.right != null){ // 오른쪽 노드에서 가장 왼쪽에 있는 노드를 찾는다. // 왼쪽 노드에서 가장 오른쪽에 있는 노드를 찾아도 된다. replaceNode = getLeafLeftNode(nodeToRemoved.right); if(replaceNode == null){ // 삭제할 노드에 오른쪽 노드가 왼쪽 노드가 없다면 // 그냥 오른쪽 노드로 대신함 replaceNode = nodeToRemoved.right; } } return replaceNode; } protected void replaceNodeWithNode(Node nodeToRemoved, Node replacementNode) { // leaf 노드를 삭제한다면 replacementNode 가 null 일수도 있다. if(replacementNode != null){ // 대체 할 노드의 오른쪽 왼쪽을 바꾸기 전에 미리 저장해 놓는다. 처음에 대체할 노드의 오른쪽 왼쪽부터 바꾼다. // 1.왼쪽에 가장 오른쪽을 선택했을경우 데체할 노드의 왼쪽 자식은 있을수도 있다. Node replacementNodeLeft = replacementNode.left; // 2.오른쪽에 가징왼쪽을 선택했을경우 대체할 노드의 오른쪽 자식은 있을수도 있다. Node replacementNodeRight = replacementNode.right; // 대체할 노드 <-> 삭제할 노드의 양쪽 자식 // ** 삭제할 노드와 대체할노드가 바로 붙어 있다면 삭제할 노드의 부모를 대체할노드로 바꿔주기만하면됨** // 삭제할 노드에 양쪽 자식을 대체할 노드에 넣어준다. Node nodeToRemoveLeft = nodeToRemoved.left; // 삭제할 노드의 왼쪽이 있다면, **근데 삭제할노드의 왼쪽이 대체할노드가 아니라면** if(nodeToRemoveLeft != null && !nodeToRemoveLeft.equals(replacementNode)){ replacementNode.left = nodeToRemoveLeft; nodeToRemoveLeft.parent = replacementNode; } Node nodeToRemoveRight = nodeToRemoved.right; // 삭제할 노드의 오른쪽이 있다면, **근데 삭제할 노드의 오른쪽이 대체할 노드가 아니라면** if(nodeToRemoveRight != null && !nodeToRemoveRight.equals(replacementNode)){ replacementNode.right = nodeToRemoveRight; nodeToRemoveRight.parent = replacementNode; } // 대체할 노드의 부모 <-> 대체할 노드의 자식 (대체할 노드가 빠지므로) // 삭제할 노드의 오른쪽 노드의 맨왼쪽 노드(대체할노드) 의 오른쪽 자식은 있을수도 있다. Node replacementParent = replacementNode.parent; // 대체할 노드의 부모가 있고, **대체할 노드의 부모가 삭제할것은 아니라면** if(replacementParent != null && !replacementParent.equals(nodeToRemoved)){ // 대체할 노드가 부모의 왼쪽이라면(1.오른쪽에서 가장 왼쪽을 선택했을경우) if(replacementParent.left != null && replacementParent.left.equals(replacementNode)){ // 대체할 노드의 오른쪽을 대체할 노드의 부모의 왼쪽으로 연결해준다. replacementParent.left = replacementNodeRight; if(replacementNodeRight != null){ // 만약 대체노드의 오른쪽이 자식이 있다면 대체할 노드의 오른쪽의 부모를 대체할 노드의 부모로 replacementNodeRight.parent = replacementParent; } }else if(replacementParent.right != null && replacementParent.right.equals(replacementNode)){ // 1.삭제할 노드의 오른쪽의 가징 왼쪽 선택했으므로 대체할 노드의 부모의 오른쪽에 있을일이 없다. replacementParent.right = replacementNodeLeft; if(replacementNodeLeft != null){ replacementNodeLeft.parent = replacementParent; } } } } // 삭제할 노드의 부모 <-> 대체 노드 Node parent = nodeToRemoved.parent; if(parent == null){ // 삭제할 노드가 루트 노드 root = replacementNode; if(root != null) root.parent = null; }else if(parent.left != null && parent.left.equals(nodeToRemoved)){ // 삭제할노드가 부모의 왼쪽 이라면 parent.left = replacementNode; if(replacementNode != null) replacementNode.parent = parent; }else if(parent.right != null && parent.right.equals(nodeToRemoved)){ // 삭제할노드가 부모의 오른쪽 이라면 parent.right = replacementNode; if(replacementNode != null) replacementNode.parent = parent; } } public E remove2(E data){ Node removeNode = getNode(data); if(removeNode.left == null && removeNode.right == null){ // leaf node Node parent = removeNode.parent; if(parent.left == removeNode){ parent.left = null; }else if(parent.right == removeNode){ parent.right = null; } removeNode = null; } else if(removeNode.left != null && removeNode.right == null){ // 자식이 한개밖에없다. Node parent = removeNode.parent; Node child = removeNode.left; if(parent.left == removeNode){ parent.left = child; }else if(parent.right == removeNode){ parent.right = child; } removeNode = null; } else if(removeNode.right != null && removeNode.left == null){ // 자식이 한개밖에없다. Node parent = removeNode.parent; Node child = removeNode.right; if(parent.left == removeNode){ parent.left = child; }else if(parent.right == removeNode){ parent.right = child; } removeNode = null; } else if(removeNode.right != null && removeNode.left != null){ Node parent = removeNode.parent; Node replaceNode = getLeafLeftNode(removeNode.right); //System.out.println(replaceNode.element); if(parent.left == removeNode){ parent.left = replaceNode; replaceNode.left = removeNode.left; if(replaceNode.right == null){ if(replaceNode != removeNode.right) replaceNode.right = removeNode.right; } replaceNode.parent.left = null; }else if(parent.right == removeNode){ parent.right = replaceNode; replaceNode.left = removeNode.left; // 대신할 노드에 왼쪽은 항상 없지만 오른쪽은 있을수도 있다. if(replaceNode.right == null){ // 삭제할 노드에 오른쪽 노드가 대신할노드랑 같으면 서로 참조하게됨 if(replaceNode != removeNode.right) replaceNode.right = removeNode.right; } replaceNode.parent.left = null; } removeNode = null; } return data; } public void rotateLeft(Node node){ System.out.println("ROTATE LEFT AT " + node); Node parent = node.parent; Position parentPosition = null; if(parent != null){ if(node.equals(parent.left)){ parentPosition = Position.LEFT; }else{ parentPosition = Position.RIGHT; } } Node greater = node.right; Node lesser = greater.left; node.right = null; greater.left = node; node.parent = greater; node.right = lesser; if(lesser != null) lesser.parent = node; if(parentPosition != null){ if(parentPosition == Position.LEFT){ parent.left = greater; }else{ parent.right = greater; } greater.parent = parent; }else{ root = greater; greater.parent = null; } } public void rotateRight(Node node){ System.out.println("ROTATE RIGHT AT " + node); Node parent = node.parent; Position parentPosition = null; if(parent != null){ if(node.equals(parent.left)){ parentPosition = Position.LEFT; }else{ parentPosition = Position.RIGHT; } } Node lesser = node.left; Node greater = lesser.right; node.left = null; lesser.right = node; node.parent = lesser; node.left = greater; if(greater != null) greater.parent = node; if(parentPosition != null){ if(parentPosition == Position.LEFT){ parent.left = lesser; }else{ parent.right = lesser; } lesser.parent = parent; }else{ root = lesser; lesser.parent = null; } } }