二叉查找树的性质

二叉查找树的基本操作

1.结构定义

其本质仍是一颗二叉树，结构与普通二叉树相同。

代码实现：

typedef struct Node {
		int key;
  	struct Node *lchild, *rchild;
}Node;

2.创建、销毁

创建与销毁也与普通二叉树相同。

代码实现：

Node *getNewNode(int key) {
	Node *p = (Node *)malloc(sizeof(Node));
	p->key = key;
	p->lchild = p->rchild = NULL;
	return p;
}

void clear (Node *root) {
	if (root == NULL) return;
	clear(root->lchild);
	clear(root->rchild);
	free(root);
	return;
}

3.插入节点

插入的节点一点会作为叶子节点，同时需保持二叉查找树的性质不变，故需找到正确的插入位置。

代码实现：

/*
1.根节点为空则新元素作为根节点，否则将传入参数key与根节点的key比较
2.根节点的值与需插入值进行比较，若等于则直接返回，若小于则进行步骤3，大于则进行步骤4
3.根节点的值小于插入值时，判断当前节点是否存在左孩子，若存在则继续将其左孩子作为参数调用插入方法，不存在则插入为左孩子
4.根节点的值大于插入值时，判断当前节点是否存在右孩子，若存在则继续将其右孩子作为参数调用插入方法，不存在则插入为右孩子
*/
Node *insert(Node *root, int key) {
    if (root == NULL) return getNewNode(key);
    if (root->key == key) return root;
    if (key < root->key) root->lchild = insert(root->lchild, key);
    else root->rchild = insert(root->rchild, key);  
    return root;
}

4.查找节点

查找操作与插入类似，先看当前节点，如果找到了就返回，否则与当前节点比较大小，再根据大小情况，递归的查找左右子节点。

代码实现：

/*
1.若节点未找到返回0，找到返回1
2.当前节点是否为空，为空则返回0
3.当前节点值与查找值比较，相等则返回1，大于则在左子树查找，大于则在右子树查找
*/
int search (Node *root, int val) {
  if (root == NULL) return 0;
  if (root->key == val) return 1;
  if (root->key > val) return search(root->lchild, val);
  else return search(root->rchild, val);
}

5.删除节点

在进行节点删除时，需注意不能改变二叉查找树的基本性质。可分为3种情况：

当待删除节点度为0时，不会改变树的基本性质，故可直接删除；当删除节点的度为1时，将孤儿节点（待删除节点的子节点）挂到待删除节点的父节点即可；当待删除节点度为2时，我们找其前驱节点（其左子树中权值最大的节点）或者后继节点（其右子树中权值最小的节点）与其替换后，转换为度为1的问题。

代码实现：

Node *predecessor(Node *root) {
    Node *temp = root->lchild;
    while (temp->rchild) temp = temp->rchild;
    return temp;
}
Node *erase(Node *root, int key) {
    if (root == NULL) return NULL;
    if (key < root->key) {
        root->lchild = erase(root->lchild, key);
    }
    else if (key > root->key) {
        root->rchild = erase(root->rchild, key);
    }
    else {
        if (root->lchild == NULL || root->rchild == NULL) {
            Node *temp = root->lchild ? root->lchild : root->rchild;
            free(root);
            return temp;
        }
        else {
            Node *temp = predecessor(root);
            root->key = temp->key;
            root->lchild = erase(root->lchild, temp->key);
        }
    }
    return root;
}

总结

二叉查找树本质上还是二叉树，只是多了节点的权值大于左子节点的权值、小于右子节点的权值，我们只要在操作它的同时维护好这一基本性质即可。开篇说到，二叉查找树的最优查找时间复杂度为，最坏情况为，其实这于二叉查找树的树形结构有关，当其各子树分布平衡时其能达到最优时间复杂度，当其分布不均时会退化为链表。这和它的节点插入顺序有关。这听起来很无语，为了解决这一问题，我们有优化其插入对树形结构影响的数据结构，如平衡二叉查找树、红黑树等...

封面： pixabay