BSTAVL红黑树共性本质都是二叉搜索树都遵守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) { //先右旋再左旋 } } } //判断先左旋还是先右旋关键是看失衡节点左右孩子的平衡因子红黑树红黑树的特点红黑树是自平衡二叉搜索树 BST不是靠高度差约束靠 5 条颜色规则限制最长路径不超过最短路径 2 倍保证查找、插入、删除都是 O(logn)性质每个节点要么红色要么黑色。根节点一定是黑色。所有叶子节点NIL 空哨兵节点不是数据节点是黑色。红色节点的两个子节点一定都是黑色不能有连续红节点红不能连红。从任意一个节点到它所有后代 NIL 叶子的所有路径黑色节点数量相等→ 黑高相同。核心思想不强制左右高度差≤1只限制红节点分布。牺牲一点点查找效率大幅减少旋转次数。AVL 插入最多 2 次旋转红黑树删除最多 3 次旋转插入最多 2 次红黑树的插入插入新节点默认为红色然后向上回溯看是否违反了红连红规则叔叔节点是红色父、叔叔变黑祖父变红继续向上回溯。叔叔黑色LR / LL旋转 变色。叔叔黑色RL / RR旋转 变色
BSTAVL红黑树共性本质都是二叉搜索树都遵守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) { //先右旋再左旋 } } } //判断先左旋还是先右旋关键是看失衡节点左右孩子的平衡因子红黑树红黑树的特点红黑树是自平衡二叉搜索树 BST不是靠高度差约束靠 5 条颜色规则限制最长路径不超过最短路径 2 倍保证查找、插入、删除都是 O(logn)性质每个节点要么红色要么黑色。根节点一定是黑色。所有叶子节点NIL 空哨兵节点不是数据节点是黑色。红色节点的两个子节点一定都是黑色不能有连续红节点红不能连红。从任意一个节点到它所有后代 NIL 叶子的所有路径黑色节点数量相等→ 黑高相同。核心思想不强制左右高度差≤1只限制红节点分布。牺牲一点点查找效率大幅减少旋转次数。AVL 插入最多 2 次旋转红黑树删除最多 3 次旋转插入最多 2 次红黑树的插入插入新节点默认为红色然后向上回溯看是否违反了红连红规则叔叔节点是红色父、叔叔变黑祖父变红继续向上回溯。叔叔黑色LR / LL旋转 变色。叔叔黑色RL / RR旋转 变色
