삭제 메소드 구현

AVL 트리에서 요소를 삭제하는 것은 트리 균형을 다시 조정해야 한다는 점을 제외하면 BST에서 요소를 삭제하는 것과 동일합니다. BST에서 요소 삭제 섹션에서 설명한 대로 이진 트리에서 요소를 삭제하기 위해 알고리즘은 먼저 요소가 포함된 노드를 찾습니다. current는 이진 트리의 요소를 포함하는 노드를 가리키고 parent는 current 노드의 부모를 가리킵니다. 현재 노드는 부모 노드
의 왼쪽 자식이거나 오른쪽 자식일 수 있습니다. 요소를 삭제할 때 두 가지 경우가 발생합니다.

사례 1: 아래 그림(a)과 같이 현재 노드에는 왼쪽 자식이 없습니다. 현재 노드를 삭제하려면 아래 그림(b)과 같이 현재 노드의 올바른 하위 노드와 상위 노드를 연결하기만 하면 됩니다. 부모 노드에서 루트까지의 경로를 따라 노드의 높이가 감소했을 수 있습니다. 트리의 균형을 유지하려면

를 호출하세요.

balancePath(parent.element);

사례 2: 현재 노드에 왼쪽 자식이 있습니다. rightMost는 현재 노드의 왼쪽 하위 트리에서 가장 큰 요소를 포함하는 노드를 가리키고 parentOfRightMost는 rightMost의 상위 노드를 가리킵니다. 노드는 아래 그림 (a)와 같습니다. rightMost 노드는 오른쪽 자식을 가질 수 없지만 왼쪽 자식을 가질 수 있습니다. current 노드의 요소 값을 rightMost 노드의 요소 값으로 바꾸고, parentOfRightMost 노드를 rightMost 노드를 삭제하고 아래 그림 (b)와 같이 rightMost 노드를 삭제합니다.

parentOfRightMost에서 루트까지의 경로를 따라 노드 높이가 감소했을 수 있습니다. 트리의 균형을 유지하려면 를 호출하세요.

balancePath(parentOfRightMost);

위 내용은 삭제 메소드 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!