"""
二叉查找树
- 如果左子树不为空，则左子树上所有节点的值均小于根节点的值。
- 如果右子树不为空，则右子树上所有节点的值均大于根节点的值。
- 左、右子树也都是二叉查找树。
二叉查找树是一种动态树表，其存在形式也不是唯一的，对于特定的数组也可以有多种结构存在，因此其核心功能在于search实现；
插入和删除操作都是在search上进行操作，不需要对整体结构改变太多；
删除操作需要考虑多种情况来进行实现
"""
class BST:
def __init__(self, node_list):
pass
def search(self, node, parent, val):
# 判断和当前节点值的大小关系后，进行迭代判断
if node is None:
return False, node, parent
if node.val == val:
return True, node, parent
if node.val > val:
return self.search(node.left, node, val)
else:
return self.search(node.right, node, val)
def insert(self, val):
# 二叉查找树是一种动态树表，树的结构通常都不是一次直接生成的
flag, n, p = self.search(self.root, self.root, val) # 通过search查找到需要插入的node
if not flag:
new_node = TreeNode(val)
if val > p.val:
p.right = new_node
else:
p.left = new_node
pass
def delete(self, root, val):
"""
存在三种情况：
1. 如果是叶子节点，可以直接删除；
2. 如果节点只有一个子节点，可以将parent的指针指向其子节点；
3. 如果节点有两个子节点，则将其右子树的最小数据代替此节点的数据，并将右子树最小数据节点删除
"""
flag, n, p = self.search(self.root, self.root, val)
if not flag:
return 'error!'
else:
if n.left is None:
if n == p.left:
p.left = n.right
else:
p.right = n.right
del p
elif n.right is None:
if n == p.left:
p.left = n.left
else:
p.right = n.left
del p
else:
pre = n.right
if pre.left is None:
n.val = pre.val
n.right = pre.right
del pre
else:
next = pre.left
while next.left:
pre = next
next = next.left
n.val = next.val
pre.left = next.right
del p
