架构训练营第八周总结

1.排序二叉树：每个节点的左边比节点小，右边比节点大，效率可以，但是有可能退化成链表，效率低；

2.平衡二叉（排序）树：节点层级相差不超过 1，通过左旋和右旋保持平衡，但是插入和更新效率会低；

3.红黑（排序）树：

每个节点只有两种颜色：红色和黑色

根节点是黑色的。

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

从根节点到叶子节点，不会出现两个连续的红色节点。

从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。



红黑树 VS 平衡二叉树：红黑树要求没那么严格，所以插入更新效率会比平衡二叉树高，所以一般数据会变化得频繁的情况就使用红黑树。平衡二叉树查询效率高，但是插入更新效率低，谨慎使用。