数据结构学习笔记

二叉搜索树（BST）

• 二叉搜索树又叫二叉排序树和二叉查找树

• 二叉树左子树所有节点的值都小于根结点值，右子树所有结点的值都大于根结点的值。（左<跟<右）

• 中序遍历（从小到大有序排列）插入结点时，树会退化成线性链表（斜树），导致查询效率下降，时间复杂度退化为O(N)

• 删除左子树和右子树都存在的结点时，可以取左子树的结点最大值或右子树结点的最小值来替换它

平衡二叉树（AVL）

• 它是一个特殊的二叉搜索数（符合二叉搜索数的所有特性，即左<跟<右），每次操作都要检测是否失衡（平衡因子绝对值>1）

• 所有结点（左子树的高度-右子树的高度)绝对值≤1，即平衡因子的绝对值≤1

四种失衡情况

• LL型：当某平衡因子=2（失衡结点），其左子树的结点平衡因子=1（失衡结点左孩），此时需要以失衡结点左孩这个结点作为中心结点，进行右旋，右旋过程中如果存在结点冲突（失衡结点左孩这个结点存在右子树结点（右孩）），则将这个右孩结点变成失衡结点左子树节点

• RR型：当某平衡因子=-2（失衡结点），其右子树的结点平衡因子=-1（失衡结点右孩），此时需要以失衡结点右孩这个结点作为中心结点，进行左旋，左旋过程中如果存在结点冲突（失衡结点右孩这个结点存在左子树结点（左孩）），则将这个左孩结点变成失衡结点右子树节点

• LR型：当某平衡因子=2（失衡结点）,其左子树的结点平衡因子=-1（失衡结点左孩），此时需要先以失衡结点左孩的右子树结点（右孩）作为中心结点，进行左旋，左旋的过程中如果存在冲突节点（右孩这个结点存在左子树结点（右孩的左孩）），则将右孩的左孩变成失衡结点的右子树结点，然后再以失衡结点左孩的右子树结点（右孩）作为中心结点，进行右旋

• RL型：当某平衡因子=-2（失衡结点）,其右子树的结点平衡因子=1（失衡结点右孩），此时需要先以失衡结点右孩的左子树结点（左孩）作为中心结点，进行右旋，右旋的过程中如果存在冲突节点（左孩这个结点存在右子树结点（左孩的右孩）），则将左孩的右孩变成失衡结点的左子树结点，然后再以失衡结点右孩的左子树结点（左孩）作为中心结点，进行左旋

红黑树

• 它是一个自平衡二叉查找树（符合二叉搜索数的所有特性，即左<根<右）

• 每个节点非黑即红，根和叶子（NULL）结点总是黑色

• 不存在连续的两个红色结点

• 从任一结点到它的叶子节点或空子结点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）

• 任一结点左右子树的高度相差不超过2倍