JavaScript 데이터 구조의 이 진 트 리 삭제 알고리즘 예제

이 글 은 자바 스 크 립 트 데이터 구조의 이 진 트 리 삭제 알고리즘 을 실례 적 으로 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
이 진 트 리 에서 노드 를 삭제 하 는 작업 의 복잡 도 는 어느 노드 를 삭제 하 느 냐 에 달 려 있다.만약 에 서브 노드 가 없 는 노드 를 삭제 하면 매우 간단 하 다.만약 에 노드 가 하나의 서브 노드 만 있 으 면 왼쪽 노드 든 오른쪽 노드 든 약간 복잡 해 지고 노드 가 두 개의 서브 노드 를 포함 하면 가장 복잡 하 다.
삭제 할 노드 가 잎 노드 라면 부모 노드 에서 링크 를 null 로 가리 키 기만 하면 됩 니 다.
만약 삭 제 를 기다 리 는 노드 가 하나의 하위 노드 만 포함 된다 면,원래 그 노드 를 가리 키 는 노드 는 그 노드 를 가리 키 게 해 야 한다.
삭제 할 노드 에 두 개의 키 노드 가 포함 되 어 있다 면 우 리 는 두 가지 방식 을 사용 할 수 있 습 니 다.하 나 는 삭제 할 노드 왼쪽 하위 트 리 의 최대 치 를 찾 는 것 입 니 다.하 나 는 삭제 할 노드 오른쪽 노드 의 최소 치 를 찾 는 것 입 니 다.우 리 는 후 자 를 채택 하여 최소 값 을 찾 은 후에 임시 노드 의 값 을 삭제 할 노드 로 복사 한 다음 에 임시 노드 를 삭제 합 니 다.
다음 과 같이 동작 하 는 코드 를 삭제 합 니 다:

function getSmallest(node){//      
    while(node.left!=null){
      node=node.left;
    }
    return node;
}
function remove(data){
    root=removeNode(this.root,data);//      
}
function removeNode(node,data){
    if(node==null){
      return null;
    }
    if(data==node.data){
      //       
      if(node.right==null&&node.left==null){
        return null;//        
      }
      //        
      if(node.left==null){
        return node.right;//        
      }
      //        
      if(node.right==null){
        return node.left;
      }
      //       
      if(node.right!=null&&node.left!=null){
        var tempNode=getSmallest(node.right);//        
        node.data=tempNode.data;
        node.right=removeNode(node.right,tempNode.data);//    
        return node;
      }
    }else if(data<node.data){
      node.left=removeNode(node.left,data);
      return node;
    }else{
      node.right=removeNode(node.right,data);
      return node;
    }
}

자 바스 크 립 트 와 관련 된 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.,,,JavaScript 데이터 구조 와 알고리즘 기술 총화,JavaScript 수학 연산 용법 총화,JavaScript 정렬 알고리즘 요약,JavaScript 스 트 리밍 알고리즘 및 기술 총화과JavaScript 찾기 알고리즘 기술 총화.
본 고 에서 말 한 것 이 여러분 의 자 바스 크 립 트 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.