AVL树是一种自平衡二叉搜索树,其中任何节点的两个子树的高度差最多为1。通过旋转操作保持树的平衡,确保操作的最坏时间复杂度为O(log n)。
AVL树是一种自平衡二叉搜索树,它在普通二叉搜索树的基础上增加了平衡因子的概念,保证树的任何节点的左右子树高度差不超过1,保证查找、插入和删除操作的时间复杂度稳定在O(log n)。
AVL树中的几个关键概念:
▼Java复制代码/** * AVL树的Java实现 */ public class AVLTree { // 树节点定义 class Node { int key; // 节点值 Node left; // 左子节点 Node right; // 右子节点 int height; // 节点高度 Node(int key) { this.key = key; this.height = 1; // 新节点高度初始为1 } } Node root; // 根节点 // 获取节点高度,空节点高度为0 private int height(Node node) { if (node == null) { return 0; } return node.height; } // 获取节点的平衡因子 private int getBalanceFactor(Node node) { if (node == null) { return 0; } return height(node.left) - height(node.right); } // 更新节点高度 private void updateHeight(Node node) { if (node == null) { return; } node.height = Math.max(height(node.left), height(node.right)) + 1; } // 右旋转(处理左左情况) private Node rotateRight(Node y) { Node x = y.left; Node T2 = x.right; // 执行旋转 x.right = y; y.left = T2; // 更新高度 updateHeight(y); updateHeight(x); return x; // 返回新的根节点 } // 左旋转(处理右右情况) private Node rotateLeft(Node x) { Node y = x.right; Node T2 = y.left; // 执行旋转 y.left = x; x.right = T2; // 更新高度 updateHeight(x); updateHeight(y); return y; // 返回新的根节点 } // 插入节点 public void insert(int key) { root = insertNode(root, key); } private Node insertNode(Node node, int key) { // 1. 执行标准BST插入 if (node == null) { return new Node(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; } // 2. 更新节点高度 updateHeight(node); // 3. 获取平衡因子 int balance = getBalanceFactor(node); // 4. 如果节点失衡,进行旋转调整 // 左左情况 - 右旋 if (balance > 1 && getBalanceFactor(node.left) >= 0) { return rotateRight(node); } // 右右情况 - 左旋 if (balance < -1 && getBalanceFactor(node.right) <= 0) { return rotateLeft(node); } // 左右情况 - 左右双旋 if (balance > 1 && getBalanceFactor(node.left) < 0) { node.left = rotateLeft(node.left); return rotateRight(node); } // 右左情况 - 右左双旋 if (balance < -1 && getBalanceFactor(node.right) > 0) { node.right = rotateRight(node.right); return rotateLeft(node); } // 返回未变化的节点引用 return node; } // 查找最小值节点 private Node findMinNode(Node node) { Node current = node; while (current.left != null) { current = current.left; } return current; } // 删除节点 public void delete(int key) { root = deleteNode(root, key); } private Node deleteNode(Node root, int key) { // 1. 执行标准BST删除 if (root == null) { return root; } if (key < root.key) { root.left = deleteNode(root.left, key); } else if (key > root.key) { root.right = deleteNode(root.right, key); } else { // 找到要删除的节点 // 情况1:叶子节点或只有一个子节点 if (root.left == null || root.right == null) { Node temp = (root.left != null) ? root.left : root.right; // 没有子节点 if (temp == null) { root = null; } else { // 一个子节点 root = temp; } } else { // 情况2:有两个子节点 // 找到右子树的最小节点(中序后继) Node temp = findMinNode(root.right); // 复制中序后继的值到当前节点 root.key = temp.key; // 删除中序后继 root.right = deleteNode(root.right, temp.key); } } // 如果树只有一个节点,删除后直接返回 if (root == null) { return root; } // 2. 更新高度 updateHeight(root); // 3. 获取平衡因子 int balance = getBalanceFactor(root); // 4. 进行旋转操作保持平衡 // 左左情况 if (balance > 1 && getBalanceFactor(root.left) >= 0) { return rotateRight(root); } // 左右情况 if (balance > 1 && getBalanceFactor(root.left) < 0) { root.left = rotateLeft(root.left); return rotateRight(root); } // 右右情况 if (balance < -1 && getBalanceFactor(root.right) <= 0) { return rotateLeft(root); } // 右左情况 if (balance < -1 && getBalanceFactor(root.right) > 0) { root.right = rotateRight(root.right); return rotateLeft(root); } return root; } // 查找节点 public boolean search(int key) { return searchNode(root, key); } private boolean searchNode(Node root, int key) { if (root == null) { return false; } if (key == root.key) { return true; } if (key < root.key) { return searchNode(root.left, key); } else { return searchNode(root.right, key); } } }
▼Javascript复制代码/** * AVL树的JavaScript实现 */ class Node { constructor(key) { this.key = key; this.left = null; this.right = null; this.height = 1; // 新节点高度初始为1 } } class AVLTree { constructor() { this.root = null; } // 获取节点高度,空节点高度为0 height(node) { if (node === null) { return 0; } return node.height; } // 获取节点的平衡因子 getBalanceFactor(node) { if (node === null) { return 0; } return this.height(node.left) - this.height(node.right); } // 更新节点高度 updateHeight(node) { if (node === null) { return; } node.height = Math.max(this.height(node.left), this.height(node.right)) + 1; } // 右旋转(处理左左情况) rotateRight(y) { const x = y.left; const T2 = x.right; // 执行旋转 x.right = y; y.left = T2; // 更新高度 this.updateHeight(y); this.updateHeight(x); return x; // 返回新的根节点 } // 左旋转(处理右右情况) rotateLeft(x) { const y = x.right; const T2 = y.left; // 执行旋转 y.left = x; x.right = T2; // 更新高度 this.updateHeight(x); this.updateHeight(y); return y; // 返回新的根节点 } // 插入节点 insert(key) { this.root = this.insertNode(this.root, key); } insertNode(node, key) { // 1. 执行标准BST插入 if (node === null) { return new Node(key); } if (key < node.key) { node.left = this.insertNode(node.left, key); } else if (key > node.key) { node.right = this.insertNode(node.right, key); } else { // 相同键值不做处理,或根据需求更新节点 return node; } // 2. 更新节点高度 this.updateHeight(node); // 3. 获取平衡因子 const balance = this.getBalanceFactor(node); // 4. 如果节点失衡,进行旋转调整 // 左左情况 - 右旋 if (balance > 1 && this.getBalanceFactor(node.left) >= 0) { return this.rotateRight(node); } // 右右情况 - 左旋 if (balance < -1 && this.getBalanceFactor(node.right) <= 0) { return this.rotateLeft(node); } // 左右情况 - 左右双旋 if (balance > 1 && this.getBalanceFactor(node.left) < 0) { node.left = this.rotateLeft(node.left); return this.rotateRight(node); } // 右左情况 - 右左双旋 if (balance < -1 && this.getBalanceFactor(node.right) > 0) { node.right = this.rotateRight(node.right); return this.rotateLeft(node); } // 返回未变化的节点引用 return node; } // 查找最小值节点 findMinNode(node) { let current = node; while (current.left !== null) { current = current.left; } return current; } // 删除节点 delete(key) { this.root = this.deleteNode(this.root, key); } deleteNode(root, key) { // 1. 执行标准BST删除 if (root === null) { return root; } if (key < root.key) { root.left = this.deleteNode(root.left, key); } else if (key > root.key) { root.right = this.deleteNode(root.right, key); } else { // 找到要删除的节点 // 情况1:叶子节点或只有一个子节点 if (root.left === null || root.right === null) { const temp = root.left !== null ? root.left : root.right; // 没有子节点 if (temp === null) { root = null; } else { // 一个子节点 root = temp; } } else { // 情况2:有两个子节点 // 找到右子树的最小节点(中序后继) const temp = this.findMinNode(root.right); // 复制中序后继的值到当前节点 root.key = temp.key; // 删除中序后继 root.right = this.deleteNode(root.right, temp.key); } } // 如果树只有一个节点,删除后直接返回 if (root === null) { return root; } // 2. 更新高度 this.updateHeight(root); // 3. 获取平衡因子 const balance = this.getBalanceFactor(root); // 4. 进行旋转操作保持平衡 // 左左情况 if (balance > 1 && this.getBalanceFactor(root.left) >= 0) { return this.rotateRight(root); } // 左右情况 if (balance > 1 && this.getBalanceFactor(root.left) < 0) { root.left = this.rotateLeft(root.left); return this.rotateRight(root); } // 右右情况 if (balance < -1 && this.getBalanceFactor(root.right) <= 0) { return this.rotateLeft(root); } // 右左情况 if (balance < -1 && this.getBalanceFactor(root.right) > 0) { root.right = this.rotateRight(root.right); return this.rotateLeft(root); } return root; } // 查找节点 search(key) { return this.searchNode(this.root, key); } searchNode(root, key) { if (root === null) { return false; } if (key === root.key) { return true; } if (key < root.key) { return this.searchNode(root.left, key); } else { return this.searchNode(root.right, key); } } // 中序遍历 inorder() { const result = []; this.inorderTraversal(this.root, result); return result; } inorderTraversal(node, result) { if (node !== null) { this.inorderTraversal(node.left, result); result.push(node.key); this.inorderTraversal(node.right, result); } } }
▼Python复制代码class Node: def __init__(self, key): self.key = key self.left = None self.right = None self.height = 1 # 新节点高度初始为1 class AVLTree: def __init__(self): self.root = None # 获取节点高度,空节点高度为0 def height(self, node): if node is None: return 0 return node.height # 获取节点的平衡因子 def get_balance_factor(self, node): if node is None: return 0 return self.height(node.left) - self.height(node.right) # 更新节点高度 def update_height(self, node): if node is None: return node.height = max(self.height(node.left), self.height(node.right)) + 1 # 右旋转(处理左左情况) def rotate_right(self, y): x = y.left T2 = x.right # 执行旋转 x.right = y y.left = T2 # 更新高度 self.update_height(y) self.update_height(x) return x # 返回新的根节点 # 左旋转(处理右右情况) def rotate_left(self, x): y = x.right T2 = y.left # 执行旋转 y.left = x x.right = T2 # 更新高度 self.update_height(x) self.update_height(y) return y # 返回新的根节点 # 插入节点 def insert(self, key): self.root = self._insert_node(self.root, key) def _insert_node(self, node, key): # 1. 执行标准BST插入 if node is None: return Node(key) if key < node.key: node.left = self._insert_node(node.left, key) elif key > node.key: node.right = self._insert_node(node.right, key) else: # 相同键值不做处理,或根据需求更新节点 return node # 2. 更新节点高度 self.update_height(node) # 3. 获取平衡因子 balance = self.get_balance_factor(node) # 4. 如果节点失衡,进行旋转调整 # 左左情况 - 右旋 if balance > 1 and self.get_balance_factor(node.left) >= 0: return self.rotate_right(node) # 右右情况 - 左旋 if balance < -1 and self.get_balance_factor(node.right) <= 0: return self.rotate_left(node) # 左右情况 - 左右双旋 if balance > 1 and self.get_balance_factor(node.left) < 0: node.left = self.rotate_left(node.left) return self.rotate_right(node) # 右左情况 - 右左双旋 if balance < -1 and self.get_balance_factor(node.right) > 0: node.right = self.rotate_right(node.right) return self.rotate_left(node) # 返回未变化的节点引用 return node # 查找最小值节点 def find_min_node(self, node): current = node while current.left is not None: current = current.left return current # 删除节点 def delete(self, key): self.root = self._delete_node(self.root, key) def _delete_node(self, root, key): # 1. 执行标准BST删除 if root is None: return root if key < root.key: root.left = self._delete_node(root.left, key) elif key > root.key: root.right = self._delete_node(root.right, key) else: # 找到要删除的节点 # 情况1:叶子节点或只有一个子节点 if root.left is None or root.right is None: temp = root.left if root.left is not None else root.right # 没有子节点 if temp is None: root = None else: # 一个子节点 root = temp else: # 情况2:有两个子节点 # 找到右子树的最小节点(中序后继) temp = self.find_min_node(root.right) # 复制中序后继的值到当前节点 root.key = temp.key # 删除中序后继 root.right = self._delete_node(root.right, temp.key) # 如果树只有一个节点,删除后直接返回 if root is None: return root # 2. 更新高度 self.update_height(root) # 3. 获取平衡因子 balance = self.get_balance_factor(root) # 4. 进行旋转操作保持平衡 # 左左情况 if balance > 1 and self.get_balance_factor(root.left) >= 0: return self.rotate_right(root) # 左右情况 if balance > 1 and self.get_balance_factor(root.left) < 0: root.left = self.rotate_left(root.left) return self.rotate_right(root) # 右右情况 if balance < -1 and self.get_balance_factor(root.right) <= 0: return self.rotate_left(root) # 右左情况 if balance < -1 and self.get_balance_factor(root.right) > 0: root.right = self.rotate_right(root.right) return self.rotate_left(root) return root # 查找节点 def search(self, key): return self._search_node(self.root, key) def _search_node(self, root, key): if root is None: return False if key == root.key: return True if key < root.key: return self._search_node(root.left, key) else: return self._search_node(root.right, key) # 中序遍历 def inorder(self): result = [] self._inorder_traversal(self.root, result) return result def _inorder_traversal(self, node, result): if node is not None: self._inorder_traversal(node.left, result) result.append(node.key) self._inorder_traversal(node.right, result)
▼Go复制代码package main import ( "fmt" "math" ) // Node 表示AVL树中的节点 type Node struct { Key int // 节点值 Left *Node // 左子节点 Right *Node // 右子节点 Height int // 节点高度 } // AVLTree 表示AVL树 type AVLTree struct { Root *Node // 根节点 } // NewNode 创建一个新节点 func NewNode(key int) *Node { return &Node{ Key: key, Height: 1, // 新节点高度初始为1 } } // Height 获取节点高度,空节点高度为0 func (t *AVLTree) Height(node *Node) int { if node == nil { return 0 } return node.Height } // GetBalanceFactor 获取节点的平衡因子 func (t *AVLTree) GetBalanceFactor(node *Node) int { if node == nil { return 0 } return t.Height(node.Left) - t.Height(node.Right) } // UpdateHeight 更新节点高度 func (t *AVLTree) UpdateHeight(node *Node) { if node == nil { return } leftHeight := t.Height(node.Left) rightHeight := t.Height(node.Right) node.Height = int(math.Max(float64(leftHeight), float64(rightHeight))) + 1 } // RotateRight 右旋转(处理左左情况) func (t *AVLTree) RotateRight(y *Node) *Node { x := y.Left T2 := x.Right // 执行旋转 x.Right = y y.Left = T2 // 更新高度 t.UpdateHeight(y) t.UpdateHeight(x) return x // 返回新的根节点 } // RotateLeft 左旋转(处理右右情况) func (t *AVLTree) RotateLeft(x *Node) *Node { y := x.Right T2 := y.Left // 执行旋转 y.Left = x x.Right = T2 // 更新高度 t.UpdateHeight(x) t.UpdateHeight(y) return y // 返回新的根节点 } // Insert 插入节点 func (t *AVLTree) Insert(key int) { t.Root = t.InsertNode(t.Root, key) } // InsertNode 插入节点的递归实现 func (t *AVLTree) InsertNode(node *Node, key int) *Node { // 1. 执行标准BST插入 if node == nil { return NewNode(key) } if key < node.Key { node.Left = t.InsertNode(node.Left, key) } else if key > node.Key { node.Right = t.InsertNode(node.Right, key) } else { // 相同键值不做处理,或根据需求更新节点 return node } // 2. 更新节点高度 t.UpdateHeight(node) // 3. 获取平衡因子 balance := t.GetBalanceFactor(node) // 4. 如果节点失衡,进行旋转调整 // 左左情况 - 右旋 if balance > 1 && t.GetBalanceFactor(node.Left) >= 0 { return t.RotateRight(node) } // 右右情况 - 左旋 if balance < -1 && t.GetBalanceFactor(node.Right) <= 0 { return t.RotateLeft(node) } // 左右情况 - 左右双旋 if balance > 1 && t.GetBalanceFactor(node.Left) < 0 { node.Left = t.RotateLeft(node.Left) return t.RotateRight(node) } // 右左情况 - 右左双旋 if balance < -1 && t.GetBalanceFactor(node.Right) > 0 { node.Right = t.RotateRight(node.Right) return t.RotateLeft(node) } // 返回未变化的节点引用 return node } // FindMinNode 查找最小值节点 func (t *AVLTree) FindMinNode(node *Node) *Node { current := node for current != nil && current.Left != nil { current = current.Left } return current } // Delete 删除节点 func (t *AVLTree) Delete(key int) { t.Root = t.DeleteNode(t.Root, key) } // DeleteNode 删除节点的递归实现 func (t *AVLTree) DeleteNode(root *Node, key int) *Node { // 1. 执行标准BST删除 if root == nil { return root } if key < root.Key { root.Left = t.DeleteNode(root.Left, key) } else if key > root.Key { root.Right = t.DeleteNode(root.Right, key) } else { // 找到要删除的节点 // 情况1:叶子节点或只有一个子节点 if root.Left == nil || root.Right == nil { var temp *Node if root.Left != nil { temp = root.Left } else { temp = root.Right } // 没有子节点 if temp == nil { root = nil } else { // 一个子节点 root = temp } } else { // 情况2:有两个子节点 // 找到右子树的最小节点(中序后继) temp := t.FindMinNode(root.Right) // 复制中序后继的值到当前节点 root.Key = temp.Key // 删除中序后继 root.Right = t.DeleteNode(root.Right, temp.Key) } } // 如果树只有一个节点,删除后直接返回 if root == nil { return root } // 2. 更新高度 t.UpdateHeight(root) // 3. 获取平衡因子 balance := t.GetBalanceFactor(root) // 4. 进行旋转操作保持平衡 // 左左情况 if balance > 1 && t.GetBalanceFactor(root.Left) >= 0 { return t.RotateRight(root) } // 左右情况 if balance > 1 && t.GetBalanceFactor(root.Left) < 0 { root.Left = t.RotateLeft(root.Left) return t.RotateRight(root) } // 右右情况 if balance < -1 && t.GetBalanceFactor(root.Right) <= 0 { return t.RotateLeft(root) } // 右左情况 if balance < -1 && t.GetBalanceFactor(root.Right) > 0 { root.Right = t.RotateRight(root.Right) return t.RotateLeft(root) } return root } // Search 查找节点 func (t *AVLTree) Search(key int) bool { return t.SearchNode(t.Root, key) } // SearchNode 查找节点的递归实现 func (t *AVLTree) SearchNode(root *Node, key int) bool { if root == nil { return false } if key == root.Key { return true } if key < root.Key { return t.SearchNode(root.Left, key) } else { return t.SearchNode(root.Right, key) } } // InOrder 中序遍历 func (t *AVLTree) InOrder() []int { result := []int{} t.inOrderTraversal(t.Root, &result) return result } // inOrderTraversal 中序遍历的递归实现 func (t *AVLTree) inOrderTraversal(node *Node, result *[]int) { if node != nil { t.inOrderTraversal(node.Left, result) *result = append(*result, node.Key) t.inOrderTraversal(node.Right, result) } } // 示例使用 func main() { avlTree := AVLTree{} // 插入节点 avlTree.Insert(10) avlTree.Insert(20) avlTree.Insert(30) avlTree.Insert(40) avlTree.Insert(50) avlTree.Insert(25) // 中序遍历 fmt.Println("中序遍历:", avlTree.InOrder()) // 搜索节点 fmt.Println("搜索 30:", avlTree.Search(30)) fmt.Println("搜索 100:", avlTree.Search(100)) // 删除节点 avlTree.Delete(30) fmt.Println("删除 30 后的中序遍历:", avlTree.InOrder()) }
▼C++复制代码#include <iostream> #include <algorithm> #include <vector> /** * AVL树的C++实现 */ class AVLTree { private: // 树节点定义 struct Node { int key; // 节点值 Node* left; // 左子节点 Node* right; // 右子节点 int height; // 节点高度 Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {} }; Node* root; // 根节点 // 获取节点高度,空节点高度为0 int height(Node* node) { if (node == nullptr) { return 0; } return node->height; } // 获取节点的平衡因子 int getBalanceFactor(Node* node) { if (node == nullptr) { return 0; } return height(node->left) - height(node->right); } // 更新节点高度 void updateHeight(Node* node) { if (node == nullptr) { return; } node->height = std::max(height(node->left), height(node->right)) + 1; } // 右旋转(处理左左情况) Node* rotateRight(Node* y) { Node* x = y->left; Node* T2 = x->right; // 执行旋转 x->right = y; y->left = T2; // 更新高度 updateHeight(y); updateHeight(x); return x; // 返回新的根节点 } // 左旋转(处理右右情况) Node* rotateLeft(Node* x) { Node* y = x->right; Node* T2 = y->left; // 执行旋转 y->left = x; x->right = T2; // 更新高度 updateHeight(x); updateHeight(y); return y; // 返回新的根节点 } // 插入节点的递归实现 Node* insertNode(Node* node, int key) { // 1. 执行标准BST插入 if (node == nullptr) { return new Node(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; } // 2. 更新节点高度 updateHeight(node); // 3. 获取平衡因子 int balance = getBalanceFactor(node); // 4. 如果节点失衡,进行旋转调整 // 左左情况 - 右旋 if (balance > 1 && getBalanceFactor(node->left) >= 0) { return rotateRight(node); } // 右右情况 - 左旋 if (balance < -1 && getBalanceFactor(node->right) <= 0) { return rotateLeft(node); } // 左右情况 - 左右双旋 if (balance > 1 && getBalanceFactor(node->left) < 0) { node->left = rotateLeft(node->left); return rotateRight(node); } // 右左情况 - 右左双旋 if (balance < -1 && getBalanceFactor(node->right) > 0) { node->right = rotateRight(node->right); return rotateLeft(node); } // 返回未变化的节点引用 return node; } // 查找最小值节点 Node* findMinNode(Node* node) { Node* current = node; while (current->left != nullptr) { current = current->left; } return current; } // 删除节点的递归实现 Node* deleteNode(Node* root, int key) { // 1. 执行标准BST删除 if (root == nullptr) { return root; } if (key < root->key) { root->left = deleteNode(root->left, key); } else if (key > root->key) { root->right = deleteNode(root->right, key); } else { // 找到要删除的节点 // 情况1:叶子节点或只有一个子节点 if (root->left == nullptr || root->right == nullptr) { Node* temp = root->left ? root->left : root->right; // 没有子节点 if (temp == nullptr) { temp = root; root = nullptr; } else { // 一个子节点 *root = *temp; // 复制非空子节点到当前节点 } delete temp; } else { // 情况2:有两个子节点 // 找到右子树的最小节点(中序后继) Node* temp = findMinNode(root->right); // 复制中序后继的值到当前节点 root->key = temp->key; // 删除中序后继 root->right = deleteNode(root->right, temp->key); } } // 如果树只有一个节点,删除后直接返回 if (root == nullptr) { return root; } // 2. 更新高度 updateHeight(root); // 3. 获取平衡因子 int balance = getBalanceFactor(root); // 4. 进行旋转操作保持平衡 // 左左情况 if (balance > 1 && getBalanceFactor(root->left) >= 0) { return rotateRight(root); } // 左右情况 if (balance > 1 && getBalanceFactor(root->left) < 0) { root->left = rotateLeft(root->left); return rotateRight(root); } // 右右情况 if (balance < -1 && getBalanceFactor(root->right) <= 0) { return rotateLeft(root); } // 右左情况 if (balance < -1 && getBalanceFactor(root->right) > 0) { root->right = rotateRight(root->right); return rotateLeft(root); } return root; } // 查找节点的递归实现 bool searchNode(Node* root, int key) { if (root == nullptr) { return false; } if (key == root->key) { return true; } if (key < root->key) { return searchNode(root->left, key); } else { return searchNode(root->right, key); } } // 中序遍历的递归实现 void inorderTraversal(Node* node, std::vector<int>& result) { if (node != nullptr) { inorderTraversal(node->left, result); result.push_back(node->key); inorderTraversal(node->right, result); } } // 清理树的递归实现 void clear(Node* node) { if (node != nullptr) { clear(node->left); clear(node->right); delete node; } } public: AVLTree() : root(nullptr) {} ~AVLTree() { clear(root); } // 插入节点 void insert(int key) { root = insertNode(root, key); } // 删除节点 void remove(int key) { root = deleteNode(root, key); } // 查找节点 bool search(int key) { return searchNode(root, key); } // 中序遍历 std::vector<int> inorder() { std::vector<int> result; inorderTraversal(root, result); return result; } // 打印中序遍历 void printInorder() { std::vector<int> result = inorder(); for (int val : result) { std::cout << val << " "; } std::cout << std::endl; } }; // 示例使用 int main() { AVLTree tree; // 插入节点 tree.insert(10); tree.insert(20); tree.insert(30); tree.insert(40); tree.insert(50); tree.insert(25); // 中序遍历 std::cout << "中序遍历: "; tree.printInorder(); // 搜索节点 std::cout << "搜索 30: " << (tree.search(30) ? "找到" : "未找到") << std::endl; std::cout << "搜索 100: " << (tree.search(100) ? "找到" : "未找到") << std::endl; // 删除节点 tree.remove(30); std::cout << "删除 30 后的中序遍历: "; tree.printInorder(); return 0; }
AVL树是最早被发明的自平衡二叉搜索树之一,适用于许多需要高效查找和维持数据有序性的场景。
比如内存管理器经常使用AVL树跟踪内存块的分配与释放。
在需要频繁执行范围查询的应用中,AVL树也比较适用,常用于实现区间查询功能。
1)AVL树的平衡因子是如何定义的?平衡因子的有效范围是什么?
2)在AVL树中,当插入节点导致失衡时,需要几种不同类型的旋转操作来维持平衡?它们分别应对什么情况?
测验答案
1)AVL树的平衡因子定义为节点的左子树高度减去右子树高度。在一棵合法的AVL树中,每个节点的平衡因子只能是-1、0或1,表示左右子树高度差不超过1。
2)AVL树中有四种旋转操作:
- 左旋(RR型):处理右子树过重的情况
- 右旋(LL型):处理左子树过重的情况
- 左右旋(LR旋转):先对左子节点进行左旋,再对当前节点进行右旋
- 右左旋(RL旋转):先对右子节点进行右旋,再对当前节点进行左旋
虽然LeetCode上没有直接要求实现AVL树的题目,但以下题目涉及到二叉搜索树和平衡树的概念,可以帮助大家加深理解: