算法相关备忘录

最大堆与最小堆

二叉查找树、平衡二叉树(AVL)与红黑树

二叉查找树:二叉查找树（Binary Search Tree）和二叉排序树（Binary Sort Tree）都是一样的。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；左、右子树也分别为二叉排序树；没有键值相等的节点（no duplicate nodes）。

因为一棵由n个结点随机构造的二叉查找树的高度为lgn，所以顺理成章，二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后，则这些操作最坏情况运行时间为O(n)。

平衡二叉树：AVL树是根据它的发明者G. M. Adelson-Velskii和E. M. Landis命名的。AVL树本质上还是一棵二叉搜索树，它的特点是：

本身首先是一棵二叉查找树。带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

红黑树：虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。
算法导论里是这样定义一棵红黑树的：

• 每个结点或是红色的，或是黑色的
• 根节点是黑色的每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
• 一个结点是红的，那么它的两个儿子都是黑的。
• 任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

B+树与B-树

动态规划算法——从斐波那契数列出发

拒绝遗忘：高效的动态规划算法