二叉搜索树原理及底层实现_二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子

二叉搜索树BST

概念

二叉搜索树又称二叉排序树，它可以是一棵空树，或者是具有以下性质的二叉树：若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；它的左右子树也分别为二叉搜索树。

即当我们按中序来遍历输出这棵树的节点时，是有序的，按从小到大的顺序。

实现的细节

搜索key的过程Find/FindR

a.从根开始查找，val比根节点值大则往右边走查找，比根节点值小则往左边走查找;
b.最多查找高度次，走到到空，还没找到，说明这个值不存在。

//普通版本--用循环解决
bool Find(const K& key)
{
    Node* cur = _root;
    while (cur)
    {
        if (cur->_key < key)
        {
            cur = cur->_right;
        }
        else if (cur->_key > key)
        {
            cur = cur->_left;
        }
        else
        {
            return true;
        }
    }
    return false;
}

//用递归来解决
public:
bool FindR(const K& key)
{
    return _FindR(_root, key);
}
private:
bool _FindR(Node* root, const K& key)
{
    if (root == nullptr)
        return false;

    if (key > root->_key)
        return _FindR(root->_right, key);
    else if (key < root->_key)
        return _FindR(root->_left, key);
    else
        return true;
}
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

插入key的过程Insert/InsertR

需要考虑以下场景：

a.树为空，则直接新增节点new，赋值给root指针;
b.树不为空，按二叉搜索树性质查找插入位置，即与根节点比较，比根节点的值小，往左查找；比根节点的值大，往右查找，找到该位置后插入新节点。这个过程需要用到2个指针，一个为判断当前值与key孰大孰小的cur指针，一个是保存cur的父节点的parent指针，最终要把key值节点插入在parent的左/右节点。【注意：此处的二叉搜索树无相同值】

bool Insert(const K& key)
{
    //如果根节点为空，直接插入这个值
    if (_root == nullptr)
    {
        _root = new Node(key);
        return true;
    }

    Node* cur = _root;
    Node* parent = nullptr;
    while (cur)
    {
        if (cur->_key == key)
        {
            //如果二叉搜索树中已经有一样的值了，插入失败
            return false;
        }
        else if (key > cur->_key)
        {
            parent = cur;
            //与根节点比较，比根节点的值小，往左走；比根节点的值大，往右走
            cur = cur->_right;
        }
        else
        {
            parent = cur;
            cur = cur->_left;
        }
    }
    cur = new Node(key);
    //与根节点比较，比根节点的值大，就链接在右边
    if (key > parent->_key)
    {
        parent->_right = cur;
    }
    else
    {
        parent->_left = cur;
    }
    return true;
}

public:
	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}
private:
bool _InsertR(Node*& root, const K& key)
	{
		//方式1 bool _InsertR(Node* root, const K& key)
		//if (key > root->_key)
		//{
		//	if (root->_right == nullptr)
		//	{
		//		root->_right = new Node(key);
		//		return true;
		//	}
		//	else
		//		return _InsertR(root->_right, key);
		//}
		//else if (key < root->_key)
		//{
		//	if (root->_left == nullptr)
		//	{
		//		root->_left = new Node(key);
		//		return true;
		//	}
		//	else
		//		return _InsertR(root->_left, key);
		//}
		//else
		//	return false;
		
		//方式2 bool _InsertR(Node*& root, const K& key)
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

		if (key > root->_key)
			return _InsertR(root->_right, key);
		else if (key < root->_key)
			return _InsertR(root->_left, key);
		else
			return false;
	}
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

这里的二叉搜索树无法保证左右平衡。

删除的过程Erase/EraseR

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：

1. 要删除的结点无孩子结点–直接删除，其父节点原来指向它的变成指向空
2. 要删除的结点只有左孩子结点–托孤，让该节点的父节点直接指向该节点的孩子节点
3. 要删除的结点只有右孩子结点–托孤，让该节点的父节点直接指向该节点的孩子节点
4. 要删除的结点有左、右孩子结点–替换，找左子树的最大和右子树的最小

看起来待删除节点的处理方式有4种情况，实际上情况1可以与情况2或者3合并起来，因此真正的删除过程如下：

1. 删除该结点且使被删除节点的父结点指向被删除节点的左孩子结点–直接删除
2. 删除该结点且使被删除节点的父结点指向被删除结点的右孩子结点–直接删除
3. 在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除

//普通版本
bool Erase(const K& key)
{
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
        //与根节点比较，比根节点的值大，往右走；比根节点的值小，往左走
        if (key > cur->_key)
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (key < cur->_key)
        {
            parent = cur;
            cur = cur->_left;
        }
        else
        {
            //能走到这，就说明找到了要删除的这个节点，要删除的节点为cur
            //情况1：左子节点为空，右子节点不为空
            if (cur->_left == nullptr)
            {
                //需要特殊处理根节点，因为根节点无父节点
                if (cur == _root)
                {
                    _root = cur->_right;
                }
                else
                {
                    //cur为parent的左子节点，cur的子节点就得继承parent的左子节点
                    if (parent->_left == cur)
                    {
                        parent->_left = cur->_right;
                    }
                    //cur为parent的右子节点，cur的子节点就得继承parent的右子节点
                    else
                    {
                        parent->_right = cur->_right;
                    }
                }
                delete cur;
            }
            //情况2：左子节点不为空，右子节点为空
            else if (cur->_right == nullptr)
            {
                //需要特殊处理根节点，因为根节点无父节点
                if (cur == _root)
                {
                    _root = cur->_left;
                }
                else
                {
                    //cur为parent的左子节点，cur的子节点就得继承parent的左子节点
                    if (parent->_left == cur)
                    {
                        parent->_left = cur->_left;
                    }
                    //cur为parent的右子节点，cur的子节点就得继承parent的右子节点
                    else
                    {
                        parent->_right = cur->_left;
                    }
                }
                delete cur;
            }
            //情况3：左右子节点均不为空
            else
            {
                //在cur的右子树中寻找中序的第一个结点
                Node* parent = cur;
                Node* minRight = cur->_right;//此处前置条件是cur的左右子树均不为空
                while (minRight->_left)
                {
                    parent = minRight;
                    minRight = minRight->_left;
                }
                //交换cur和minRight的值
                cur->_key = minRight->_key;
                //删除minRight
                if (minRight == parent->_left)
                    parent->_left = minRight->_right;
                else
                    parent->_right = minRight->_right;
                delete minRight;
            }
            return true;
        }
    }
    //走到这，说明没找到
    return false;
}

//递归版本
public:
	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}
private:
	bool _EraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
			return false;

		if (key > root->_key)
		{
			return _EraseR(root->_right, key);
		}
		else if (key < root->_key)
		{
			return _EraseR(root->_left, key);
		}
		else
		{
			Node* del = root;
			//相等就开始删除
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			//情况2：左子节点不为空，右子节点为空
			else if (root->_right == nullptr)
			{				
				root = root->_left;
			}
			//情况3：左右子节点均不为空
			else
			{
				Node* minRight = root->_right;
				while (minRight->left)
				{
					minRight = minRight->left;
				}
				swap(root->_key, minRight->_key);

				// 转换成在子树中去删除节点
				return _EraseR(root->_right, key);
			}
			delete del;

			return true; 
		}
	}
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
137
138
139
140
141
142
143
144
145

中序遍历InOrder

在不暴露根节点_root的情况下（比如写一个函数getroot()等让用户获取），套一层函数接口就直接在类内使用这个_root，实现中序遍历

void InOrder()
{
    _InOrder(_root);
    std::cout << std::endl;
}
private:
void _InOrder(Node* root)
{
    //中序：左根右
    if (root == nullptr) return;

    _InOrder(root->_left);
    std::cout << root->_key << " ";
    _InOrder(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意：二叉搜素树不支持改，对于二叉搜索树而言，仅仅修改对应节点的值，极有可能破坏原结构，所以改=删除+插入

构造函数、拷贝构造函数、赋值构造函数、析构函数

public:
	BSTree()
		:_root(nullptr)
	{}

	BSTree(const BSTree<K>& t)
	{
		_root = Copy(t._root);
	}
	
	BSTree<K>& operator=(BSTree<K> t)
	{
		swap(_root, t._root);
		return *this;
	}

	~BSTree()
	{
		Destory(_root);
		_root = nullptr;
	}
private:
	void Destory(Node* root)
	{
		if (root == nullptr)
			return;
		//按后序来删除
		Destory(root->_left);
		Destory(root->_right);
		delete root;
	}

	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		//前序遍历，再递归拷贝
		Node* newnode = new Node(root->_key);
		newnode->_left = Copy(root->_left);
		newnode->_right = Copy(root->_right);
		return newnode;
	}
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

应用场景

K模型–判断某个key在不在的场景；KV模型–通过key查找或修改value

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。其他场景：检查单词拼写是否正确/车库出入系统/宿舍楼门禁系统

2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：

比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。其他场景：英汉互译/学号学生对应

性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

• 最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：$lo{g}_{2}N$
• 最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：$\frac{N}{2}$

但是如果退化成单支树，二叉搜索树的性能就很差，后续引入红黑树和AVL树来解决。