二叉搜刮树讲解

1. 二叉搜刮树的概念

二叉搜刮树又称二叉排序树，它大概是一颗空树，大概是具有以下性子的二叉树：
1. 若它的左子树不为空，则左子树上的所有结点的值都小于等于根节点的值。
2. 若它的右子树不为空，则右子树上的所有结点的值都大于等于根节点的值。
3. 它的左右子树也分别为二叉搜刮树。
4. 二叉搜刮树中可以支持插入相等的值，也可以不支持插入相等的值，详细看利用场景定义。

2. 二叉搜刮树的性能分析

最优环境下，二叉搜刮树为完全二叉树(大概接近完全二叉树)，其高度为：log2 N。
最差环境下，二叉搜刮树退化为单支树(大概类似单支)，其高度为：N。
所以综合而言二叉搜刮树增删查改时间复杂度为O(N)。
另外需要阐明的是，二分查找也可以实现O(log2N)级别的查找效率，但是二分查找有两大缺陷：
1. 需要存储在支持下标随机访问的结构中，而且有序。
2. 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一样平常需要挪动数据。
这里也就体现出了平衡二叉搜刮树的代价。

3. 二叉搜刮树的插入

插入的详细过程如下：
1. 树为空，则直接新增结点，赋值给root指针。
2. 树不空，按二叉搜刮树的性子，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。
3. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走也可以往左走，找到空位置，插入新结点。（要留意的是要保持逻辑同等性，插入相等的值不要一会往右走，一会往左走）。
我给出的示例代码是不支持插入相等的值的。

1. bool Insert(const T& key)
2. {
3.         if (_root == nullptr)
4.         {
5.                 _root = new Node(key);
6.                 return true;
7.         }
9.         Node* cur = _root;
10.         Node* parent = nullptr;
12.         while (cur)
13.         {
14.                 if (key > cur->_key)
15.                 {
16.                         parent = cur;
17.                         cur = cur->_right;
18.                 }
19.                 else if (key < cur->_key)
20.                 {
21.                         parent = cur;
22.                         cur = cur->_left;
23.                 }
24.                 else
25.                 {
26.                         return false;
27.                 }
28.         }
30.         cur = new Node(key);
31.         if (key > parent->_key)
32.         {
33.                 parent->_right = cur;
34.         }
35.         else
36.         {
37.                 parent->_left = cur;
38.         }
40.         return true;
41. }

复制代码

4. 二叉搜刮树的查找

1. 从根开始比力，查找x，x比根的值大则往右边走查找，比根的值小则往左边走查找。
2. 最多查找高度次，走到空，还没找到，那么就阐明这个值不存在。
3. 如果不支持插入相等的值，找到x即可返回。
4. 如果支持插入相等的值，意味着有多个x存在，一样平常是要求查找中序的第一个x。如下图，查找3，要找到1的右孩子的那个3返回。

1. bool Find(const T& x)
2. {
3.         Node* cur = _root;
4.         while (cur)
5.         {
6.                 if (x > cur->_key)
7.                 {
8.                         cur = cur->_right;
9.                 }
10.                 else if (x < cur->_key)
11.                 {
12.                         cur = cur->_left;
13.                 }
14.                 else
15.                 {
16.                         return true;
17.                 }
18.         }
19.         return false;
20. }

复制代码

5. 二叉搜刮树的删除

起首查找元素是否在二叉搜刮树中，如果不存在，直接返回false。
如果查找元素存在，则分为以下四种环境分别处理：（假设要删除的结点为N）
1. N的左右孩子均为空。
2. N左孩子为空，右孩子不为空。
3. N右孩子为空，左孩子不为空。
4. N的左右孩子均不为空
对应以上四种环境的解决方案：
1. 把N结点的父亲对应孩子指针指向空，直接删除N结点。（环境1可以当成环境2大概环境3处理，效果是一样的）
2. 把N结点的父亲对应孩子指针指向右孩子，直接删除N结点。
3. 把N结点的父亲对应孩子指针指向左孩子，直接删除N结点。
4. 无法直接删除N结点，因为N的两个孩子无处安放，只能用更换法删除。找N左子树的值最大结点R(最右结点)大概N右子树的值最小结点R(最左结点)替代N，因为这两个结点中恣意一个，放到N的位置，都满足二叉搜刮树的规则。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结点，R结点符合环境2和环境3，可以直接删除。

1. bool Erase(const T& key)
2. {
3.         Node* cur = _root;
4.         Node* parent = nullptr;
5.        
6.         while (cur)
7.         {
8.                 if (key > cur->_key)
9.                 {
10.                         parent = cur;
11.                         cur = cur->_right;
12.                 }
13.                 else if (key < cur->_key)
14.                 {
15.                         parent = cur;
16.                         cur = cur->_left;
17.                 }
18.                 else
19.                 {
20.                         // 开始删除
21.                         if (cur->_left == nullptr)
22.                         {
23.                                 if (cur == _root)
24.                                 {
25.                                         _root = cur->_right;
26.                                 }
27.                                 else
28.                                 {
29.                                         if (cur == parent->_left)
30.                                         {
31.                                                 parent->_left = cur->_right;
32.                                         }
33.                                         else
34.                                         {
35.                                                 parent->_right = cur->_right;
36.                                         }
37.                                 }
38.                                 delete cur;
39.                         }
40.                         else if (cur->_right == nullptr)
41.                         {
42.                                 if (cur == _root)
43.                                 {
44.                                         _root = cur->_left;
45.                                 }
46.                                 else
47.                                 {
48.                                         if (cur == parent->_left)
49.                                         {
50.                                                 parent->_left = cur->_left;
51.                                         }
52.                                         else
53.                                         {
54.                                                 parent->_right = cur->_left;
55.                                         }
56.                                 }
57.                                 delete cur;
58.                         }
59.                         else
60.                         {
61.                                 // 找右子树的最小节点(最左节点)替代
62.                                 Node* replace_parent = cur;
63.                                 Node* replace = cur->_right;
64.                                 while (replace->_left)
65.                                 {
66.                                         replace_parent = replace;
67.                                         replace = replace->_left;
68.                                 }
69.                                 swap(cur->_key, replace->_key);
70.                                 if (replace == replace_parent->_left)
71.                                 {
72.                                         replace_parent->_left = replace->_right;
73.                                 }
74.                                 else
75.                                 {
76.                                         replace_parent->_right = replace->_right;
77.                                 }
78.                                 delete replace;
79.                         }
80.                         return true;
81.                 }
82.         }
83.         return false;
84. }

复制代码

6. 完备的实现代码

1. #include<iostream>
3. using namespace std;
5. template<class T>
6. struct BinarySearchTreeNode
7. {
8.         T _key;
9.         BinarySearchTreeNode<T>* _left;
10.         BinarySearchTreeNode<T>* _right;
12.         BinarySearchTreeNode(const T& key)
13.                 :_key(key)
14.                 ,_left(nullptr)
15.                 ,_right(nullptr)
16.         { }
17. };
19. template<class T>
20. class BSTree
21. {
22.         typedef BinarySearchTreeNode<T> Node;
23. public:
24.         bool Insert(const T& key)
25.         {
26.                 if (_root == nullptr)
27.                 {
28.                         _root = new Node(key);
29.                         return true;
30.                 }
32.                 Node* cur = _root;
33.                 Node* parent = nullptr;
35.                 while (cur)
36.                 {
37.                         if (key > cur->_key)
38.                         {
39.                                 parent = cur;
40.                                 cur = cur->_right;
41.                         }
42.                         else if (key < cur->_key)
43.                         {
44.                                 parent = cur;
45.                                 cur = cur->_left;
46.                         }
47.                         else
48.                         {
49.                                 return false;
50.                         }
51.                 }
53.                 cur = new Node(key);
54.                 if (key > parent->_key)
55.                 {
56.                         parent->_right = cur;
57.                 }
58.                 else
59.                 {
60.                         parent->_left = cur;
61.                 }
63.                 return true;
64.         }
66.         bool Find(const T& x)
67.         {
68.                 Node* cur = _root;
69.                 while (cur)
70.                 {
71.                         if (x > cur->_key)
72.                         {
73.                                 cur = cur->_right;
74.                         }
75.                         else if (x < cur->_key)
76.                         {
77.                                 cur = cur->_left;
78.                         }
79.                         else
80.                         {
81.                                 return true;
82.                         }
83.                 }
84.                 return false;
85.         }
87.         bool Erase(const T& key)
88.         {
89.                 Node* cur = _root;
90.                 Node* parent = nullptr;
91.                
92.                 while (cur)
93.                 {
94.                         if (key > cur->_key)
95.                         {
96.                                 parent = cur;
97.                                 cur = cur->_right;
98.                         }
99.                         else if (key < cur->_key)
100.                         {
101.                                 parent = cur;
102.                                 cur = cur->_left;
103.                         }
104.                         else
105.                         {
106.                                 // 开始删除
107.                                 if (cur->_left == nullptr)
108.                                 {
109.                                         if (cur == _root)
110.                                         {
111.                                                 _root = cur->_right;
112.                                         }
113.                                         else
114.                                         {
115.                                                 if (cur == parent->_left)
116.                                                 {
117.                                                         parent->_left = cur->_right;
118.                                                 }
119.                                                 else
120.                                                 {
121.                                                         parent->_right = cur->_right;
122.                                                 }
123.                                         }
124.                                         delete cur;
125.                                 }
126.                                 else if (cur->_right == nullptr)
127.                                 {
128.                                         if (cur == _root)
129.                                         {
130.                                                 _root = cur->_left;
131.                                         }
132.                                         else
133.                                         {
134.                                                 if (cur == parent->_left)
135.                                                 {
136.                                                         parent->_left = cur->_left;
137.                                                 }
138.                                                 else
139.                                                 {
140.                                                         parent->_right = cur->_left;
141.                                                 }
142.                                         }
143.                                         delete cur;
144.                                 }
145.                                 else
146.                                 {
147.                                         // 找右子树的最小节点(最左节点)替代
148.                                         Node* replace_parent = cur;
149.                                         Node* replace = cur->_right;
150.                                         while (replace->_left)
151.                                         {
152.                                                 replace_parent = replace;
153.                                                 replace = replace->_left;
154.                                         }
155.                                         swap(cur->_key, replace->_key);
156.                                         if (replace == replace_parent->_left)
157.                                         {
158.                                                 replace_parent->_left = replace->_right;
159.                                         }
160.                                         else
161.                                         {
162.                                                 replace_parent->_right = replace->_right;
163.                                         }
164.                                         delete replace;
165.                                 }
166.                                 return true;
167.                         }
168.                 }
169.                 return false;
170.         }
172.         void _InOrder(Node* root)
173.         {
174.                 if (root == nullptr)
175.                 {
176.                         return;
177.                 }
178.                 _InOrder(root->_left);
179.                 cout << root->_key << ' ';
180.                 _InOrder(root->_right);
181.         }
183.         void InOrder()
184.         {
185.                 _InOrder(_root);
186.                 cout << endl;
187.         }
189. private:
190.         Node* _root = nullptr;
191. };
193. int main()
194. {
195.         BSTree<int> tree;
196.         int arr[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
197.         for (auto& e : arr)
198.         {
199.                 tree.Insert(e);
200.         }
201.         tree.InOrder();
203.         cout << tree.Find(10) << endl;
204.         cout << tree.Find(100) << endl;
206.         tree.Erase(10);
207.         tree.Erase(6);
208.         tree.InOrder();
210.         return 0;
211. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。