二分搜索树
二叉搜索树wiki定义
二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
复杂度
| 算法 | 平均 | 最差 |
|---|---|---|
| 空间 | O(n) | O(n) |
| 搜索 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
应用
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。
二叉查找树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉查找树的存储结构。中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以透过建构一棵二叉查找树变成一个有序序列，建构树的过程即为对无序序列进行查找的过程。
每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，期望O(log n)，最坏O(n)（数列有序，树退化成线性表）。
虽然二叉查找树的最坏效率是O(n)，但它支持动态查询，且有很多改进版的二叉查找树可以使树高为O(log n)，从而将最坏效率降至O(log n)，如AVL树、红黑树等。
操作
遍历
二分搜索树是一种极具递归性质的树,需要掌握下面四种遍历算法:
层次遍历、前序遍历、中序遍历、后序遍历。
层次遍历很简单，就是根据每层的节点从左到右访问下来
前中后序遍历三种方法的区别是对于根节点的访问顺序上面。每个节点都是各自子树的根节点（叶子节点可以看做孩子节点为NULL），对于这些根节点的访问顺序分别是第1\2\3个访问。
前序遍历: 每次对根节点优先访问，用途可以是输出某个文件夹下所有文件名称(可以有子文件夹)
中序遍历：当树中存放的值为可比较的时，遍历的结果将会有序。
后序遍历：优先访问最底下的孩子节点，也就是在释放二叉树的节点内存时候可以使用得到。
添加和删除
添加操作简而言之就是从根节点开始递归到底,找到相应位置插入即可
删除操作比较复杂,首先需要判断被删除节点是否有左孩子或者右孩子，如果有就只需要将孩子节点顶替被删节点在其父节点中的位置即可。
如果同时有左右孩子就需要在删除前，找到最接近被删节点值的节点来顶替被删节点的位置.我们用被删节点的左子树中最大值来顶替被删节点的位置和用右子树中最小值来顶替被删节点的位置是一样的，这两者都不会改变中序遍历的顺序。
通过用复杂的删除操作、添加操作来保持二分搜索树中节点的排序规则，可以保证二分搜索树的性质不变。
代码实现
下面是C++代码实现
//BST.hpp
# include <iostream>
# include <string>
# include <stack>
# include <queue>
# include <time.h>
using namespace std;
template <typename T> class BST;
template <class T>
class Node {
public:
Node(T e)
{
this->e = e;
left = NULL;
right - NULL;
}
inline T getElement() { return e; }
friend class BST<T>;
private:
T e;
Node<T>* left;
Node<T>* right;
};
template <class T>
class BST
{
public:
BST()
{
root = NULL;
size = 0;
}
inline int Size()
{
return size;
}
void add(T e) //向二分搜索树添加新的元素e
{
/*第一版
if(root==NULL)// 特殊处理
{
root=new Node<T>(e);
size++;
}else
add(root,e);*/
/*第二版*/
root = add(root, e);
}
bool contains(T e)
{
return contains(root, e);
}
void preOrder()
{
preOrder(root);
}
void preOrderNR()
{
stack<Node<T>*> stack ;
stack.push(root);
while (!stack.empty())
{
Node<T>* cur= stack.top();;
stack.pop();
cout << cur->e << " ";
if(cur->left!=NULL)
stack.push(cur->left);
if(cur->right!=NULL)
stack.push(cur->right);
}
}
void inOrder()
{
inOrder(root);
}
void postOrder() //应用:内存释放方面,先将孩子节点的内存都释放干净，再释放根节点
{
postOrder(root);
}
//层次遍历(广度优先遍历)
void levelOrder()
{
queue<Node<T>*> q;
q.push(root);
while (!q.empty())
{
Node<T>* cur = q.front();
q.pop();
cout << cur->e << " ";
if (cur->left != NULL)
{
q.push(cur->left);
}
if (cur->right != NULL)
q.push(cur->right);
}
}
T minElement()
{
if (!size)
throw "BST is empty";
return minElement(root)->e;
}
T maxElement()
{
if (!size)
throw "BST is empty";
maxElement(root)->e;
}
string toString()
{
string val;
generateBSTString(root, 0, val);
return val;
}
T removeMin()
{
T val = minElement();
root = removeMin(root);
return val;
}
T removeMax()
{
T val = maxElement();
root = removeMax(root);
return val;
}
void remove(T val)
{
root=remove(root, val);
}
private:
//第一版
/*
void add(Node<T>* root,T e)//以Node为根的二分搜索树插入元素e 递归
{
if(e==root.e)
return ;
else if(e<root.e&&root.left==NULL)
{
root.left=new Node<T>(e);
size++;
return ;
}else if(e>root.e&&root.right==NULL)
{
root.right=new Node<T>(e);
size++;
return ;
}
if(e<root.e)
add(root.left,e);
else
add(root.right,e);
}*/
//第二版 相等的时候返回回去
Node<T>* add(Node <T>* node, T e)
{
if (node == NULL)
{
size++;
return new Node<T>(e);
}
if (e < node->e)
node->left = add(node->left, e);
else if(e>node->e)
node->right = add(node->right, e);
return node;
}
bool contains(Node <T>* node, T e)
{
if (node == NULL)
return false;
if (node->e == e)
return true;
else if (node->e < e)
return contains(node->left, e);
else
return contains(node->right, e);
}
void preOrder(Node <T>* node)
{
if (node == NULL)
return;
cout << node->e<<" ";
preOrder(node->left);
preOrder(node->right);
}
void inOrder(Node<T>* node)
{
if (node == NULL)
return;
inOrder(node->left);
cout << node->e << " ";
inOrder(node->right);
}
void postOrder(Node<T>* node)
{
if (node == NULL)
return;
postOrder(node->left);
postOrder(node->right);
cout << node->e << " ";
}
//打印输出函数
void generateBSTString(Node<T>* node, int depth, string& str)
{
if (node == NULL)
{
str += generateDepthString(depth) + "null\n";
return;
}
str =str+ generateDepthString(depth) + to_string(node->e) + "\n";
generateBSTString(node->left, depth + 1, str);
generateBSTString(node->right, depth + 1, str);
}
string generateDepthString(int depth)
{
string str;
for (int i = 0; i < depth; i++)
str += "--";
return str;
}
Node<T>* minElement(Node<T>*node)
{
if (node->left == NULL)
return node;
return minElement(node->left);
}
Node<T>* maxElement(Node<T>* node)
{
if (node->right == NULL)
return node;
return minElement(node->right);
}
//删除以node为根的二分搜索树中的最小节点
//返回删除节点后新的二分搜索树的根
Node<T>* removeMin(Node<T> *node)
{
if (node->left == NULL)
{
Node<T>* rightNode = node->right;
node->right = NULL;
delete node;
size--;
return rightNode;
}
node->left=removeMin(node->left);
return node;
}
Node<T> * removeMax(Node<T> *node)
{
if (node->right == NULL) //当前节点为最大值
{
Node* leftNode = node->left;
node->left = NULL;
delete node;
size--;
return leftNode;
}
node->right = removeMax(node->right);
return node;
}
//任意删除节点
Node<T>* remove(Node<T>* node, T e)
{
if (node == NULL)
return NULL;
if (e < node->e)
{
node->left=remove(node->left,e);
return node;
}
else if (e > node->e)
{
node->right = remove(node->right, e);
return node;
}
else
{
if (node->left == NULL)
{
Node<T>* rightNode = node->right;
node->right = NULL;
delete node;
size--;
return rightNode;
}
if (node->right == NULL)
{
Node<T>* leftNode = node->left;
node->left = NULL;
delete node;
size--;
return leftNode;
}
Node<T>* successor = new Node<T>(*minElement(node->right);
successor->right = removeMin(node->right);
successor->left = node->left;
node->left = NULL;
node->right = NULL;
delete node;
return successor;
}
}
private:
Node<T>* root;
int size;
};基于二分搜索树的集合(set)
template <class T>
class Set
{
public:
virtual void add(T e) = 0;
virtual void remove(T e) = 0;
virtual bool contains(T e) = 0;
virtual int size() = 0;
virtual bool empty() = 0;
};
template <class T>
class BSTSet:public Set
{
public:
virtual void add(T e) {
bst.add(e);
}
virtual void remove(T e)
{
bst.remove(e);
}
virtual bool contains(T e)
{
return bst.contains(e);
}
virtual int size()
{
return bst.Size();
}
virtual bool empty()
{
return bst.Size() == 0;
}
private:
BST<T> bst;
};
基于二分搜索树的映射(map)
# include <iostream>
# include <string>
# include <stack>
# include <queue>
# include <time.h>
using namespace std;
template <class K, class V> class BSTMap;
template<class K, class V>
class Map {
public:
virtual void add(K key, V value) = 0;
virtual V remove(K key) = 0;
virtual bool contains(K key) = 0;
virtual V get(K key) = 0;
virtual int Size() = 0;
virtual bool empty() = 0;
};
template <class K,class V>
class Node {
public:
Node(K key,V value)
{
this->key = key;
this->value = value;
left = NULL;
right - NULL;
}
friend class BSTMap<K,V>;
private:
K key;
V value;
Node<K,V>* left;
Node<K,V>* right;
};
template <class K, class V>
class BSTMap :public Map<K,V>
{
public:
BSTMap()
{
root = NULL;
size = 0;
}
inline int Size()
{
return size;
}
V get(K key)
{
return getNode(root, key)->value;
}
bool empty()
{
return size == 0;
}
void add(K key,V value) //向二分搜索树添加新的元素e
{
/*第一版
if(root==NULL)// 特殊处理
{
root=new Node<T>(e);
size++;
}else
add(root,e);*/
/*第二版*/
root = add(root, key,value);
}
bool contains(K e)
{
return contains(root, e);
}
void preOrder()
{
preOrder(root);
}
void preOrderNR()
{
stack<Node<K,V>*> stack ;
stack.push(root);
while (!stack.empty())
{
Node<K,V>* cur= stack.top();;
stack.pop();
cout << cur->e << " ";
if(cur->left!=NULL)
stack.push(cur->left);
if(cur->right!=NULL)
stack.push(cur->right);
}
}
void inOrder()
{
inOrder(root);
}
void postOrder() //应用:内存释放方面,先将孩子节点的内存都释放干净，再释放根节点
{
postOrder(root);
}
//层次遍历(广度优先遍历)
void levelOrder()
{
queue<Node<K,V>*> q;
q.push(root);
while (!q.empty())
{
Node<K,V>* cur = q.front();
q.pop();
cout << cur->e << " ";
if (cur->left != NULL)
{
q.push(cur->left);
}
if (cur->right != NULL)
q.push(cur->right);
}
}
V minElement()
{
if (!size)
throw "BST is empty";
return minElement(root)->value;
}
V maxElement()
{
if (!size)
throw "BST is empty";
maxElement(root)->value;
}
string toString()
{
string val;
generateBSTString(root, 0, val);
return val;
}
V removeMin()
{
V val = minElement();
root = removeMin(root);
return val;
}
V removeMax()
{
V val = maxElement();
root = removeMax(root);
return val;
}
V remove(K key)
{
V val=getNode(root, key)->value;
root=remove(root, key);
return val;
}
private:
//第一版
/*
void add(Node<T>* root,T e)//以Node为根的二分搜索树插入元素e 递归
{
if(e==root.e)
return ;
else if(e<root.e&&root.left==NULL)
{
root.left=new Node<T>(e);
size++;
return ;
}else if(e>root.e&&root.right==NULL)
{
root.right=new Node<T>(e);
size++;
return ;
}
if(e<root.e)
add(root.left,e);
else
add(root.right,e);
}*/
//第二版 相等的时候返回回去
Node<K,V>* add(Node <K,V>* node, K key,V value)
{
if (node == NULL)
{
size++;
return new Node<K,V>(key,value);
}
if (key < node->key)
node->left = add(node->left, key,value);
else if(key >node->key)
node->right = add(node->right, key, value);
return node;
}
bool contains(Node <K, V>* node, K e)
{
if (node == NULL)
return false;
if (node->key == e)
return true;
else if (node->key < e)
return contains(node->left, e);
else
return contains(node->right, e);
}
void preOrder(Node <K, V>* node)
{
if (node == NULL)
return;
cout << node->value<<" ";
preOrder(node->left);
preOrder(node->right);
}
void inOrder(Node<K, V>* node)
{
if (node == NULL)
return;
inOrder(node->left);
cout << node->value << " ";
inOrder(node->right);
}
void postOrder(Node<K, V>* node)
{
if (node == NULL)
return;
postOrder(node->left);
postOrder(node->right);
cout << node->value << " ";
}
//打印输出函数
void generateBSTString(Node<K, V>* node, int depth, string& str)
{
if (node == NULL)
{
str += generateDepthString(depth) + "null\n";
return;
}
str =str+ generateDepthString(depth) + to_string(node->value) + "\n";
generateBSTString(node->left, depth + 1, str);
generateBSTString(node->right, depth + 1, str);
}
string generateDepthString(int depth)
{
string str;
for (int i = 0; i < depth; i++)
str += "--";
return str;
}
Node<K, V>* minElement(Node<K, V>*node)
{
if (node->left == NULL)
return node;
return minElement(node->left);
}
Node<K, V>* maxElement(Node<K, V>* node)
{
if (node->right == NULL)
return node;
return minElement(node->right);
}
//删除以node为根的二分搜索树中的最小节点
//返回删除节点后新的二分搜索树的根
Node<K, V>* removeMin(Node<K, V>*node)
{
if (node->left == NULL)
{
Node<K, V>* rightNode = node->right;
node->right = NULL;
delete node;
size--;
return rightNode;
}
node->left=removeMin(node->left);
return node;
}
Node<K, V>* removeMax(Node<K, V>*node)
{
if (node->right == NULL) //当前节点为最大值
{
Node* leftNode = node->left;
node->left = NULL;
delete node;
size--;
return leftNode;
}
node->right = removeMax(node->right);
return node;
}
//任意删除节点
Node<K, V>* remove(Node<K, V>* node, K e)
{
if (node == NULL)
return NULL;
if (e < node->key)
{
node->left=remove(node->left,e);
return node;
}
else if (e > node->key)
{
node->right = remove(node->right, e);
return node;
}
else
{
if (node->left == NULL)
{
Node<K,V>* rightNode = node->right;
node->right = NULL;
delete node;
size--;
return rightNode;
}
if (node->right == NULL)
{
Node<K, V>* leftNode = node->left;
node->left = NULL;
delete node;
size--;
return leftNode;
}
Node<T>* successor = new Node<T>(*minElement(node->right));
successor->right = removeMin(node->right);
successor->left = node->left;
node->left = NULL;
node->right = NULL;
delete node;
return successor;
}
}
Node<K, V>* getNode(Node<K,V> *node,K key)
{
if (node == NULL)
return NULL;
if (key < node->key)
getNode(node->left, key);
else if (key > node->key)
getNode(node->right, key);
else
return node;
}
private:
Node<K,V>* root;
int size;
};
完整的基于BST映射代码实现
//BST.hpp
# include <iostream>
# include <string>
# include <stack>
# include <queue>
# include <time.h>
using namespace std;
template <typename K,typename V> class BST;
template <class K,class V>
class BST
{
private:
template <class K, class V>
class Node {
public:
Node(K key, V value)
{
this->key = key;
this->value = value;
height = 1; //初始为叶子节点
left = NULL;
right = NULL;
}
public:
K key;
V value;
Node<K, V>* left;
Node<K, V>* right;
int height;
};
public:
BST()
{
root = NULL;
size = 0;
}
inline int Size()
{
return size;
}
V get(K key)
{
V ret=getNode(root, key)->value;
return ret;
}
void add(K key,V value) //向二分搜索树添加新的元素e
{
/*第一版
if(root==NULL)// 特殊处理
{
root=new Node(e);
size++;
}else
add(root,e);*/
/*第二版*/
root = add(root, key,value);
}
bool contains(K e)
{
return contains(root, e);
}
void preOrder()
{
preOrder(root);
}
void preOrderNR()
{
stack<Node<K,V>*> stack;
stack.push(root);
while (!stack.empty())
{
Node<K,V>* cur = stack.top();;
stack.pop();
cout << cur->key << " ";
if (cur->left != NULL)
stack.push(cur->left);
if (cur->right != NULL)
stack.push(cur->right);
}
}
void inOrder()
{
inOrder(root);
}
void postOrder() //应用:内存释放方面,先将孩子节点的内存都释放干净，再释放根节点
{
postOrder(root);
}
//层次遍历(广度优先遍历)
void levelOrder()
{
queue<Node<K,V>*> q;
q.push(root);
while (!q.empty())
{
Node<K,V>* cur = q.front();
q.pop();
cout << cur->key << " ";
if (cur->left != NULL)
{
q.push(cur->left);
}
if (cur->right != NULL)
q.push(cur->right);
}
}
K minElement()
{
if (!size)
throw "BST is empty";
return minElement(root)->key;
}
K maxElement()
{
if (!size)
throw "BST is empty";
maxElement(root)->key;
}
string toString()
{
string val;
generateBSTString(root, 0, val);
return val;
}
K removeMin()
{
K val = minElement();
root = removeMin(root);
return val;
}
K removeMax()
{
K val = maxElement();
root = removeMax(root);
return val;
}
void remove(K val)
{
root = remove(root, val);
}
bool isBST()
{
vector<K> keys;
inOrder(root, keys);
for (int i = 1; i < keys.size(); i++)
{
if (keys[i] < keys[i - 1])
return false;
}
return true;
}
private:
Node<K, V>* getNode(Node<K, V>* node, K key)
{
if (node == NULL)
return NULL;
if (key < node->key)
return getNode(node->left, key);
else if (key > node->key)
return getNode(node->right, key);
else
return node;
}
Node<K,V>* add(Node<K,V>* node, K key,V value)
{
if (node == NULL)
{
size++;
return new Node<K,V>(key,value);
}
if (key < node->key)
node->left = add(node->left, key,value);
else if (key > node->key)
node->right = add(node->right, key, value);
return node;
}
bool contains(Node<K,V>* node, K e)
{
if (node == NULL)
return false;
if (node->key == e)
return true;
else if (node->key < e)
return contains(node->left, e);
else
return contains(node->right, e);
}
void preOrder(Node<K,V>* node)
{
if (node == NULL)
return;
cout << node->key << " ";
preOrder(node->left);
preOrder(node->right);
}
void inOrder(Node<K,V>* node)
{
if (node == NULL)
return;
inOrder(node->left);
cout << node->key << " ";
inOrder(node->right);
}
void inOrder(Node<K, V>* node, vector<K>& keys)
{
if (node == NULL)
return;
inOrder(node->left,keys);
keys.push_back(node->key);
inOrder(node->right, keys);
}
void postOrder(Node<K,V>* node)
{
if (node == NULL)
return;
postOrder(node->left);
postOrder(node->right);
cout << node->key << " ";
}
//打印输出函数
void generateBSTString(Node<K,V>* node, int depth, string& str)
{
if (node == NULL)
{
str += generateDepthString(depth) + "null\n";
return;
}
str = str + generateDepthString(depth) + to_string(node->key) + "\n";
generateBSTString(node->left, depth + 1, str);
generateBSTString(node->right, depth + 1, str);
}
string generateDepthString(int depth)
{
string str;
for (int i = 0; i < depth; i++)
str += "--";
return str;
}
Node<K,V>* minElement(Node<K,V>* node)
{
if (node->left == NULL)
return node;
return minElement(node->left);
}
Node<K,V>* maxElement(Node<K,V>* node)
{
if (node->right == NULL)
return node;
return minElement(node->right);
}
//删除以node为根的二分搜索树中的最小节点
//返回删除节点后新的二分搜索树的根
Node<K,V>* removeMin(Node<K,V>* node)
{
if (node->left == NULL)
{
Node<K,V>* rightNode = node->right;
node->right = NULL;
delete node;
size--;
return rightNode;
}
node->left = removeMin(node->left);
return node;
}
Node<K,V>* removeMax(Node<K,V>* node)
{
if (node->right == NULL) //当前节点为最大值
{
Node* leftNode = node->left;
node->left = NULL;
delete node;
size--;
return leftNode;
}
node->right = removeMax(node->right);
return node;
}
//任意删除节点
Node<K,V>* remove(Node<K,V>* node, K e)
{
if (node == NULL)
return NULL;
if (e < node->key)
{
node->left = remove(node->left, e);
return node;
}
else if (e > node->key)
{
node->right = remove(node->right, e);
return node;
}
else
{
if (node->left == NULL)
{
Node<K,V>* rightNode =node->right;
node->right = NULL;
delete node;
node = NULL;
size--;
return rightNode;
}
if (node->right == NULL)
{
Node<K,V>* leftNode = node->left;
node->left = NULL;
delete node;
node = NULL;
size--;
return leftNode;
} //有两个孩子节点且都不为空
Node<K,V>* successor = new Node<K,V>(*minElement(node->right));
successor->right = removeMin(node->right);
successor->left = node->left;
node->left = NULL;
node->right = NULL;
delete node;
node = NULL;
return successor;
}
}
private:
Node<K, V>* root;
int size;
};
总结
set和map的二分搜索树实现和链表实现的方式其实都很简单,首先需要声明个set/map接口后继承，然后实现接口中的方法即可。二分搜索树只能应用于有序集合/键 中，链表都可以。
本身二分搜索树就满足集合的性质(值唯一),如果要改写为映射的话实际上也很简单,在每个节点中添加一个值属性，并改写节点的构造函数.
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Comment
