AVL 트리를 위한 클래스 설계

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이지만 createNewNode() AVLTree 클래스의 메소드는 AVLTreeNode입니다. AVLTreeNode는 TreeNode의 하위 클래스이므로 괜찮습니다.

AVLTree에서 요소를 검색하는 것은 일반 이진 트리에서 검색하는 것과 동일하므로 BST 클래스에 정의된 search 메서드도 작동합니다. AVLTree용.

insert 및 delete 메소드는 요소를 삽입 및 삭제하고 트리 균형을 유지하기 위해 필요한 경우 재조정 작업을 수행하도록 재정의되었습니다.

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