二叉搜索树
树型数据结构的一个重要用途是用作搜索树。二叉搜索树：当前节点值为k，左子树的值都小于k，右子树的值都大于k。
二叉搜索树的中序遍历是按照值增加的顺序进行的
二叉搜索树的一些方法
first()：返回一个包含最小值的节点
last()：返回一个包含最大值的节点
before(p)：返回比节点p的值小的所有节点中值最大的节点（即中序遍历在p之前最后一个被访问的节点）
after(p)：返回比p的值大的所有节点中值最小的节点（即中序遍历在p后的第一个节点）
after方法即中序遍历的下一个结点，参考剑指offer第8题
二叉搜索树的搜索
lc700 二叉搜索树的搜索
如果要搜索的值小于当前节点的值，则往左子树搜索，如果要搜索的值大于当前节点的值，则往右子树搜索
class Solution(object):
def searchBST(self, root, val):
if not root:
return None
if root.val == val:
return root
elif root.val < val:
return Solution().searchBST(root.right,val)
else:
return Solution().searchBST(root.left,val)
二叉搜索树的插入
在二叉树中搜索要插入的值，当递归到空子树时，就用插入的值替代空子树
lc701 二叉搜索树中的插入操作
class Solution(object):
def insertIntoBST(self, root, val):
def dfs(root,val):
if val<root.val:
if root.left:
dfs(root.left,val)
else:
root.left = TreeNode(val)
else:
if root.right:
dfs(root.right,val)
else:
root.right = TreeNode(val)
dfs(root,val)
return root
二叉搜索树的删除
从二叉树中删除一个节点比插入一个新的节点更复杂，因为删除的位置可能在树中的任何地方，而插入总是在搜索路径的最后一个位置。要删除一个节点，首先找到该节点，然后：
1.如果该节点最多有一个子节点，则就用其子节点替换它
2.如果该节点有两个子节点，先找到它的前继节点r，因为它有两个子节点，所以其前继节点即它的左子树最右边的位置。用r节点替代该节点，用r的左子节点替代r原来的位置
lc450 删除二叉搜索树中的节点
AVL树、伸展树和红黑树是基于少量操作对标准二叉搜索树进行扩展去重新调整树并降低树的高度
平衡二叉搜索树
平衡二叉搜索树的主要操作是旋转。在旋转之前，如果x是y的左子树（x<y），则旋转之后，y成为x的右子树。此外，还必须利用被旋转的两个位置之间的值连接子树节点。
旋转修改了常数数量的父子关系，在一个二叉树中实现它用O(1)时间。
AVL树
高度平衡属性：对于T中的每一个位置p，p的孩子的高度最多相差1
任何满足高度平衡属性的二叉搜索树T被称为AVL树。
高度平衡维持的树对数的高度，且带来的一个直接结果是AVL树子树本身就是一棵AVL树。同时也可以保持高度最小。
一棵存有n个节点的AVL树的高度是O(logn)
对于一棵二叉搜索树，如果孩子之间的高度差的绝对值最多为1，则该位置是平衡的，AVL的高度搜索属性相当于每个位置都是平衡的。
AVL树的插入和删除操作类似于二叉搜索树的操作，当因为收到改变的不利影响对每一部分恢复平衡所进行的操作的后期处理是不一样的
插入
在叶子节点p的位置产生了一个新节点，这个操作可能违反了高度平衡属性，然而唯一可能变得不平衡的位置是p的祖先，因为该位置是其子树唯一变化过的位置。
假设z是插入p后变得不平衡的最近的p的祖先，y是z的具有更高高度的孩子，x是y具有更高高度的孩子，通过一次或多次旋转使他们平衡
删除
同样通过旋转恢复平衡，z表示在T中从p向根方向遇到的第一个不平衡位置，y表示z具有更高高度的孩子；如果y的一个孩子比另一个高，令x是较高的孩子，否则，令x是与y在同一边的y的孩子。
但是旋转可能导致中间位置的祖先变得不平衡，所以还要继续在T中寻找不平衡的位置。如果找到，则用旋转来恢复平衡。
伸展树
伸展树在高度上没有一个严格的对数上界，其效率取决于某一位置移动到根的操作（称为伸展），每次在插入、删除或者搜索都要从最底层的位置p开始。直观上讲，会使得被频繁访问的元素更快接近于根，从而减少典型的搜索时间。它对插入、删除、搜索操作保证了对数的运行时间
伸展：已知二叉搜索树的一个节点x，我们通过一系列的重组将x移动到T的根来对x进行伸展。分为zig-zig型（节点x和父节点y都在树的左边或者右边）、zig-zag型（节点x和父节点y一个是左孩子，一个是右孩子）、zig型（没有祖父节点）
何时进行伸展：
1.搜索k时，发现k在位置p，则伸展p。否则，在搜索失败的位置伸展叶子节点
2.插入k时，身材新插入的内部节点k
3.删除k时，在位置p进行伸展，其中p是被移除节点的父节点
（2，4）树*
红黑树
红黑树更新之后，使用O(1)次结构变化来保持平衡
红黑树是一棵带有红色和黑色节点的二叉搜索树，其具有下面的属性：
- 根属性：根节点是黑色的
- 红色属性：红色节点的子节点是黑色的
- 深度属性：具有零个子节点或一个子节点的所有节点都具有相同的黑色深度（黑色祖先节点的数量）
红黑树存储n个条目的高度是O(logn)
操作
搜索
红黑树的搜索算法与标准二叉树中的搜索算法是相同的
插入
特殊情况下，x是T的唯一节点，因此将根着色为黑色。其他情况下，将x着色为红色，但有可能违法红色属性
即x和其父结点都是红色的，但x的祖先z是黑色的，这种情况称为双红色问题
如果y的兄弟姐妹为黑色，则通过重组把父结点变为黑，x节点和祖先节点分别作为父结点的左右子树且为红色
如果y的兄弟姐妹是红色，则重新着色，把y和兄弟姐妹着色为黑色，其父结点z着色为红色，但是双红色问题可能再次出现
删除
