二叉查找树(BST)

缘起

从现在开始，我们将讨论的重点将逐步转入查找技术。介绍各种精妙的查找结构——主要分成两类结构

  1. 查找树
  2. hash

查找树涉及比较，所以一般复杂度性能的上限由logn所制. 而hash不基于比较，而基于桶排序思想, 所以hash的性能能到线性.

对于计算机而言，查找是很重要的一种结构诶~ 你想想在海量信息爆炸的年代, 查找有多重要吧~

分析

查找树的脉络如下

即分为二路查找和多路查找. BST以及它的衍生品——AVL、splay、红黑都是平衡二路查找，所谓平衡确切讲就是不论数据有多么倾斜, 都能在插入的时候维护其高度在logn的水平. 而红黑的衍生就可以得到多路查找的B树(以及B+树)以及kd树. 前者是数据库索引实现的重要基石（例如mysql的数据库引擎），后者是地图搜索的重要基石.

所以无论如何，我们从最简单的二叉搜索树（BST）入手. 完成对查找树的探索.

二叉排序树（Binary Sort Tree）也有的书翻译成二叉查找树（Binary Search Tree），之所以带排序二字是因为只需要中序遍历该树就能从小到大输出树中的元素，排序的时间复杂度是O(NlogN)的

左小右大，BST中元素彼此严格不相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996)
//#define LOCAL
using namespace std;

typedef struct BiTreeNode
{
	int data;
	BiTreeNode *lc, *rc;
	BiTreeNode(int data):data(data),lc(NULL),rc(NULL){}

} BiTreeNode, *BiTree;

// 递归版本的搜索, 返回指向BST上节点的指针, 如果没找到的话, 返回NULL  不会因为没有就新增的, 但是下面的search重载会"没有就新增"
BiTree search(BiTreeNode *root, int key)
{
	if (root == NULL) return NULL;
	return root->data == key? root:(key < root->data? search(root->lc, key):search(root->rc, key));
}


// 非递归版本的搜索, 在BST root 上搜索 key, 返回指向BST上节点的指针 如果找到了就返回true，没找到就插入并返回false, 不论哪种情况, ret都指向节点
bool search(BiTree root, int key, BiTree &ret)
{
	BiTreeNode *p = root, *father = NULL;
	while(p && p->data != key)
	{
		father = p; // 记录父指针
		key < p->data?p =p->lc:p=p->rc; // p进一步下探
	}
	if (!p) // 如果没找到, 就新建节点并插入
	{
		BiTree newNode = new BiTreeNode(key);
		key < father->data? father->lc = newNode : father->rc = newNode;
		ret = newNode;
		return false;
	}
	else
	{
		ret = p;
		return true;// 如果找到了
	}
}

bool insert(BiTree root, int key) // 往root中插入节点key
{
	BiTree newNode;
	return search(root, key, newNode); // p指向新插入的节点, 注意, 如果已经在BST中存在等于key的节点, 则插入失败, 返回false.
}

void free(BiTree &root) // 释放树
{
	if (root)
	{
		free(root->lc);
		free(root->rc);
		delete root;
		root = NULL;
	}
}

bool delKey(BiTree &node) // 删除节点node, 注意，为什么这里可以不用考虑node的父节点, 这是因为你要看看本函数的调用——是引用传递（入参是引用）, 就拿没有右子树只有左子树的情形来讲, 入参是某个节点的左孩子或者右孩子指针(以左孩子为例), 则 node = node->lc; 就变成了 xxx->lc = xxx->lc->lc ，你看, 这不就接上了吗? 注意, 引用传递入参是关键, 如果不是引用传递入参的话, 程序的逻辑就是错误的
{
	BiTree p = NULL,q = NULL;
	if (!node->lc&&!node->rc) free(node); // 叶子节点, 直接释放
	else if (!node->lc && node->rc) // 没有左子树，只有右子树
	{
		p = node; // 临时记录一下, 因为node马上要变
		node = node->rc;
		delete p; // 释放原本的node
		p = NULL;
	}
	else if (node->lc && !node->rc) // 没有右子树，只有左子树
	{
		p = node;
		node = node->lc;
		delete p;
		p = NULL;
	}
	else // node既有左子树，又有右子树, 这是最复杂的情形
	{
		p = node; // 临时记一下
		q = node->rc; // node的右孩子， 注意, 这是存在的, 因为node存在左右子树
		while(q->lc)
		{
			p=q;
			q=q->lc; // 不断飞奔到node的右孩子的极左节点上去
		}
		node->data = q->data; // node 使用q顶替
		if (p==node) node->rc = q->rc;// 如果压根上面的while循环没跑， 亦即node的右孩子没有左孩子, 则只需要将q顶替node即可
		else p->lc = q->rc;// 说明上面while循环跑了, q已经变成了node的右孩子的极左,p 是q的父节点, 此时将node用q顶替, p的左子树变成q的右子树（注意, q已经没有左子树了）
		delete q; // 释放q节点(q是按中序p的后继)
		q = NULL;
	}
	return true;
}

bool del( BiTree &root, int key) // 删除BST root上的key
{
	if (!root) return false; // 没找到, 删除失败
	if (root->data == key) return delKey(root);  // 如果找到了要删除的节点
	else if (key < root->data) return del(root->lc, key); // 跑左子树上删除节点
	else return del(root->rc, key); // 跑右子树上删除节点
}



int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	BiTree root = new BiTreeNode(12);
	insert(root,53);
	insert(root,24);
	insert(root,3);
	insert(root,61);
	insert(root,37);
	insert(root,78);
	insert(root,90);
	insert(root,45);
	insert(root,100);

	cout << (search(root, 12)?"找到了12":"没找到12") << endl;
	cout << (search(root, 35)?"找到了35":"没找到35") << endl;
	cout << (search(root, 37)?"找到了37":"没找到37") << endl;

	if (!del(root,12)) puts("没找到12, 删除失败!");
	if (!del(root,73))  puts("没找到73, 删除失败!");
	if (!del(root,37))  puts("没找到37, 删除失败!");
	if (!del(root,67))  puts("没找到67, 删除失败!");
	if (!del(root,3))  puts("没找到3, 删除失败!");

	return 0;
}

关于上面BST删除节点的算法可以参见下图:

因为BST是按中序遍历就是排好序的. 所以q是node的后继, 所以node要被删除的话, 就应该使用q来顶替才是合理的. 其实对于其他的——有左孩子没右孩子、没左孩子有右孩子的情形, 也是使用后继来顶替的.