AVL 트리는 이진 검색 트리이므로 AVLTree는 BST의 하위 클래스로 설계되었습니다. AVL 트리는 이진 트리이므로 아래 그림과 같이 AVLTree 클래스를 정의하여 BST 클래스를 확장할 수 있습니다. BST 및 TreeNode 클래스는 섹션
에 정의되었습니다.트리의 균형을 맞추려면 각 노드의 높이를 알아야 합니다. 편의를 위해 각 노드의 높이를 AVLTreeNode에 저장하고 AVLTreeNode를 BST.TreeNode의 하위 클래스로 정의합니다. TreeNode는 BST에서 정적 내부 클래스로 정의됩니다. AVLTreeNode는 AVLTree에서 정적 내부 클래스로 정의됩니다. TreeNode에는 AVLTreeNode에 상속된 데이터 필드 element, left 및 right가 포함되어 있습니다. 따라서 AVLTreeNode에는 아래 그림과 같이 4개의 데이터 필드가 포함됩니다.
BST 클래스에서 createNewNode() 메서드는 TreeNode 개체를 생성합니다. 이 메서드는 AVLTree 클래스에서 재정의되어 AVLTreeNode를 생성합니다. BST 클래스에 있는 createNewNode() 메서드의 반환 유형은 TreeNode이지만, AVLTree 클래스에 있는 createNewNode() 메서드의 반환 유형은 AVLTreeNode입니다. AVLTreeNode는 TreeNode.
의 하위 클래스이므로 괜찮습니다.AVLTree에서 요소를 검색하는 것은 일반 이진 트리에서 검색하는 것과 동일하므로 BST 클래스에 정의된 search 메서드는 AVLTree에서도 작동합니다.
insert 및 delete 메소드는 요소를 삽입 및 삭제하고 트리의 균형을 유지하기 위해 필요한 경우 재조정 작업을 수행하도록 재정의되었습니다.
위 내용은 AVL 트리를 위한 클래스 설계의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!