AVLTree 클래스

AVLTree 클래스는 BST 클래스를 확장하여 필요한 경우 트리 균형을 재조정하기 위해 insert 및 delete 메서드를 재정의합니다. 아래 코드는 AVLTree 클래스의 전체 소스 코드를 제공합니다.

AVLTree 클래스는 BST를 확장합니다. BST 클래스와 마찬가지로 AVLTree 클래스에는 빈 AVLTree(5행)을 생성하는 인수 없는 생성자와 요소 배열(8~10행)에서 초기 AVLTree를 생성하는 생성자가 있습니다. .

BST 클래스에 정의된 createNewNode() 메소드는 TreeNode를 생성합니다. 이 메서드는 AVLTreeNode(13~15행)을 반환하도록 재정의되었습니다.

AVLTree의 insert 메서드는 18~27행에서 재정의됩니다. 이 메서드는 먼저 BST에서 insert 메서드를 호출한 다음 balancePath(e)(라인 23)을 호출하여 트리의 균형이 맞는지 확인합니다.

balancePath 메서드는 먼저 e 요소가 포함된 노드에서 루트까지의 경로에 있는 노드를 가져옵니다(45행). 경로의 각 노드에 대해 높이를 업데이트하고(48행), 균형 요소를 확인하고(51행), 필요한 경우 적절한 회전을 수행합니다(51-67행).

회전을 수행하는 네 가지 방법이 82~178행에 정의되어 있습니다. 각 메서드는 두 개의 TreeNode 인수(A 및 parentOfA)를 사용하여 호출되어 노드 A에서 적절한 회전을 수행합니다. 각 회전이 수행되는 방식은 게시물의 그림에 설명되어 있습니다. 회전 후 노드 A, B 및 C의 높이가 업데이트됩니다(라인 98, 125, 148, 175).

AVLTree의 delete 메서드는 183~248행에서 재정의됩니다. 두 가지 경우(218, 243행)에서 삭제 후 노드의 균형을 다시 맞춰야 한다는 점을 제외하면 방법은 BST 클래스에서 구현된 것과 동일합니다.

위 내용은 AVLTree 클래스의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!