餐饮网站模板,跨境网站建设,wordpress音乐主题推荐,win7记事本做网站文章目录 二叉树常用术语初始化插入与删除常见类型满二叉树完全二叉树完满二叉树平衡二叉树 二叉树退化二叉树遍历层序遍历前序、中序、后序遍历 数组表示二叉树表示完美二叉树表示任意二叉树 二叉搜索树查找节点插入节点删除节点遍历有序搜索效率常见应用 AVL树常见术语节点高… 文章目录 二叉树常用术语初始化插入与删除常见类型满二叉树完全二叉树完满二叉树平衡二叉树 二叉树退化二叉树遍历层序遍历前序、中序、后序遍历 数组表示二叉树表示完美二叉树表示任意二叉树 二叉搜索树查找节点插入节点删除节点遍历有序搜索效率常见应用 AVL树常见术语节点高度节点平衡因子 AVL 树旋转右旋左旋先左旋后右旋先右旋后左旋旋转的选择 常用操作插入节点删除节点查找节点 典型应用 二叉树
二叉树是一种非线性数据结构代表着祖先与后代之间的派生关系体现着“一分为二”的分治逻辑。与链表类似二叉树的基本单元是节点每个节点包含值、左子节点引用、右子节点引用。
Python
class TreeNode:二叉树节点类def __init__(self, val: int):self.val: int val # 节点值self.left: Optional[TreeNode] None # 左子节点引用self.right: Optional[TreeNode] None # 右子节点引用Go
/* 二叉树节点结构体 */
type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}
/* 节点初始化方法 */
func NewTreeNode(v int) *TreeNode {return TreeNode{Left: nil, // 左子节点指针Right: nil, // 右子节点指针Val: v, // 节点值}
}每个节点都有两个引用指针分别指向左子节点和右子节点 该节点被称为这两个子节点的父节点 。当给定一个二叉树的节点时我们将该节点的左子节点及其以下节点形成的树称为该节点的左子树同理可得右子树。
在二叉树中除叶节点外其他所有节点都包含子节点和非空子树。如下图所示如果将“节点 2”视为父节点则其左子节点和右子节点分别是“节点 4”和“节点 5”左子树是“节点 4 及其以下节点形成的树”右子树是“节点 5 及其以下节点形成的树”。 常用术语
根节点位于二叉树顶层的节点没有父节点。叶节点没有子节点的节点其两个指针均指向 None 。边连接两个节点的线段即节点引用指针。节点所在的层 从顶至底递增根节点所在层为 1 。节点的度 节点的子节点的数量。在二叉树中度的取值范围是 0、1、2 。二叉树的高度从根节点到最远叶节点所经过的边的数量。节点的深度从根节点到该节点所经过的边的数量。节点的高度从最远叶节点到该节点所经过的边的数量。 初始化
Python
# 初始化二叉树
# 初始化节点
n1 TreeNode(val1)
n2 TreeNode(val2)
n3 TreeNode(val3)
n4 TreeNode(val4)
n5 TreeNode(val5)
# 构建引用指向即指针
n1.left n2
n1.right n3
n2.left n4
n2.right n5Go
/* 初始化二叉树 */
// 初始化节点
n1 : NewTreeNode(1)
n2 : NewTreeNode(2)
n3 : NewTreeNode(3)
n4 : NewTreeNode(4)
n5 : NewTreeNode(5)
// 构建引用指向即指针
n1.Left n2
n1.Right n3
n2.Left n4
n2.Right n5插入与删除 Python
# 插入与删除节点
p TreeNode(0)
# 在 n1 - n2 中间插入节点 P
n1.left p
p.left n2
# 删除节点 P
n1.left n2Go
/* 插入与删除节点 */
// 在 n1 - n2 中间插入节点 P
p : NewTreeNode(0)
n1.Left p
p.Left n2
// 删除节点 P
n1.Left n2插入节点可能会改变二叉树的原有逻辑结构而删除节点通常意味着删除该节点及其所有子树。因此在二叉树中插入与删除操作通常是由一套操作配合完成的以实现有实际意义的操作。
常见类型
满二叉树
满二叉树又叫完美二叉树除了最底层外其余所有层的节点都被完全填满。在完美二叉树中叶节点的度为 0 其余所有节点的度都为 2 若树高度为 ℎ 则节点总数为 2^(ℎ1)−1 呈现标准的指数级关系反映了自然界中常见的细胞分裂现象。 完全二叉树
完全二叉树只有最底层的节点未被填满且最底层节点尽量靠左填充。 完满二叉树
完满二叉树除了叶节点之外其余所有节点都有两个子节点。 平衡二叉树
平衡二叉树中任意节点的左子树和右子树的高度之差的绝对值不超过 1 。 二叉树退化
当二叉树的每层节点都被填满时达到“完美二叉树”而当所有节点都偏向一侧时二叉树退化为“链表”。
完美二叉树是理想情况可以充分发挥二叉树“分治”的优势。链表则是另一个极端各项操作都变为线性操作时间复杂度退化至 O(n) 。 完美二叉树链表第 i 层的节点数量2^(i−1)1高度 ℎ 树的叶节点数量2^ℎ1高度 ℎ 树的节点总数2^(ℎ1)−1ℎ1节点总数n树的高度log2(n1)−1n-1
二叉树遍历
层序遍历
层序遍历从顶部到底部逐层遍历二叉树并在每一层按照从左到右的顺序访问节点。
层序遍历本质上属于广度优先遍历它体现了一种“一圈一圈向外扩展”的逐层遍历方式。 广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则而广度优先遍历则遵循“逐层推进”的规则两者背后的思想是一致的。
Python
def level_order(root: TreeNode | None) - list[int]:层序遍历# 初始化队列加入根节点queue: deque[TreeNode] deque()queue.append(root)# 初始化一个列表用于保存遍历序列res []while queue:node: TreeNode queue.popleft() # 队列出队res.append(node.val) # 保存节点值if node.left is not None:queue.append(node.left) # 左子节点入队if node.right is not None:queue.append(node.right) # 右子节点入队return resGo:
/* 层序遍历 */
func levelOrder(root *TreeNode) []any {// 初始化队列加入根节点queue : list.New()queue.PushBack(root)// 初始化一个切片用于保存遍历序列nums : make([]any, 0)for queue.Len() 0 {// 队列出队node : queue.Remove(queue.Front()).(*TreeNode)// 保存节点值nums append(nums, node.Val)if node.Left ! nil {// 左子节点入队queue.PushBack(node.Left)}if node.Right ! nil {// 右子节点入队queue.PushBack(node.Right)}}return nums
}时间复杂度 O(n) 所有节点被访问一次使用 O(n) 时间其中 n 为节点数量。空间复杂度 O(n) 在最差情况下即满二叉树时遍历到最底层之前队列中最多同时存在 (n1)/2 个节点占用 O(n) 空间。
前序、中序、后序遍历
前序、中序和后序遍历都属于深度优先遍历它体现了一种“先走到尽头再回溯继续”的遍历方式。下图展示了对二叉树进行深度优先遍历的工作原理。深度优先遍历就像是绕着整个二叉树的外围“走”一圈在每个节点都会遇到三个位置分别对应前序遍历、中序遍历和后序遍历。 深度优先搜索通常基于递归实现
Python
def pre_order(root: TreeNode | None):前序遍历if root is None:return# 访问优先级根节点 - 左子树 - 右子树res.append(root.val)pre_order(rootroot.left)pre_order(rootroot.right)def in_order(root: TreeNode | None):中序遍历if root is None:return# 访问优先级左子树 - 根节点 - 右子树in_order(rootroot.left)res.append(root.val)in_order(rootroot.right)def post_order(root: TreeNode | None):后序遍历if root is None:return# 访问优先级左子树 - 右子树 - 根节点post_order(rootroot.left)post_order(rootroot.right)res.append(root.val)Go
/* 前序遍历 */
func preOrder(node *TreeNode) {if node nil {return}// 访问优先级根节点 - 左子树 - 右子树nums append(nums, node.Val)preOrder(node.Left)preOrder(node.Right)
}/* 中序遍历 */
func inOrder(node *TreeNode) {if node nil {return}// 访问优先级左子树 - 根节点 - 右子树inOrder(node.Left)nums append(nums, node.Val)inOrder(node.Right)
}/* 后序遍历 */
func postOrder(node *TreeNode) {if node nil {return}// 访问优先级左子树 - 右子树 - 根节点postOrder(node.Left)postOrder(node.Right)nums append(nums, node.Val)
}下图展示了前序遍历二叉树的递归过程其可分为“递”和“归”两个逆向的部分。
“递”表示开启新方法程序在此过程中访问下一个节点。“归”表示函数返回代表当前节点已经访问完毕。 时间复杂度 O(n) 所有节点被访问一次使用 O(n) 时间。空间复杂度 O(n) 在最差情况下即树退化为链表时递归深度达到 n 系统占用 O(n) 栈帧空间。
数组表示二叉树
表示完美二叉树
给定一个完美二叉树我们将所有节点按照层序遍历的顺序存储在一个数组中则每个节点都对应唯一的数组索引。根据层序遍历的特性我们可以推导出父节点索引与子节点索引之间的“映射公式”若节点的索引为 i 则该节点的左子节点索引为 2i1 右子节点索引为 2i2 。 映射公式的角色相当于链表中的指针。给定数组中的任意一个节点我们都可以通过映射公式来访问它的左右子节点。
表示任意二叉树
完美二叉树是一个特例在二叉树的中间层通常存在许多 None 。由于层序遍历序列并不包含这些 None 因此我们无法仅凭该序列来推测 None 的数量和分布位置。这意味着存在多种二叉树结构都符合该层序遍历序列。 我们可以考虑在层序遍历序列中显式地写出所有 None 这样处理后层序遍历序列就可以唯一表示二叉树了。
Python
# 二叉树的数组表示
# 使用 None 来表示空位
tree [1, 2, 3, 4, None, 6, 7, 8, 9, None, None, 12, None, None, 15]Go
/* 二叉树的数组表示 */
// 使用 any 类型的切片, 就可以使用 nil 来标记空位
tree : []any{1, 2, 3, 4, nil, 6, 7, 8, 9, nil, nil, 12, nil, nil, 15}完全二叉树非常适合使用数组来表示。回顾完全二叉树的定义None 只出现在最底层且靠右的位置因此所有 None 一定出现在层序遍历序列的末尾。这意味着使用数组表示完全二叉树时可以省略存储所有 None 非常方便。 以下代码实现了一个基于数组表示的二叉树包括以下几种操作。
给定某节点获取它的值、左右子节点、父节点。获取前序遍历、中序遍历、后序遍历、层序遍历序列。
Python
class ArrayBinaryTree:数组表示下的二叉树类def __init__(self, arr: list[int | None]):构造方法self.__tree list(arr)def size(self):节点数量return len(self.__tree)def val(self, i: int) - int:获取索引为 i 节点的值# 若索引越界则返回 None 代表空位if i 0 or i self.size():return Nonereturn self.__tree[i]def left(self, i: int) - int | None:获取索引为 i 节点的左子节点的索引return 2 * i 1def right(self, i: int) - int | None:获取索引为 i 节点的右子节点的索引return 2 * i 2def parent(self, i: int) - int | None:获取索引为 i 节点的父节点的索引return (i - 1) // 2def level_order(self) - list[int]:层序遍历self.res []# 直接遍历数组for i in range(self.size()):if self.val(i) is not None:self.res.append(self.val(i))return self.resdef __dfs(self, i: int, order: str):深度优先遍历if self.val(i) is None:return# 前序遍历if order pre:self.res.append(self.val(i))self.__dfs(self.left(i), order)# 中序遍历if order in:self.res.append(self.val(i))self.__dfs(self.right(i), order)# 后序遍历if order post:self.res.append(self.val(i))def pre_order(self) - list[int]:前序遍历self.res []self.__dfs(0, orderpre)return self.resdef in_order(self) - list[int]:中序遍历self.res []self.__dfs(0, orderin)return self.resdef post_order(self) - list[int]:后序遍历self.res []self.__dfs(0, orderpost)return self.resGo
/* 数组表示下的二叉树类 */
type arrayBinaryTree struct {tree []any
}/* 构造方法 */
func newArrayBinaryTree(arr []any) *arrayBinaryTree {return arrayBinaryTree{tree: arr,}
}/* 节点数量 */
func (abt *arrayBinaryTree) size() int {return len(abt.tree)
}/* 获取索引为 i 节点的值 */
func (abt *arrayBinaryTree) val(i int) any {// 若索引越界则返回 null 代表空位if i 0 || i abt.size() {return nil}return abt.tree[i]
}/* 获取索引为 i 节点的左子节点的索引 */
func (abt *arrayBinaryTree) left(i int) int {return 2*i 1
}/* 获取索引为 i 节点的右子节点的索引 */
func (abt *arrayBinaryTree) right(i int) int {return 2*i 2
}/* 获取索引为 i 节点的父节点的索引 */
func (abt *arrayBinaryTree) parent(i int) int {return (i - 1) / 2
}/* 层序遍历 */
func (abt *arrayBinaryTree) levelOrder() []any {var res []any// 直接遍历数组for i : 0; i abt.size(); i {if abt.val(i) ! nil {res append(res, abt.val(i))}}return res
}/* 深度优先遍历 */
func (abt *arrayBinaryTree) dfs(i int, order string, res *[]any) {// 若为空位则返回if abt.val(i) nil {return}// 前序遍历if order pre {*res append(*res, abt.val(i))}abt.dfs(abt.left(i), order, res)// 中序遍历if order in {*res append(*res, abt.val(i))}abt.dfs(abt.right(i), order, res)// 后序遍历if order post {*res append(*res, abt.val(i))}
}/* 前序遍历 */
func (abt *arrayBinaryTree) preOrder() []any {var res []anyabt.dfs(0, pre, res)return res
}/* 中序遍历 */
func (abt *arrayBinaryTree) inOrder() []any {var res []anyabt.dfs(0, in, res)return res
}/* 后序遍历 */
func (abt *arrayBinaryTree) postOrder() []any {var res []anyabt.dfs(0, post, res)return res
}二叉树的数组表示主要有以下优点。
数组存储在连续的内存空间中对缓存友好访问与遍历速度较快。不需要存储指针比较节省空间。允许随机访问节点。
然而数组表示也存在一些局限性。
数组存储需要连续内存空间因此不适合存储数据量过大的树。增删节点需要通过数组插入与删除操作实现效率较低。当二叉树中存在大量 None 时数组中包含的节点数据比重较低空间利用率较低。
二叉搜索树
二叉搜索树满足以下条件。
对于根节点左子树中所有节点的值 根节点的值 右子树中所有节点的值。任意节点的左、右子树也是二叉搜索树即同样满足条件 1. 。 将二叉搜索树封装为一个类 ArrayBinaryTree 并声明一个成员变量 root 指向树的根节点。
查找节点
给定目标节点值 num 可以根据二叉搜索树的性质来查找。我们声明一个节点 cur 从二叉树的根节点 root 出发循环比较节点值 cur.val 和 num 之间的大小关系。
若 cur.val num 说明目标节点在 cur 的右子树中因此执行 cur cur.right 。若 cur.val num 说明目标节点在 cur 的左子树中因此执行 cur cur.left 。若 cur.val num 说明找到目标节点跳出循环并返回该节点。 二叉搜索树的查找操作与二分查找算法的工作原理一致都是每轮排除一半情况。循环次数最多为二叉树的高度当二叉树平衡时使用O(logn) 时间。
Python
def search(self, num: int) - TreeNode | None:查找节点cur self.__root# 循环查找越过叶节点后跳出while cur is not None:# 目标节点在 cur 的右子树中if cur.val num:cur cur.right# 目标节点在 cur 的左子树中elif cur.val num:cur cur.left# 找到目标节点跳出循环else:breakreturn curGo
/* 查找节点 */
func (bst *binarySearchTree) search(num int) *TreeNode {node : bst.root// 循环查找越过叶节点后跳出for node ! nil {if node.Val.(int) num {// 目标节点在 cur 的右子树中node node.Right} else if node.Val.(int) num {// 目标节点在 cur 的左子树中node node.Left} else {// 找到目标节点跳出循环break}}// 返回目标节点return node
}插入节点
给定一个待插入元素 num 为了保持二叉搜索树“左子树 根节点 右子树”的性质
查找插入位置与查找操作相似从根节点出发根据当前节点值和 num 的大小关系循环向下搜索直到越过叶节点遍历至 None 时跳出循环。在该位置插入节点初始化节点 num 将该节点置于 None 的位置。 在代码实现中需要注意以下两点。
二叉搜索树不允许存在重复节点否则将违反其定义。因此若待插入节点在树中已存在则不执行插入直接返回。为了实现插入节点我们需要借助节点 pre 保存上一轮循环的节点。这样在遍历至 None 时我们可以获取到其父节点从而完成节点插入操作。
Python
def insert(self, num: int):插入节点# 若树为空则初始化根节点if self.__root is None:self.__root TreeNode(num)return# 循环查找越过叶节点后跳出cur, pre self.__root, Nonewhile cur is not None:# 找到重复节点直接返回if cur.val num:returnpre cur# 插入位置在 cur 的右子树中if cur.val num:cur cur.right# 插入位置在 cur 的左子树中else:cur cur.left# 插入节点node TreeNode(num)if pre.val num:pre.right nodeelse:pre.left nodeGo
/* 插入节点 */
func (bst *binarySearchTree) insert(num int) {cur : bst.root// 若树为空则初始化根节点if cur nil {bst.root NewTreeNode(num)return}// 待插入节点之前的节点位置var pre *TreeNode nil// 循环查找越过叶节点后跳出for cur ! nil {if cur.Val num {return}pre curif cur.Val.(int) num {cur cur.Right} else {cur cur.Left}}// 插入节点node : NewTreeNode(num)if pre.Val.(int) num {pre.Right node} else {pre.Left node}
}删除节点
先在二叉树中查找到目标节点再将其从二叉树中删除。与插入节点类似我们需要保证在删除操作完成后二叉搜索树的“左子树 根节点 右子树”的性质仍然满足。因此我们需要根据目标节点的子节点数量共分为 0、1 和 2 这三种情况执行对应的删除节点操作。
当待删除节点的度为 0 时表示该节点是叶节点可以直接删除。 当待删除节点的度为 1 时将待删除节点替换为其子节点即可。 当待删除节点的度为 2 时我们无法直接删除它而需要使用一个节点替换该节点。由于要保持二叉搜索树“左 根 右”的性质因此这个节点可以是右子树的最小节点或左子树的最大节点。
假设我们选择右子树的最小节点即中序遍历的下一个节点则删除操作流程如下图 所示。
找到待删除节点在“中序遍历序列”中的下一个节点记为 tmp 。将 tmp 的值覆盖待删除节点的值并在树中递归删除节点 tmp 。 删除节点操作同样使用 O(logn) 时间其中查找待删除节点需要 O(logn) 时间获取中序遍历后继节点需要 O(logn) 时间。
Python
def remove(self, num: int):删除节点# 若树为空直接提前返回if self.__root is None:return# 循环查找越过叶节点后跳出cur, pre self.__root, Nonewhile cur is not None:# 找到待删除节点跳出循环if cur.val num:breakpre cur# 待删除节点在 cur 的右子树中if cur.val num:cur cur.right# 待删除节点在 cur 的左子树中else:cur cur.left# 若无待删除节点则直接返回if cur is None:return# 子节点数量 0 or 1if cur.left is None or cur.right is None:# 当子节点数量 0 / 1 时 child null / 该子节点child cur.left or cur.right# 删除节点 curif cur ! self.__root:if pre.left cur:pre.left childelse:pre.right childelse:# 若删除节点为根节点则重新指定根节点self.__root child# 子节点数量 2else:# 获取中序遍历中 cur 的下一个节点tmp: TreeNode cur.rightwhile tmp.left is not None:tmp tmp.left# 递归删除节点 tmpself.remove(tmp.val)# 用 tmp 覆盖 curcur.val tmp.valGo
/* 删除节点 */
func (bst *binarySearchTree) remove(num int) {cur : bst.root// 若树为空直接提前返回if cur nil {return}// 待删除节点之前的节点位置var pre *TreeNode nil// 循环查找越过叶节点后跳出for cur ! nil {if cur.Val num {break}pre curif cur.Val.(int) num {// 待删除节点在右子树中cur cur.Right} else {// 待删除节点在左子树中cur cur.Left}}// 若无待删除节点则直接返回if cur nil {return}// 子节点数为 0 或 1if cur.Left nil || cur.Right nil {var child *TreeNode nil// 取出待删除节点的子节点if cur.Left ! nil {child cur.Left} else {child cur.Right}// 删除节点 curif cur ! bst.root {if pre.Left cur {pre.Left child} else {pre.Right child}} else {// 若删除节点为根节点则重新指定根节点bst.root child}// 子节点数为 2} else {// 获取中序遍历中待删除节点 cur 的下一个节点tmp : cur.Rightfor tmp.Left ! nil {tmp tmp.Left}// 递归删除节点 tmpbst.remove(tmp.Val.(int))// 用 tmp 覆盖 curcur.Val tmp.Val}
}遍历有序
二叉树的中序遍历遵循“左 → 根 → 右”的遍历顺序而二叉搜索树满足“左子节点 根节点 右子节点”的大小关系。这意味着在二叉搜索树中进行中序遍历时总是会优先遍历下一个最小节点从而得出一个重要性质二叉搜索树的中序遍历序列是升序的。利用中序遍历升序的性质我们在二叉搜索树中获取有序数据仅需 O(n) 时间无须进行额外的排序操作非常高效。 搜索效率
给定一组数据考虑使用数组或二叉搜索树存储。二叉搜索树的各项操作的时间复杂度都是对数阶具有稳定且高效的性能表现。只有在高频添加、低频查找删除的数据适用场景下数组比二叉搜索树的效率更高。
无序数组二叉搜索树查找元素O(n)O(logn)插入元素O(1)O(logn)删除元素O(n)O(logn)
在理想情况下二叉搜索树是“平衡”的这样就可以在 logn 轮循环内查找任意节点。然而如果我们在二叉搜索树中不断地插入和删除节点可能导致二叉树退化为链表这时各种操作的时间复杂度也会退化为O(n)。 常见应用
用作系统中的多级索引实现高效的查找、插入、删除操作。作为某些搜索算法的底层数据结构。用于存储数据流以保持其有序状态。
AVL树
在二叉搜索树章节中我们提到了在多次插入和删除操作后二叉搜索树可能退化为链表。这种情况下所有操作的时间复杂度将从O(logn) 恶化为 O(n)。
如下图所示经过两次删除节点操作这个二叉搜索树便会退化为链表。 又如下图完美二叉树中插入两个节点后树将严重向左倾斜查找操作的时间复杂度也随之恶化。 而对于AVL树在持续添加和删除节点后其不会退化从而使得各种操作的时间复杂度保持在n(logn) 级别。换句话说在需要频繁进行增删查改操作的场景中AVL 树能始终保持高效的数据操作性能具有很好的应用价值。
常见术语
AVL 树既是二叉搜索树也是平衡二叉树同时满足这两类二叉树的所有性质因此也被称为平衡二叉搜索树 。
节点高度
由于 AVL 树的相关操作需要获取节点高度因此我们需要为节点类添加 height 变量。
Python
class TreeNode:AVL 树节点类def __init__(self, val: int):self.val: int val # 节点值self.height: int 0 # 节点高度self.left: Optional[TreeNode] None # 左子节点引用self.right: Optional[TreeNode] None # 右子节点引用Go
/* AVL 树节点结构体 */
type TreeNode struct {Val int // 节点值Height int // 节点高度Left *TreeNode // 左子节点引用Right *TreeNode // 右子节点引用
}“节点高度”是指从该节点到最远叶节点的距离即所经过的“边”的数量。需要特别注意的是叶节点的高度为 0 而空节点的高度为 -1 。创建两个工具函数分别用于获取和更新节点的高度。
Python
def height(self, node: TreeNode | None) - int:获取节点高度# 空节点高度为 -1 叶节点高度为 0if node is not None:return node.heightreturn -1def __update_height(self, node: TreeNode | None):更新节点高度# 节点高度等于最高子树高度 1node.height max([self.height(node.left), self.height(node.right)]) 1Go
/* 获取节点高度 */
func (t *aVLTree) height(node *TreeNode) int {// 空节点高度为 -1 叶节点高度为 0if node ! nil {return node.Height}return -1
}/* 更新节点高度 */
func (t *aVLTree) updateHeight(node *TreeNode) {lh : t.height(node.Left)rh : t.height(node.Right)// 节点高度等于最高子树高度 1if lh rh {node.Height lh 1} else {node.Height rh 1}
}节点平衡因子
节点的平衡因子定义为节点左子树的高度减去右子树的高度同时规定空节点的平衡因子为 0 。同样将获取节点平衡因子的功能封装成函数方便后续使用。
Python
def balance_factor(self, node: TreeNode | None) - int:获取平衡因子# 空节点平衡因子为 0if node is None:return 0# 节点平衡因子 左子树高度 - 右子树高度return self.height(node.left) - self.height(node.right)Go
/* 获取平衡因子 */
func (t *aVLTree) balanceFactor(node *TreeNode) int {// 空节点平衡因子为 0if node nil {return 0}// 节点平衡因子 左子树高度 - 右子树高度return t.height(node.Left) - t.height(node.Right)
}设平衡因子为f则一棵 AVL 树的任意节点的平衡因子皆满足 −1≤f≤1 。
AVL 树旋转
AVL 树的特点在于“旋转”操作它能够在不影响二叉树的中序遍历序列的前提下使失衡节点重新恢复平衡。换句话说旋转操作既能保持“二叉搜索树”的性质也能使树重新变为“平衡二叉树”。将平衡因子绝对值 1 的节点称为“失衡节点”。根据节点失衡情况的不同旋转操作分为四种右旋、左旋、先右旋后左旋、先左旋后右旋。
右旋
如下图所示节点下方为平衡因子。从底至顶看二叉树中首个失衡节点是“节点 3”。我们关注以该失衡节点为根节点的子树将该节点记为 node 其左子节点记为 child 执行“右旋”操作。完成右旋后子树已经恢复平衡并且仍然保持二叉搜索树的特性。 当节点 child 有右子节点记为 grandChild 时需要在右旋中添加一步将 grandChild 作为 node 的左子节点。 “向右旋转”是一种形象化的说法实际上需要通过修改节点指针来实现代码如下所示:
Python
def __right_rotate(self, node: TreeNode | None) - TreeNode | None:右旋操作child node.leftgrand_child child.right# 以 child 为原点将 node 向右旋转child.right nodenode.left grand_child# 更新节点高度self.__update_height(node)self.__update_height(child)# 返回旋转后子树的根节点return childGo
/* 右旋操作 */
func (t *aVLTree) rightRotate(node *TreeNode) *TreeNode {child : node.LeftgrandChild : child.Right// 以 child 为原点将 node 向右旋转child.Right nodenode.Left grandChild// 更新节点高度t.updateHeight(node)t.updateHeight(child)// 返回旋转后子树的根节点return child
}左旋
相应的如果考虑上述失衡二叉树的“镜像”则需要执行“左旋”操作。 当节点 child 有左子节点记为 grandChild 时需要在左旋中添加一步将 grandChild 作为 node 的右子节点。 可以观察到右旋和左旋操作在逻辑上是镜像对称的它们分别解决的两种失衡情况也是对称的。基于对称性只需将右旋的实现代码中的所有的 left 替换为 right 将所有的 right 替换为 left 即可得到左旋的实现代码。
Python
def __left_rotate(self, node: TreeNode | None) - TreeNode | None:左旋操作child node.rightgrand_child child.left# 以 child 为原点将 node 向左旋转child.left nodenode.right grand_child# 更新节点高度self.__update_height(node)self.__update_height(child)# 返回旋转后子树的根节点return childGo
/* 左旋操作 */
func (t *aVLTree) leftRotate(node *TreeNode) *TreeNode {child : node.RightgrandChild : child.Left// 以 child 为原点将 node 向左旋转child.Left nodenode.Right grandChild// 更新节点高度t.updateHeight(node)t.updateHeight(child)// 返回旋转后子树的根节点return child
}先左旋后右旋
对于下图中的失衡节点 3 仅使用左旋或右旋都无法使子树恢复平衡。此时需要先对 child 执行“左旋”再对 node 执行“右旋”。 先右旋后左旋
对于上述失衡二叉树的镜像情况需要先对 child 执行“右旋”然后对 node 执行“左旋”。 旋转的选择
下图展示的四种失衡情况与上述案例逐个对应分别需要采用右旋、左旋、先右后左、先左后右的旋转操作。 如下表所示我们通过判断失衡节点的平衡因子以及较高一侧子节点的平衡因子的正负号来确定失衡节点属于上图中的哪种情况。
失衡节点的平衡因子子节点的平衡因子应采用的旋转方法1 即左偏树≥0右旋1 即左偏树0先左旋后右旋−1 即右偏树≤0左旋−1 即右偏树0先右旋后左旋
为了便于使用将旋转操作封装成一个函数。有了这个函数就能对各种失衡情况进行旋转使失衡节点重新恢复平衡。
Python
def __rotate(self, node: TreeNode | None) - TreeNode | None:执行旋转操作使该子树重新恢复平衡# 获取节点 node 的平衡因子balance_factor self.balance_factor(node)# 左偏树if balance_factor 1:if self.balance_factor(node.left) 0:# 右旋return self.__right_rotate(node)else:# 先左旋后右旋node.left self.__left_rotate(node.left)return self.__right_rotate(node)# 右偏树elif balance_factor -1:if self.balance_factor(node.right) 0:# 左旋return self.__left_rotate(node)else:# 先右旋后左旋node.right self.__right_rotate(node.right)return self.__left_rotate(node)# 平衡树无须旋转直接返回return nodeGo
/* 执行旋转操作使该子树重新恢复平衡 */
func (t *aVLTree) rotate(node *TreeNode) *TreeNode {// 获取节点 node 的平衡因子// Go 推荐短变量这里 bf 指代 t.balanceFactorbf : t.balanceFactor(node)// 左偏树if bf 1 {if t.balanceFactor(node.Left) 0 {// 右旋return t.rightRotate(node)} else {// 先左旋后右旋node.Left t.leftRotate(node.Left)return t.rightRotate(node)}}// 右偏树if bf -1 {if t.balanceFactor(node.Right) 0 {// 左旋return t.leftRotate(node)} else {// 先右旋后左旋node.Right t.rightRotate(node.Right)return t.leftRotate(node)}}// 平衡树无须旋转直接返回return node
}常用操作
插入节点
AVL 树的节点插入操作与二叉搜索树在主体上类似。唯一的区别在于在 AVL 树中插入节点后从该节点到根节点的路径上可能会出现一系列失衡节点。因此我们需要从这个节点开始自底向上执行旋转操作使所有失衡节点恢复平衡。
Python
def insert(self, val):插入节点self.root self.__insert_helper(self.root, val)def __insert_helper(self, node: TreeNode | None, val: int) - TreeNode:递归插入节点辅助方法if node is None:return TreeNode(val)# 1. 查找插入位置并插入节点if val node.val:node.left self.__insert_helper(node.left, val)elif val node.val:node.right self.__insert_helper(node.right, val)else:# 重复节点不插入直接返回return node# 更新节点高度self.__update_height(node)# 2. 执行旋转操作使该子树重新恢复平衡return self.__rotate(node)Go
/* 插入节点 */
func (t *aVLTree) insert(val int) {t.root t.insertHelper(t.root, val)
}/* 递归插入节点辅助函数 */
func (t *aVLTree) insertHelper(node *TreeNode, val int) *TreeNode {if node nil {return NewTreeNode(val)}/* 1. 查找插入位置并插入节点 */if val node.Val.(int) {node.Left t.insertHelper(node.Left, val)} else if val node.Val.(int) {node.Right t.insertHelper(node.Right, val)} else {// 重复节点不插入直接返回return node}// 更新节点高度t.updateHeight(node)/* 2. 执行旋转操作使该子树重新恢复平衡 */node t.rotate(node)// 返回子树的根节点return node
}删除节点
类似地在二叉搜索树的删除节点方法的基础上需要从底至顶地执行旋转操作使所有失衡节点恢复平衡。
Python
def remove(self, val: int):删除节点self.root self.__remove_helper(self.root, val)def __remove_helper(self, node: TreeNode | None, val: int) - TreeNode | None:递归删除节点辅助方法if node is None:return None# 1. 查找节点并删除之if val node.val:node.left self.__remove_helper(node.left, val)elif val node.val:node.right self.__remove_helper(node.right, val)else:if node.left is None or node.right is None:child node.left or node.right# 子节点数量 0 直接删除 node 并返回if child is None:return None# 子节点数量 1 直接删除 nodeelse:node childelse:# 子节点数量 2 则将中序遍历的下个节点删除并用该节点替换当前节点temp node.rightwhile temp.left is not None:temp temp.leftnode.right self.__remove_helper(node.right, temp.val)node.val temp.val# 更新节点高度self.__update_height(node)# 2. 执行旋转操作使该子树重新恢复平衡return self.__rotate(node)Go
/* 删除节点 */
func (t *aVLTree) remove(val int) {t.root t.removeHelper(t.root, val)
}/* 递归删除节点辅助函数 */
func (t *aVLTree) removeHelper(node *TreeNode, val int) *TreeNode {if node nil {return nil}/* 1. 查找节点并删除之 */if val node.Val.(int) {node.Left t.removeHelper(node.Left, val)} else if val node.Val.(int) {node.Right t.removeHelper(node.Right, val)} else {if node.Left nil || node.Right nil {child : node.Leftif node.Right ! nil {child node.Right}if child nil {// 子节点数量 0 直接删除 node 并返回return nil} else {// 子节点数量 1 直接删除 nodenode child}} else {// 子节点数量 2 则将中序遍历的下个节点删除并用该节点替换当前节点temp : node.Rightfor temp.Left ! nil {temp temp.Left}node.Right t.removeHelper(node.Right, temp.Val.(int))node.Val temp.Val}}// 更新节点高度t.updateHeight(node)/* 2. 执行旋转操作使该子树重新恢复平衡 */node t.rotate(node)// 返回子树的根节点return node
}查找节点
AVL 树的节点查找操作与二叉搜索树一致。
典型应用
组织和存储大型数据适用于高频查找、低频增删的场景。用于构建数据库中的索引系统。红黑树在许多应用中比 AVL 树更受欢迎。这是因为红黑树的平衡条件相对宽松在红黑树中插入与删除节点所需的旋转操作相对较少其节点增删操作的平均效率更高。
Referenceshttps://www.hello-algo.com/chapter_tree/
