搜索树

定义

搜索树是一种可以进行插入、搜素、删除等操作的数据结构，可以用作字典或优先级队列。二叉搜索树属于最基本的搜索树。

性质

设x为二叉搜索树的结点，如果y是x左子树的结点，那么y的键值小于等于x的键值。如果z是x的右子树中的结点，那么x的键值小于等于z的键值。

如图所示

当数据进行插入或者删除操作后，所有结点仍然满足上述的性质。

插入

伪代码

insert方法用于在二叉搜索树T中插入新值v，insert 将键值为v，左子树为NIL，右子树为NIL的点z作为实参传入

insert(T,z)
    y=NIL //x的父结点
    x='T的根节点'
    while x!=NIL
        y=x //设置父结点
        if z.key < x.key
            x=x.left
        else
            x=x.right
    z.p=y
    
    if y==NIL //T为空时
         'T的根节点'=z
    else if z.key <y.key
        y.left=z //将z定为y的左子结点
    else
        y.right=z //将z定为y的右子结点

定义

struct Node{
    int key;
    struct Node * parent,*left,*right;
};