二叉树

前序遍历

根结点在前
先访问根结点，再遍历左子树，最后遍历右子树 根==》左==》右

中序遍历

根结点在中
左==》根==》右

后序遍历

根结点在后
左==》右==》根

二叉树的定义

二叉查找树

平均时间复杂度为O（log n），n为节点个数

红黑树

是一种自平衡的二叉查找树 左旋：逆时针旋转两个节点，让一个节点被其右子节点取代，而该节点成为右子节点的左子节点。
右旋：顺时针旋转两个节点，让一个节点被其左子节点取代，而该节点成为左子节点的右子节点。

HashMap、TreeMap中有用到

B树

每个节点可以存储多个数值元素，又名平衡多路二叉树