4. Tree

• Tree
  • 그래프의 일종으로 하나의 노드는 여러개의 노드를 가리킬수 있지만 여러개의 노드가 하나의 노드를 가리킬수 없는 구조이다.
  • 노드와 노드를 이어주는 간선으로 구성되어있다.
  • 트리는 순회가 불가능 하다
  • 용어
    • Root Node : 최상의 부모 노드로서 하나만 존재한다
    • Parent Node : 부모노드, 0개 이상의 자식을 가질 수 있다.
    • child Node : 하나의 부모를 가진다.
    • Leaf Node : 자식이 없는 노드를 말한다.
    • edge : 간선, 노드와 노드를 연결하는 선을 말한다.
    • sibling : 간은 부모를 가지는 형제 노드
    • size : 자신을 포함한 모든 자식(자손)노드의 수
    • depth : 노드의 깊이(부모노드부터 하위 노드까지의 깊이)
    • level : 부모를 0으로 밑으로 내려갈수록 1씩 증가한다.
    • degree : 노드가 가지고있는 edge의 수
  • 
• 종류
  
  • binary : 부모노드가 자식노드를 최대 2개까지 가질 수 있다.
  • full binary : 모든 노드가 2개의 자식을 갖거나 자식이 없는 구조를 말한다.
  • perfect binary
    • 모든 내부 노드가 2개의 자식을 가지고 있어야 함
    • 모든 말단 노드(마지막 레벨에 하나의 노드만 있어서는 안됨)는 같은 높이에 있어야 함
  • ternary : 각 노드가 최대 3개의 자식을 갖는 트리
  • binary search
    • 부모 노드의 왼쪽 자식은 부모의 값보다 작은 값을 지닌 노드로 이루어져 있다.
    • 부모 노드의 오른쪽 자식은 부모의 값보다 큰 값을 지닌 노드로 이루어져 있다.
• Binary Search Tree 구현 코드
  • tree class생성

  • public class BinarySearchTree {
    	Node head = null;
    }​

     
  • 트리구조에서 데이터가 저장될 노드 클래스를 생성한다.

  • public class Node {
    	Node left;
        Node right;
        int data;
    
    	public Node(int data) {
        	this.data = data;
        }
    }

  • 삽입

  • public void add(int data) {
    	if(this.head == null) {
        	this.head = new Node(data);
        } else {
        	Node parentNode = this.head;
            
            while(true) {
            	if(data < parentNode.data) {
                	if(parentNode.left != null) {
                    	parentNode = parentNode.left;
                    } else {
                    	parentNode.left = new Node(data);
                        break;
                    }
                } else {
                	if(parentNode.right != null) {
                    	parentNode = parentNode.right;
                    } else {
                    	parentNode.right = new Node(data);
                        break;
                    }
                }
            }
        }
    }

  • 검색

  • public Node findNode(int data) {
    	if(this.head == null) {
        	return null;
        } else {
        	Node parentNode = this.haed;
            while(parentNode != null) {
            	if(parentNode.data == data) {
                	return parentNode;
                } else if(data < parentNode.data) {
                	parentNode = parentNode.left;
                } else {
                	parentNode = parentNode.right;
                }
            }
            return null;
        }
    }

  • 삭제

  • public Boolean remove(int data) {
    	Node currParentNode = this.head;
        Node currNode = this.head;
    
    	if (this.head == null) {
    		return false;
    	} else {
    		if (this.head.value == value && this.head.left == null && this.head.right == null) {
    			this.head = null;
    			return true;
    		}
    
    		while (currNode != null) {
    			if (currNode.value == value) {
    				searched = true;
    				break;
    			} else if (value < currNode.value) {
    				currParentNode = currNode;
    				currNode = currNode.left;
    			} else {
    				currParentNode = currNode;
    				currNode = currNode.right;
    			}
    		}
    
    		if (searched == false) {
    			return false;
    		}
    	}
    
    
    	if (currNode.left == null && currNode.right == null) {
    		if (value < currParentNode.value) {
    			currParentNode.left = null;
    			currNode = null;
    		} else {
    			currParentNode.right = null;
    			currNode = null;
    		}
    		return true;
    
    	} else if (currNode.left != null && currNode.right == null) {
    		if (value < currParentNode.value) {
    			currParentNode.left = currNode.left;
    			currNode = null;
    	} else {
    		currParentNode.right = currNode.left;
    		currNode = null;
    	}
    		return true;
    
    	} else if (currNode.left == null && currNode.right != null) {
    		if (value < currParentNode.value) {
    			currParentNode.left = currNode.right;
    			currNode = null;
    		} else {
    			currParentNode.right = currNode.right;
    			currNode = null;
    		}
    		return true;
    	} else {
    		if (value < currParentNode.value) {
    			Node changeNode = currNode.right;
    			Node changeParentNode = currNode.right;
    			while (currNode.left != null) {
    				changeParentNode = currNode;
    				changeNode = currNode.left;
    			}
    
    			if (changeNode.right != null) {
    				changeParentNode.left = changeNode.right;
    			} else {
    				changeParentNode.left = null;
    			}
    			changeNode.right = currNode.right;
    			changeNode.left = currNode.left;
    			currNode = null;
    		} else {
    			Node changeNode = currNode.right;
    			Node changeParentNode = currNode.right;
    			while (changeNode.left != null) {
    				changeParentNode = changeNode;
    				changeNode = changeNode.left;
    			}
    
    			if (changeNode.right != null) {
    				changeParentNode.left = changeNode.right;
    			} else {
    				changeParentNode.left = null;
    			}
    			currParentNode.right = changeNode;
    			changeNode.right = currNode.right;
    			changeNode.left = currNode.left;
    			currNode = null;
    		}
    		return true;
    	}
    }​