二叉树(Binary Search Tree)

特性

1. 左子树上所有结点的值均小于或等于它的根结点的值

2. 右子树上所有结点的值均大于或等于它的根结点的值。

3. 左、右子树也分别为二叉排序树。

分析

通过查找10可以看出查找方式是二分法的查找思想，查找次数等同于二叉查找树的高度。插入新的节点也是类似的方法，通过一层一层比较找到合适的节点插入

缺陷

容易导致不平衡(所以才有后面的平衡二叉树)

平衡二叉树

• 具有二叉查找树的全部特性

• 每个节点的左子树和右子树的高度差至多等于1
  

红黑树(Red Black Tree)

平衡树是为了解决二叉查找树退化为链表的情况，而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况

红黑树是一种自平衡的二叉查找树，除了符合二叉查找树的基本特性外，还具有以下附加特性:

• 节点是红色或者黑色

• 根节点是黑色

• 每个叶子节点都是黑色的空节点（NIL节点）

• 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

有了以上特性就可以保证:

1. 可以保证红黑树的自平衡

2. 红黑树从根到叶子的最长录几个不会超过最短路径的2倍

红黑树旋转和变色

完全平衡二叉树

哈希表

O(1)时间复杂度

B树

B+树

AVL树与红黑树（RB树）的区别与联系

1. AVL是严格的平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多

2. 红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低开销；

3. 所以简单说，查询多选择AVL树，查询更新次数差不多选红黑树

4. AVL树顺序插入和删除时有20%左右的性能优势，红黑树随机操作15%左右优势，现实应用当然一般都是随机情况，所以红黑树得到了更广泛的应用 索引为B+树 Hashmap为红黑树

我遇到的实际算法题

1. 大数加减乘除算法