数据结构 ----- 二叉搜索树-育师

BST，AVL，红黑树

共性：

本质都是二叉搜索树，都遵守BST规则，
中序遍历的结果都是升序有序序列，
节点结构都是二叉树节点：数据域+左指针+右指针
基础操作逻辑一致，查找，插入，删除的查找路径一致

区别：

主要在平衡约束强度。普通 BST 不保证平衡；AVL 严格平衡，查找快但增删旋转多；红黑树弱平衡，旋转少，增删性能更好。AVL 和红黑树是在 BST 基础上增加平衡约束，解决普通 BST 最坏退化成链表的缺陷。

二叉搜索树（BST）

核心规则：

左子树所有节点值＜根节点值
右子树所有节点值＞根节点值
左、右子树本身也都是 BST

三大基础操作

1.查找

从根开始比较：小于根去左子树，大于根去右子树，相等找到

平均：O()

最坏:O(n)（有序插入，树退化成一条链表）

TreeNode* search(TreeNode* root, int key) { if (root == nullptr || root->val == key)return root; if (key < root->val) { return search(root->left, key); } return search(root->right, key); }

2.插入

与查找的逻辑一致，新节点一定是叶子节点

TreeNode* insert(TreeNode* root, int val) { if (root == nullptr)return new TreeNode(val); if (val < root->val) { root->left = insert(root->left, val); } else if (val > root->val) { root->right = insert(root->right, val); } return root; }

3.删除

删除（难点，分 3 种情况）

叶子节点：直接删除
只有左孩子 / 只有右孩子：用子节点替换当前节点

左右孩子都存在：两种选择取右子树的最小值（右子树最左节点）替换当前节点，再删掉这个最小节点或者取左子树的最大值（左子树最右节点）替换当前节点，再删掉该节点

TreeNode* remove(TreeNode* &root, int key) { if (root == nullptr)return nullptr; if (key < root->val) { root->left = remove(root->left, key); } else if (key > root->val) { root->right = remove(root->right, key); } else { if (!root->left) { TreeNode* tmp = root->right; delete root; return tmp; } if(!root->right) { TreeNode* tmp = root->left; delete root; return tmp; } TreeNode* minParent =nullptr; TreeNode* cur = getMinAndParent(root->right,minParent); if (minParent == nullptr) root->right = cur->right; else minParent->left = cur->right; cur->left = root->left; cur->right = root->right; delete root; return cur; } return root; }

TreeNode* getMinAndParent(TreeNode* root, TreeNode*& parent) { parent = nullptr; while (root->left != nullptr) { parent = root; // 记录当前节点作为父 root = root->left; } return root; // root停在最左，就是最小值节点 }

关于情况三，关键是要断掉cur与树的联系所以要提前保存cur的父节点，以免出现野指针

AVL（平衡二叉搜索树）

AVL 树 =BST + 平衡约束

平衡因子 BF = 左子树高度 − 右子树高度

AVL 强制要求：每个节点的平衡因子只能是 -1、0、1如果 (|BF|>1) → 树失衡，需要旋转修复

目的：限制树高，保证查找 / 插入 / 删除时间复杂度 O (logn)，不会退化成链表（普通 BST 最坏 O (n)）

结点结构：

struct TreeNode { int val; TreeNode *left; TreeNode *right; int height; // AVL独有：记录以当前节点为根的子树高度 TreeNode(int v) : val(v), left(nullptr), right(nullptr), height(1){} };

四种失衡情况

LL左左（右旋）

在失衡节点的左子树的左孩子处插入，左子树过重

此时为AVL树，插入1

根节点平衡因子为2，失衡此时应该右旋

把失衡节点的左孩子提上来作为新根
左孩子原来的右子树，变成失衡节点的左子树
失衡节点变成其左孩子的右孩子

代码:

AVLNode* Right_Rotate(AVLNode* node) { AVLNode* child = node->leftchild; AVLNode* grandchild = child->rightchild; node->leftchild = grandchild; child->rightchild = node; //更新node和child的高度 Update_Height(node); Update_Height(child); return child;

RR右右（左旋）

失衡节点的右孩子顶替失衡节点的位置：右孩子提升为当前子树根
失衡节点下沉，变成其右孩子的左孩子
T2 搬家：右孩子原来的左子树，拿出来，作为失衡节点的右子树

AVLNode* Left_Rotate(AVLNode* node) { AVLNode* child = node->rightchild; AVLNode* grandchild = child->leftchild; node->rightchild = grandchild; child->leftchild = node; Update_Height(node); Update_Height(child); return child; }

LR（左-右）左子树的右子树过重

先左旋左孩子，再右旋失衡点

RL（右-左）右子树的左子树过重

先右旋右孩子，再左旋失衡点

AVLNode* Rotate(AVLNode* node) { int ba = Get_BalanceFactor(node); if (ba == 2) { int cba = Get_BalanceFactor(node->leftchild); if (cba == 1) { Right_Rotate(node); }//LL单右旋 if (cba ==-1) { //先左旋再右旋 node->leftchild = Left_Rotate(node->rightchild); } } int ba_right = Get_BalanceFactor(node); if(ba_right==- 2) { int cba_right = Get_BalanceFactor(node->rightchild); if (cba_right==-1){ return; }//RR单左旋 if (cba_right ==1) { //先右旋再左旋 } } } //判断先左旋还是先右旋关键是看失衡节点左右孩子的平衡因子