• Home
  • About
    • Yerim Oh photo

      Yerim Oh

      Happy and worthwhile day by day :)

    • Learn More
    • Email
    • LinkedIn
    • Instagram
    • Github
    • Youtube
  • Posts
    • All Posts
    • All Tags
  • Projects

[024] Concept(비선형자료구조_TREE 노드의 삭제)

12 Feb 2020

Reading time ~5 minutes

Table of Contents
  • 목차
  • 트리 노드 삭제
    • leaf 노드 삭제
    • single child를 갖은 노드 삭제
    • two child를 갖은 노드 삭제
      • [soultion 1]
      • [soultion 2]
  • 구현
    • python 구현
    • java 구현
    • 기본 base class for python
      • node class
      • tree method class
      • 구현하는 main 함수
    • 기본 base class for java
      • node class
      • tree method class
      • 구현하는 main 함수

목차

  • 트리 노드 삭제
    • leaf 노드 삭제
    • single child를 갖은 노드 삭제
    • two child를 갖은 노드 삭제
      • [solution 1]
      • [solution 2]
  • 구현
    • python 구현
    • java 구현
    • 기본 base class for python
      • node class
      • tree method class
      • 구현하는 main 함수
    • 기본 base class for java
      • node class
      • tree method class
      • 구현하는 main 함수

트리 노드 삭제

leaf 노드 삭제

leaf node?
image
[처리 방법]
1) 지우고자 하는 노드를 찾는다
2) 해당 노드를 null로 바꾼다

  • (주의) 삭제되는 노드가 root node인 경우, 예외처리
    123

single child를 갖은 노드 삭제

child node?
image [처리 방법]
1) 지우고자하는 노드를 찾는다
2) 해당노드를 지운다
3) 지운자리에 자식을 대신 배치한다

  • (주의) 삭제되는 노드가 root node인 경우, 대신 들어오는 자식이 root가 된다
    12121212123

two child를 갖은 노드 삭제

image

  • [soultion 1] 오른쪽 자식노드 중 가장 작은 값을 대신 배치(더 자주 사용)
  • [soultion 2] 왼쪽 자식노드 중 가장 큰 값을 대신 배치

[soultion 1]

image [처리 방법]
1) 지워야하는 노드를 찾는다
2) 지워야하는 노드의 오른쪽 자식노드 중 가장 작은 노드(왼쪽노드)를 찾는다
3) 찾은 노드를 지워야할 노드에 대체한다
4) 찾은 노드를 지워준다 1234

[soultion 2]

image 1) 지워야하는 노드를 찾는다
2) 지워야하는 노드의 왼쪽 자식노드 중 가장 큰 노드(오른쪽노드)를 찾는다
3) 찾은 노드를 지워야할 노드에 대체한다
4) 찾은 노드를 지워준다


구현

python 구현

  • 먼저 트리노드를 구현해준다
# 자식이 몇명인지 세어줌
def countChildren(self):
    count = 0
    if self.left:
        count += 1
    if self.right:
        count += 1
    return count
 
 
 def delect(self, key):
  node, parent = self.lookup(key)
  
  if node:
      nChildren = node.countChildren()
      
      # leaf 노드 삭제(자식이 이무것도 없는 경우)
      if nChildren == 0:
            # 지울 node 가 그 parent의 왼쪽 자식인지 오른쪽 자식인지 판단하여
            # leaf node 였던 자식의 parent= null으로 바꿔 자식을 끊어낸다
            if parent:
                if node == parent.right:
                    parent.right = None
                if node == parent.left:
                    parent.left = None
            # 지워야 할 노드가 root 인 경우(예외처리)
            else:
                self.root = None
      
      #######################################################################
      # single child를 갖은 노드 삭제
      elif nChildren == 1:
           # 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
           # 그 자식을 displace가 가리키도록 함
           if node.left:
                displace = node.left
           else:
                displace = node.right
            
           # node의 parent를 통해 node가 parent의 왼쪽 자식인지 오른쪽 자식인지 판단하여
           # node의 child(displace)을 node 의 자리에 넣음
           # 즉 parent-node-child
           # -> parent-child
           if parent:
                if node == parent.right:
                    parent.right = displace
                else:
                    parent.left = displace
            # node 는 root 인 경우 예외처리
            else:
                self.root = displace
        
        
        ####################################################
        # 이해를 돕기 위해 위의 예를 그대로 사용했습니다 그림과 대조하면서 읽어보세요
        # two child를 갖은 노드 삭제 [soultion 1]
        else:
            # parent = 41
            parent = node
            
            # 노드의 오른쪽에서 가장 작은 노드를 찾아야함
            # successor은 노드의 오른쪽 (65)
            successor = node.right
            
            # 이제 successor중 가장 작은 값(왼쪽노드or 왼쪽노드가 없으면 자기자신)을 찾아야함
            # while문이 종료되었을때, 
            # successor 는 바로 다음 키를 가진 노드를
            # 그리고 parent 는 그 노드의 부모 노드를 가리키게함
            # 계속 왼쪽으로 감
            while successor.left: # successor.left= 50
                parent = successor # parent = 65
                successor = successor.left  # successor= 50
            
            # 삭제하려는 노드인 node 에 successor 의 key 와 data 를 대입
            node.key = successor.key
            node.data = successor.data
            
            # 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
            # 그에 따라 parent.left 또는 parent.right 를
            # successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 함  
                if successor.key is parent.left.key:
                    parent.left = successor.right
                else:
                    parent.right = successor.right
                    
            return True
                

        else:
            return False

java 구현

  • 먼저 트리노드를 구현해준다
public void delete(int data){
	if(root==null){
		 		 return;
	}
		        
	TNode parent = root;
	TNode current = root;
		        
	// parent의 좌,우를 나타내는 변수
	boolean isLeft = false;
		        
	// 삭제 하려는 노드 찾기
	while(current.data !=data){
		   parent = current;
		   if(current == null){
		             return;
		   }
		   else if(current.data <data){
		        isLeft = false;
		        current = current.right;
		   }
		   else if(current.data >data){
		         isLeft = true;
		         current = current.left;
		    }
         }
	
	//////////////////////////////////////////////////////////////
	//leaf 노드 삭제
	if(current.left==null && current.right==null){
		// 삭제하려는 노드가 root인 경우
		if(current == root) root = null;
		            
		if(isLeft){
		   	parent.left=null;
		}
    		else{
		  	parent.right=null;
		}
	}	
  
  
	//////////////////////////////////////////////////////////////       
	// single child를 갖은 노드 삭제
	else if(current.left==null){    // 오른쪽 서브트리가 존재
		 if(current==root){    // 삭제하려는 노드가 root인 경우(예외처리)
		       root = current.right;
		 }
          
	  	if(isLeft){
		          parent.left=current.right;
		}
		else{
		          parent.right=current.right;
		}
    	}
		
   	else if(current.right==null){    // 왼쪽 서브트리가 존재
		      if(current==root){    // 삭제하려는 노드가 root인 경우(예외처리)
		              root = current.left;
		      }
		      if(isLeft){
		               parent.left=current.left;
		      }
        
		      else{
		  		parent.right=current.left;
		      }
	}
		        
    	//////////////////////////////////////////////////////////////////////
    	//two child를 갖은 노드 삭제 [soultion 1] 구현
    	else if(current.left!=null && current.right!=null){
		      if(current==root){    // 삭제하려는 노드가 root인 경우(예외처리)
		          root = current.left;
		      }
		      if(isLeft){
		           parent.left=current.left;
		      }
		      else{
		            parent.right=current.right;
		      }
	}


기본 base class for python

node class

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

tree method class

class tree:
    def __init__(self, root):
        self.root = root

    def insert(self, value):
        self.current_node = self.root
        while True:
            if value < self.current_node.value:
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break
      ############
      # 이곳에 delect 함수 

구현하는 main 함수

tree.insert(41);
tree.insert(20);
tree.insert(11);
tree.insert(29);
tree.insert(32);
tree.insert(65);
tree.insert(50);
tree.insert(91);
tree.insert(72);
tree.insert(99);
// 지우는 법
tree.delete(72);

기본 base class for java

node class

public class TNode {
	int data;
	TNode left;
	TNode right;	
}

tree method class

public class Tree{ 
  public void insert(int data)
  {
	  TNode newNode = new TNode();
	  newNode.data = data;
    
    // 노드 삽입
    private void insertNode(TNode current, TNode newNode)
		{
			if(current.data >= newNode.data)
			{
				if(current.left == null)
					current.left = newNode;
				else
					// 재귀함수
					insertNode(current.left, newNode);
			}
			else 
			{
				if(current.right == null)
					current.right = newNode;
				else
					insertNode(current.right, newNode);
			}
		}
		
    // 아직 트리에 데이터가 하나도 없다
    if(root == null)
	  {
	  	root = newNode;
		  return;
	  }
		
	  insertNode(root, newNode);
  }
  
  //// 여기에 삭제 추가
}

구현하는 main 함수

public class TreeMain {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Tree tree = new Tree();
		// 트리구성
    tree.insert(41);
		tree.insert(20);
		tree.insert(11);
		tree.insert(29);
		tree.insert(32);
		tree.insert(65);
		tree.insert(50);
		tree.insert(91);
		tree.insert(72);
		tree.insert(99);
		// 지우는 법
    tree.delete(72);

	}
	

}



Coding test Share Tweet +1