2015년 2월 16일 월요일

20141106 더블 링크드 리스트로 이진 검색 트리 구현

2014-11-10 리팩토링

이전에 망친거를 다시 복구함.

물론 고수의 눈에는 항상 망가져있음.

아...어렵다..

이런거 배우면서 대학생활 하신 분들은 정말 즐거웠을 듯?!
이라고 즐거운척 하면서 울어봅니다...

패키지는 빼고, 해보면 될껀데..

이제 스레드 돌려서 테스트 하는거 해봐야 하는데..
시작도 엄두가 안나는데
누가 힌트좀 줬으면 좋겠다...



package dataStructure3;

public class Node {
private Node parents;
private Integer data;
private Node leftChild;
private Node rightChild;

public Node() {
this.parents = null;
this.data = null;
this.leftChild = null;
this.rightChild = null;
}
public Node(Integer data) {
this();
this.data = data;
}
public Node getParents() {
return parents;
}
public void setParents(Node parents) {
this.parents = parents;
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public Node getLeftChild() {
return leftChild;
}
public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}
public Node getRightChild() {
return rightChild;
}
public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}

}
package dataStructure3;

public class DLLTree {
private Node root;

public DLLTree() {
this.root = null; 
}

public DLLTree(Node root) {
this();
this.root = root;
}

public Node getRoot() {
return root;
}

public void setRoot(Node root) {
this.root = root;
}
// 검색 - 데이터
public boolean searchData(int data){
return searchData(root, data);
}

private boolean searchData(Node node, int data) {
if(node == null){
return false;
}
if(data < node.getData()){
return searchData(node.getLeftChild(), data);
}
if(data > node.getData()){
return searchData(node.getRightChild(), data);
}
if(data == node.getData()){
return true;
}
return false;
}
// 삽입
public boolean insertData(int data){
if(searchData(data)){ // 같은 데이터는 삽입 불가
return false;
}
Node newNode = new Node(data);
return insertData(root, newNode, data);
}

private boolean insertData(Node node, Node newNode, int data) {
if(data < node.getData()){
if(node.getLeftChild() != null){
return insertData(node.getLeftChild(), newNode, data);
}else{
node.setLeftChild(newNode);
newNode.setParents(node);
return true;
}
}
if(data> node.getData()){
if(node.getRightChild() != null ){
return insertData(node.getRightChild(), newNode, data);
}else{
node.setRightChild(newNode);
newNode.setParents(node);
return true;
}
}
return false;
}
public boolean deleteData(int data){
if(data == root.getData()){
return false;
}
if(searchData(data)){
Node targetNode = searchNodeToDelete(data);
return deleteNode(targetNode);
}
return false;
}
// 검색 - 노드
private Node searchNodeToDelete(int data){
return searchNode(root, data);
}

private Node searchNode(Node node, int data) {
if(node == null){
return null;
}
if(data < node.getData()){
return searchNode(node.getLeftChild(), data);
}
if(data > node.getData()){
return searchNode(node.getRightChild(), data);
}
if(data == node.getData()){
return node;
}
return null;
}
private boolean deleteNode(Node node) {
// child = 0
if(node.getLeftChild() == null && node.getRightChild() == null){
if(node.getParents().getLeftChild() == node){
node.getParents().setLeftChild(null);
}else{
node.getParents().setRightChild(null);
}
node = null;
return true;
}
// child = 2
if(node.getLeftChild() != null && node.getRightChild() != null){
if(node.getParents().getLeftChild() == node){
node.getParents().setLeftChild(null);
}else{
node.getParents().setRightChild(null);
}
node.setParents(null);
insertData(root, node.getLeftChild(), node.getLeftChild().getData());
insertData(root, node.getRightChild(), node.getRightChild().getData());
return true;
}
// child = 1
if(node.getLeftChild() != null || node.getRightChild() != null){
if(node.getParents().getLeftChild() == node){
node.getParents().setLeftChild(null);
}else{
node.getParents().setRightChild(null);
}
if(node.getLeftChild() != null){
insertData(root, node.getLeftChild(), node.getLeftChild().getData());
}else{
insertData(root, node.getRightChild(), node.getRightChild().getData());
}
node = null;
return true;
}
return false;
}

}


public class DLLTree{
private Node root;

public DLLTree() {
this.root = null;
}

public DLLTree(Node root) {
this();
this.root = root;
}

public Node getRoot() {
return this.root;
}

public void setRoot(Node root) {
this.root = root;
}


// 검색 - 데이터
public boolean searchData(int data){
return searchData(this.root, data);
}

@SuppressWarnings("boxing")
private boolean searchData(Node node, int data) {
if(node == null){
return false;
}

if(data < node.getData()){
return searchData(node.getLeftChild(), data);
}
if(data > node.getData()){
return searchData(node.getRightChild(), data);
}
if(data == node.getData()){
return true;
}
return false;
}



// 삽입
@SuppressWarnings("boxing")
public boolean insertData(int data){
if(searchData(data)){ // 같은 데이터는 삽입 불가
return false;
}
Node newNode = new Node(data);
insertData(this.root, newNode, data);
return true;
}

@SuppressWarnings("boxing")
private void insertData(Node node, Node newNode, int data) {

if(data < node.getData()){
if(node.getLeftChild() != null){
insertData(node.getLeftChild(), newNode, data);
return ;
}
node.setLeftChild(newNode);
newNode.setParents(node);
return ;

}

if(node.getRightChild() != null ){
insertData(node.getRightChild(), newNode, data);
return ;
}
node.setRightChild(newNode);
newNode.setParents(node);
return ;


}

@SuppressWarnings("boxing")
public boolean deleteData(int data){
if(data == this.root.getData()){
System.out.println(data+" is rootData.");
return false;
}

if(searchData(data)){
Node targetNode = searchNodeToDelete(data);
return deleteNode(targetNode);
}
return false;
}

// 검색 - 노드
private Node searchNodeToDelete(int data){
return searchNode(this.root, data);
}

@SuppressWarnings("boxing")
private Node searchNode(Node node, int data) {
if(node == null){
return null;
}
if(data == node.getData()){
return node;
}

if(data < node.getData()){
return searchNode(node.getLeftChild(), data);
}
if(data > node.getData()){
return searchNode(node.getRightChild(), data);
}

return null;
}


@SuppressWarnings("boxing")
private boolean deleteNode(Node node) {
disconnectFromParentNode(node);
if(node.getLeftChild() != null){
insertData(this.root, node.getLeftChild(), node.getLeftChild().getData());
}
if(node.getRightChild() != null){
insertData(this.root, node.getRightChild(), node.getRightChild().getData());
}
deleteNodeself(node);
return true;
}

private static void disconnectFromParentNode(Node node){
if(node.getParents().getLeftChild() == node){
node.getParents().setLeftChild(null);
}else{
node.getParents().setRightChild(null);
}
node.setParents(null);
}

private static void deleteNodeself(Node node){
node.setParents(null);
node.setLeftChild(null);
node.setRightChild(null);
}
}


리펙토링.
작성자: 시간:
라벨:

댓글 없음:

댓글 쓰기

피드 구독하기: 댓글 (Atom)