二叉排序树

二叉排序树BST，又叫二叉搜索树
或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

二分查找，时间log2n
有前序遍历，根、左、右的顺序访问遍历每个结点
中序遍历，左跟右顺序
后序遍历，左右跟顺序

旋转

红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。

左旋，就是把节点变成左孩子节点，原来的右孩子节点变成父节点

右旋，就是把节点变成右孩子节点，原来的左孩子节点变成父节点
y
x \
/ \ --(右旋)–> x
y z
z
左旋 和 右旋 是相对的两个概念，它们是对称的。无论是左旋还是右旋，被旋转的树，在旋转前是二叉查找树，并且旋转之后仍然是一颗二叉查找树。

优化方式有
Size Balanced Tree(SBT)
AVL树
红黑树
Treap(Tree+Heap)
这些均可以使查找树的高度为O(log(n))