算法

一、二叉树(Binary Search Tree)

特性

• 左子树上所有结点的值均小于或等于它的根结点的值
• 右子树上所有结点的值均大于或等于它的根结点的值。
• 左、右子树也分别为二叉排序树。

分析

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

缺陷

容易导致不平衡

二、平衡二叉树

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

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

三、红黑树(Red Black Tree)

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

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

• 节点是红色或者黑色
• 根节点是黑色
• 每个叶子节点都是黑色的空节点(NIL节点)
• 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

有了以上特性可以保证

• 可以保证红黑树的自平衡
• 红黑树从根到叶子的最长路径不会超过最短路径的2倍

旋转和变色

AVL树与红黑树(RB树)的区别与联系

• AVL是严格的平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多
• 红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低开销；
• 所以简单说，查询多选择AVL树，查询更新次数差不多选红黑树
• AVL树顺序插入和删除时有20%左右的性能优势，红黑树随机操作15%左右优势，现实应用当然一般都是随机情况，所以红黑树得到了更广泛的应用 索引为B+树 Hashmap为红黑树

其他数据结构

• 完全平衡二叉树
• 哈希表
• B树
• B+树