二叉树是很重要的数据结构，今次的任务是复习一下搜索二叉树和红黑树~主要对应《算法导论》中的《二叉搜索树》和《红黑树》两章。这里的搜索二叉树不是B树，所以插入操作时不需要进行专门的旋转操作。
二叉搜索树
二叉搜索树性质
二叉搜索树满足的性质：
如果y是x左子树的一个节点，那么y.key$\leq$x.key。如果y是x右子树的一个节点，那么$y.key \geq x.key$。
遍历顺序
先序遍历、中序遍历和后序遍历，遍历方法都是使用递归思想，如先序遍历“先左子树先序遍历，再根节点，再右子树先序遍历”的递归。
查询
查询二叉搜索树的方法是：对于每个遇到的节点$x$，比较关键字$k$与$x.key$，如果$k<x.key$，那么就查找左子树，否则查找右子树。直到找到元素或发现元素不存在。
递归版本：
class TreeNode:
left_node = None
right_node = None
value = None
def __init__(self, value):
self.value = value
def search(self, value):
if self.value is None:
return False
if self.value == value:
return True
if self.value > value and self.left_node is not None:
return self.left_node.search(value)
if self.value < value and self.right_node is not None:
return self.right_node.search(value)
return False
循环版本：
class TreeNode:
left_node = None
right_node = None
value = None
parent = None
def __init__(self, value):
self.value = value
def search_iter(node, value):
while node is not None and value != node.value:
if value < node.value:
node = node.left_node
else:
node = node.right_node
return node is not None and value == node.value
插入数据
插入数据会带来二叉树的结构变化，由于本小结讨论的不是B树，所以不需要考虑平衡性，也就只需要找到可以放置的位置并添加即可。
def insert(root: TreeNode, node: TreeNode):
curr = root
while curr is not None:
p = curr
if curr.value < node.value:
curr = curr.right_node
else:
curr = curr.left_node
node.parent = p
if p.value < node.value:
p.right_node = node
else:
p.left_node = node
删除
由于要维护搜索二叉树的性质，从中删除一个节点z分成三种情况：
- z没有孩子节点，那么可以直接删除
- z只有一个孩子节点，那么可以直接把这个孩子节点提升到原来的位置
- z有两个孩子节点，那么就需要找z的后继节点(中序遍历中紧随其后的节点)y，并让y占据z的位置。z的左右子树变成y的左右子树。
def delete(node: TreeNode):
if node.right_node is None and node.left_node is None:
transplant(node, None)
if node.left_node is None:
transplant(node,node.right_node)
elif node.right_node is None:
transplant(node,node.left_node)
else:
y = tree_minimum(node.right_node) #寻找到后继节点——右子树最小的节点
if y.parent != node:
y.left_node = node.left_node
y.right_node.parent = y
transplant(y, y.right_node);
y.left_node = node.left_node
y.left_node.parent = y
transplant(node,y)
def tree_minimum(node: TreeNode):
y = node
while node.left_node is not None:
y = node
node = node.left_node
return y
红黑树
红黑树性质
红黑树是许多平衡搜索树中的一种，可以保证在最坏情况下基本动态集合操作的时间复杂度是$O(lgn)$。 红黑树的满足的性质：
- 每个节点是黑色或者红色的
- 每个叶节点是黑色的
- 如果一个节点是黑色的，那么他的两个子节点都是红色的
- 对每个结点，从该节点到其所有后代叶节点的简单路径上都包含相同数目的黑色结点。
由于红黑树在二叉搜索树的基础上还需要维护树的平衡，所以需要有“旋转”这样的操作。
树旋转的操作转换如图：
插入操作
红黑树在插入新元素时，先按照搜索二叉树的方式将元素放在相应位置。为了满足性质4，先将此元素标记为红色。这时可能依然违反其它的红黑树性质，因此需要对节点重新着色并旋转。
….啊，好烦，不想写代码了，找好实习再更新红黑树这一章吧。
