Golang 中的 AVL 树实现

17 Mar 2025 | 4 分钟阅读

在本文中，我们将使用 Golang 探索 AVL 树的实现。

AVL 树是一种自平衡二叉搜索树，它通过将左右子树高度差保持在最多一个来使树保持平衡。这使得搜索、插入和删除操作非常快速。

实现流程

搜索：搜索过程与传统二叉搜索树相同。我们从根节点开始，将要搜索的性能与当前节点的数据进行比较。然后，如果找到数据，则返回该树的节点。如果节点数据小于当前节点数据，则转到左子节点。如果数据大于当前节点数据，则转到右子节点。我们不断重复此过程，直到找到数据或到达叶节点。
插入：我们首先将节点放置在树中的合适位置。然后，我们从下往上遍历树，检查每个节点的平衡因子。当树中任何节点的平衡因子大于 1 或小于 -1 时，我们需要执行旋转操作以恢复树的平衡。
删除：删除过程与插入方法非常相似，唯一的区别是我们需要在删除节点之前检查树中每个节点的平衡因子。此外，如果任何节点的平衡因子大于 1 或小于 -1，则需要进行旋转。

下面是 Golang 中 AVL 树的代码

Golang 程序

package main

import "fmt"

type Node struct{
	key int
	left *Node
	right *Node
	height int
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func height(N *Node) int {
	if N == nil {
		return 0
	}
	return N.height
}
func newNode(key int) *Node {
	node := &Node{key: key}
	node.left = nil
	node.right = nil
	node.height = 1
	return node
}
func rightRotate(y *Node) *Node{
	x := y.left
	T2 := x.right
	x.right = y
	y.left = T2
	y.height = max(height(y.left), height(y.right)) + 1
	x.height = max(height(x.left), height(x.right)) + 1
	return x
}

func leftRotate(x *Node) *Node{
	y := x.right
	T2 := y.left
	y.left = x
	x.right = T2
	x.height = max(height(x.left), height(x.right)) + 1
	y.height = max(height(y.left), height(y.right)) + 1
	return y
}
func getBalanceFactor(N *Node) int {
	if N == nil {
		return 0
	}
	return height(N.left) - height(N.right)
}
func insertNode(node *Node, key int) *Node {
	if node == nil {
		return newNode(key)
	}
	if key < node.key {
		node.left = insertNode(node.left, key)
	} else if key > node.key {
		node.right = insertNode(node.right, key)
	} else {
		return node
	}

	node.height = 1 + max(height(node.left), height(node.right))
	balanceFactor := getBalanceFactor(node)

	if balanceFactor > 1 {
		if key < node.left.key {
			return rightRotate(node)
		} else if key > node.left.key {
			node.left = leftRotate(node.left)
			return rightRotate(node)
		}
	}

	if balanceFactor < -1 {
		if key > node.right.key {
			return leftRotate(node)
		} else if key < node.right.key {
			node.right = rightRotate(node.right)
			return leftRotate(node)
		}
	}

	return node
}
func nodeWithMinimumValue(node *Node) *Node {
	current := node
	for current.left != nil {
		current = current.left
	}
	return current
}
func deleteNode(root *Node, key int) *Node {

	if root == nil {
		return root
	}
	if key < root.key {
		root.left = deleteNode(root.left, key)
	} else if key > root.key {
		root.right = deleteNode(root.right, key)
	} else {
		if root.left == nil || root.right == nil {
			temp := root.left
			if temp == nil {
				temp = root.right
			}
			if temp == nil {
				temp = root
				root = nil
			} else {
				*root = *temp
			}
		} else {
			temp := nodeWithMinimumValue(root.right)
			root.key = temp.key
			root.right = deleteNode(root.right, temp.key)
		}
	}
	if root == nil {
		return root
	}
	root.height = 1 + max(height(root.left), height(root.right))
	balanceFactor := getBalanceFactor(root)

	if balanceFactor > 1 {
		if getBalanceFactor(root.left) >= 0 {
			return rightRotate(root)
		} else {
			root.left = leftRotate(root.left)
			return rightRotate(root)
		}
	}
	if balanceFactor < -1 {
		if getBalanceFactor(root.right) <= 0 {
			return leftRotate(root)
		} else {
			root.right = rightRotate(root.right)
			return leftRotate(root)
		}
	}
	return root
}

func printTree(root *Node, indent string, last bool){
	if root != nil {
		fmt.Print(indent)
		if last {
			fmt.Print("R----")
			indent += " "
		} else {
			fmt.Print("L----")
			indent += "| "
		}
		fmt.Println(root.key)
		printTree(root.left, indent, false)
		printTree(root.right, indent, true)
	}
}

func main(){

	root := insertNode(nil, 33)
	root = insertNode(root, 13)
	root = insertNode(root, 53)
	root = insertNode(root, 9)
	root = insertNode(root, 21)
	root = insertNode(root, 61)
	root = insertNode(root, 8)
	root = insertNode(root, 11)

	printTree(root, "", true)
	root = deleteNode(root, 13)
	fmt.Println("After deleting ")
	printTree(root, "", true)
}

输出

时间复杂度为 O(log n)。

辅助空间为 O(n)。

下一主题两个链表在 O(1) 时间内连接

Golang 中的 AVL 树实现

实现流程

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

Golang 中的 AVL 树实现

实现流程

相关帖子

哪个 Python 数据结构是不可变的

最长公共子串

螺旋形式打印给定矩阵

打印数字的第 k 个最低有效位

查找二叉树中的下一个更大元素

二进制链表的十进制等价物

使用 Trie 从字典生成所有可能的单词组合

使用堆的时间复杂度

二叉树枚举

二叉树的直径

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器