Back to Repositories

Testing AVL Tree Balance Operations in hello-algo

This test suite validates the implementation of an AVL (Adelson-Velsky and Landis) tree data structure in Go, focusing on core operations like insertion, deletion, and search. The tests ensure the tree maintains its self-balancing properties through various node manipulations.

Test Coverage Overview

The test suite provides comprehensive coverage of AVL tree operations:

Node insertion with automatic balancing
Deletion handling for nodes with different degrees (0, 1, and 2)
Duplicate node insertion scenarios
Search functionality verification
Tree balance maintenance after modifications

Implementation Analysis

The testing approach utilizes Go’s native testing framework with a focus on visual verification. Each operation is followed by tree visualization to confirm proper balancing and structure maintenance.

The implementation employs helper functions testInsert() and testRemove() to modularize the testing process and provide clear operation feedback.

Technical Details

Testing infrastructure includes:

Go testing package (testing)
Custom tree visualization utility (PrintTree)
AVL tree implementation (aVLTree)
Integration with hello-algo package for tree operations

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Systematic operation verification
Visual feedback for complex data structures
Modular test helper functions
Comprehensive edge case coverage
Clear test case organization and progression

krahets/hello-algo

codes/go/chapter_tree/avl_tree_test.go

            
// File: avl_tree_test.go
// Created Time: 2023-01-08
// Author: Reanon ([email protected])

package chapter_tree

import (
	"fmt"
	"testing"

	. "github.com/krahets/hello-algo/pkg"
)

func TestAVLTree(t *testing.T) {
	/* 初始化空 AVL 树 */
	tree := newAVLTree()
	/* 插入节点 */
	// 请关注插入节点后，AVL 树是如何保持平衡的
	testInsert(tree, 1)
	testInsert(tree, 2)
	testInsert(tree, 3)
	testInsert(tree, 4)
	testInsert(tree, 5)
	testInsert(tree, 8)
	testInsert(tree, 7)
	testInsert(tree, 9)
	testInsert(tree, 10)
	testInsert(tree, 6)

	/* 插入重复节点 */
	testInsert(tree, 7)

	/* 删除节点 */
	// 请关注删除节点后，AVL 树是如何保持平衡的
	testRemove(tree, 8) // 删除度为 0 的节点
	testRemove(tree, 5) // 删除度为 1 的节点
	testRemove(tree, 4) // 删除度为 2 的节点

	/* 查询节点 */
	node := tree.search(7)
	fmt.Printf("\n查找到的节点对象为 %#v ，节点值 = %d \n", node, node.Val)
}

func testInsert(tree *aVLTree, val int) {
	tree.insert(val)
	fmt.Printf("\n插入节点 %d 后，AVL 树为 \n", val)
	PrintTree(tree.root)
}

func testRemove(tree *aVLTree, val int) {
	tree.remove(val)
	fmt.Printf("\n删除节点 %d 后，AVL 树为 \n", val)
	PrintTree(tree.root)
}