一、树

树（tree）是一种抽象数据类型（ADT），用来模拟具有树状结构性质的数据集合。树有很多种，向上面的一个节点有多余两个的子节点的树，称为多路树，而每个节点最多只能有两个子节点的一种形式称为二叉树。

二、二叉搜索树

如果我们给二叉树加一个额外的条件，就可以得到一种被称作二叉搜索树(binary search tree)的特殊二叉树。左子树要么是空要么所有节点小于根节点，右子树要么是空要么所有节点大于根节点。且左右子树也都是BST。

2.1 查找

• 查找值比当前节点值大，则搜索右子树
• 查找值等于当前节点值，停止搜索（终止条件）
• 查找值小于当前节点值，则搜索左子树

2.2 插入

待插入的节点也需要从根节点开始进行比较，小于根节点则与根节点左子树比较，
反之则与右子树比较，直到左子树为空或右子树为空，则插入到相应为空的位置。

2.3 删除

• 删除没有子节点的节点，只需要改变该节点的父节点引用该节点的值，即将其引用改为 null 即可。
• 删除有一个子节点的节点，我们只需要将其父节点原本指向该节点的引用，改为指向该节点的子节点即可。
• 删除有两个子节点的节点，际上就是要找比删除节点关键值大的节点集合中最小的一个节点，只有这样代替删除节点后才能满足二叉搜索树的特性。

删除其实是挺复杂的，那么其实我们可以不用真正的删除该节点，只需要在Node类中增加一个标识字段isDelete。

2.4 二叉搜索树的特点和缺陷

特点：拥有二分查找的高性能又能拥有链表一样的灵活性
缺陷：极端情况，可能退化成线性链表

三、平衡二叉树AVL树

• 具有二叉查找树的全部特性。
• 每个节点的左子树和右子树的高度差至多等于1。

四、红黑树

太多了懒得抄，直接看有道云笔记
额外想说的：
数据项只能存储在内部结点中（internal node）。我们所指的"叶结点"在其父结点中可能仅仅用一个NULL指针表示，但是将它也看作一个实际的结点有助于描述红黑树的插入与删除算法，叶结点一律为黑色。
插入的节点一定是叶子节点。

参考资料：
B站-小刘讲源码