集合

什么是二叉树，二叉搜索树？

二叉树，顾名思义，每个节点最多有两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。二叉树每个节点的左子树和右子树也分别满足二叉树的定义。

❒ 二叉树分类
✔ 满二叉树
✔ 完全二叉树
✔ 二叉搜索树(Binary Search Tree，BST)：又名二叉查找树，有序二叉树或者排序二叉树，是二叉树中比较常用的一种类型。
✔ 红黑树(Red Black Tree)：是一种自平衡的二叉搜索树(BST)，之前叫做平衡二叉B树（Symmetric Binary B-Tree）

❒ 什么是二叉树
✔ 每个节点最多有两个子节点，分别是左子节点和右子节点。
✔ 不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。
✔ 二叉树每个节点的左子树和右子树也分别满足二叉树的定义。

❒ 什么是二叉搜索树
✔ 二叉搜索树(Binary Search Tree，BST)又名二叉查找树，有序二叉树。
✔ 在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值而右子树节点的值都大于这个节点的值。
✔ 没有键值相等的节点。
✔ 通常情况下二叉树搜索的时间复杂度为O(log n)。
✔ 退化二叉树（链表）的时间复杂度是O(n)。