# 算法

# 一、二叉树(Binary Search Tree)
![](/software-engineer/drawio/Moatkon-BinarySearchTree.drawio.svg)

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

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

## 缺陷
容易导致不平衡

![](/software-engineer/drawio/Moatkon-BinarySearchTreeNoBalance.drawio.svg)

# 二、平衡二叉树
具有二叉查找树的全部特性

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

![](/software-engineer/drawio/Moatkon-BinarySearchTreeBalance.drawio.svg)

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

红黑树是一种自平衡的二叉查找树，除了符合二叉查找树的基本特性外，还具有一下附加特性
- 节点是红色或者黑色
- 根节点是黑色
- 每个叶子节点都是黑色的空节点(NIL节点)
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

**有了以上特性可以保证**
- 可以保证红黑树的自平衡
- 红黑树从根到叶子的最长路径不会超过最短路径的2倍

![](/software-engineer/drawio/Moatkon-RedBlackTree.drawio.svg)
> 旋转和变色

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

# 其他数据结构
- 完全平衡二叉树
- 哈希表
- B树
- B+树