JavaScript 데이터 구조의 이 진 트 리 삭제 알고리즘 예제
2651 단어 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;
}
}
본 고 에서 말 한 것 이 여러분 의 자 바스 크 립 트 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
기초 정리 - 1문자 (String) 숫자 (Number) 불린 (Boolean) null undefined 심볼 (Symbol) 큰정수 (BigInt) 따옴표로 묶어 있어야 함 Not-A-Number - 숫자 데이터 / 숫자로 표...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
