二叉搜索树

发表于 | 本文阅读数 次

顾名思义，二叉搜索树是以一棵二叉树来组织的，这样的一棵树可以用一个链表结构来表示，每个节点除了data还有left、right、parent，分别指向节点的左孩子，右孩子和父节点。如果对应的节点不存在则指向NIL节点。（因为最简单的二叉搜索树中的NIL节点里并没有有用信息，所以在实现时简单的指向NULL也是可以的，本文中就会这么实现）

二叉搜索树的性质

  1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
  2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
  3. 它的左右子树也分别是二叉搜索树

二叉树的常用操作

二叉树的查找

Find操作

若根节点不为空，则：

  1. 如果要查找的值与根节点的值相同，即要查找data==根节点data，则返回true;
  2. 如果要查找的值比根节点的值小，即要查找data<根节点data，则在其左子树进行查找
  3. 如果要查找的值比根节点的值大，即要查找data>根节点data，则在其右子树进行查找

二叉树的插入

  • 树为空，则直接进行插入

    Insert操作

  • 树不空，按二叉搜索树性质查找插入位置，插入新节点

    Insert操作

    1.按照二叉树的性质，先找到插入节点的位置

    ​ root->5,5<10,root = root->right,parent = root;

    ​ root->7,7<10,root = root->right,parent = root;

    ​ root->8,8<10,root = root->right,parent = root;

    ​ root->9,9<10,root = root->right,parnet = root;

    2.插入新节点

    二叉树的删除

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

    1
    2
    3
    4
    a. 要删除的结点无孩子结点
    b. 要删除的结点只有左孩子结点
    c. 要删除的结点只有右孩子结点
    d. 要删除的结点有左、右孩子结点

    看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：
    情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点
    情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
    情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，
    再来处理该结点的删除操作

二叉树的实现

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
#pragma once
#include<iostream>
#include<vector>
using namespace std;

template<class T>
struct BSTNode{
	T _data;
	BSTNode<T>* _pLeft;
	BSTNode<T>* _pRight;

	BSTNode(const T& data)
		:_data(data)
		,_pLeft(nullptr)
		,_pRight(nullptr)
	{}
};

template<class T>
class BSTree{
	typedef BSTNode<T> Node;
	typedef Node* PNode;
private:
	PNode _pRoot;

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

	~BSTree()
	{
		_Destroy(_pRoot);
	}

	bool Insert(const T& data)
	{
		if(nullptr == _pRoot){
			_pRoot = new Node(data);
			return true;
		}
		//非空则先找到应插入的位置
		PNode pParent = nullptr;
		PNode pCur = _pRoot;  //记录一下pCur的双亲位置
		while(pCur){
			pParent = pCur;
			if(data < pCur->_data)
				pCur = pCur->_pLeft;
			else if(data > pCur->_data)
				pCur = pCur->_pRight;
			else
				return true;
		}
		//插入节点
		pCur = new Node(data);
		if(data < pParent->_data)
			pParent->_pLeft = pCur;
		else
			pParent->_pRight = pCur;
		return true;
	}

	bool Erase(const T& data)
	{
		//找待删除节点的位置
		PNode pCur = _pRoot;
		PNode pParent = nullptr;
		while(pCur)
		{
			//pParent = pCur;    不能放在这里，这里时能找到待删除节点，但是不能记录下双亲的位置
			if(data == pCur->_data)
				break;
			else if(data < pCur->_data)
			{
				pParent = pCur;
				pCur = pCur->_pLeft;
			}
			else
			{
				pParent = pCur;
				pCur = pCur->_pRight;
			}
		}
		if(nullptr == pCur)			//没有找到
			return false;

		//分情况删除节点：
		//1.叶子节点||只有右孩子，则左孩子为空—— pParnet->right = pCur->right;（为双亲的右孩子） 或者 pParent->left = pCur->right（为双亲的左孩子）;(待删除节点为非根节点)  为根节点则更新pRoot然后直接删除节点即可
		//2.只有左孩子
		//3.左右孩子均存在
		if(nullptr == pCur->_pLeft)   //情况1
		{
			if(_pRoot == pCur)
				_pRoot = pCur->_pRight;
			else
			{
				if(pCur == pParent->_pLeft)
					pParent->_pLeft = pCur->_pRight;
				else
					pParent->_pRight = pCur->_pRight;
			}
		}

		else if(nullptr == pCur->_pRight)  //情况2
		{
			if(pCur == _pRoot)
				_pRoot = pCur->_pLeft;
			else
			{
				if(pCur == pParent->_pLeft)
					pParent->_pLeft = pCur->_pLeft;
				else
					pParent->_pRight = pCur->_pLeft;
			}
		}
		else
		{
			//左右孩子均存在---不能直接删除，找一个替代节点
			//可以在左子树中找：左子树中最右侧节点
			//也可以在右子树中找：右子树中最左侧节点
			PNode pFirstOfIn = pCur->_pRight;
			PNode pParent = pCur;
			while(pFirstOfIn->_pLeft)
			{
				pParent = pFirstOfIn;
				pFirstOfIn = pFirstOfIn->_pLeft;
			}//找到右子树的最左侧节点,替代节点，一定没有左孩子，可能有右孩子

			pCur->_data = pFirstOfIn->_data;
			//删除替代节点
			if(pFirstOfIn == pParent->_pLeft)
				pParent->_pLeft = pFirstOfIn->_pRight;
			else
				pParent->_pRight = pFirstOfIn->_pRight;
			pCur = pFirstOfIn;
		}
		delete pCur;
		return true;
	}

	void Inorder()
	{
		_InOrder(_pRoot);
	}

	PNode Find(const T& data)
	{
		PNode pCur = _pRoot;
		while (pCur)
		{
			if(data < pCur->_data)
				pCur = pCur->_pLeft;
			else if(data > pCur->_data)
				pCur = pCur->_pRight;
			else
				return pCur;
		}
		return nullptr;
	}

private:
	void _InOrder(PNode _pRoot)  //中序遍历
	{
		if (_pRoot)
			{
				_InOrder(_pRoot->_pLeft);
				cout << _pRoot->_data << " ";
				_InOrder(_pRoot->_pRight);
			}
	}

	void _Destroy(PNode& pRoot)
	{
		if (pRoot)  //后序销毁
		{
			_Destroy(pRoot->_pLeft);
			_Destroy(pRoot->_pRight);
			delete pRoot;
			pRoot = nullptr;
		}
		
	}
};


void TestBSTree()
{
	int a[] = {5,3,4,1,7,8,2,6,0,9};
	BSTree<int> t;
	for(auto e : a)
		t.Insert(e);

	t.Inorder();

	BSTNode<int>* pNode = t.Find(0);
	if(pNode)
		cout << "Yes"<<endl;
	else
		cout << "No"<<endl;

	t.Erase(6);
	t.Inorder();
	cout <<endl;
	t.Erase(8);
	t.Inorder();
	cout <<endl;
	t.Erase(5);
	t.Inorder();
}

二叉树的性能分析

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

完全二叉树

右单支树

也就是说：

最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log

最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2

0%