二叉排序树的插入、删除

数据结构-二叉搜索树（BST树）

插入一个结点：

• 按左小右大原则选择插入位置，插入的位置一定是叶子

删除一个结点：

• 若删除的结点是叶子结点，直接删除
• 若删除的结点不是叶子结点，只有一个孩子，孩子替代当前结点，删除孩子。
• 若删除的结点不是叶子结点，有两个孩子，中序后继替代当前结点，删除中序后继结点。

二叉平衡树的插入(平衡方式)、删除

数据结构-平衡二叉树（AVL树）

插入一个结点：

1. 第一步 同BST树
2. 若不平衡，要进行平衡操作
   1. LL旋转
   2. RR旋转
   3. LR旋转
   4. RL旋转

删除一个结点：同BST树

堆的初始化、插入、删除

堆排序

初始化一个堆（大顶堆或小顶堆）：

• 从最后一个非终端结点开始，向前依次调整每个非终端结点的子树
• 调整过程可能会破坏下一级的堆，要继续采用上述方法再调整下一级的堆

插入一个结点：