1.二叉查找树
二叉查找树是一颗二叉树，其中每一个结点都含有一个可比较的键以及相关联的值，并且每个结点的键都大于左子树的任意结点的键而小于右子树的任意结点的键
-
结点定义
template <typename T> class BSTNode { public: int key; //键 T val; //值 BSTNode *left, *right; int N; BSTNode(int k, T v, int n) : key(k), val(v), N(1), left(NULL), right(NULL){} }; -
查找(递归实现)
由二叉树查找树的结构可知，查询每个结点所需要的比较次数为结点的深度加一。只要结点的关键字若等于查找的关键字，则查找成功；若小于结点的关键字则递归查找左子树，大于结点的关键字则递归查找右子树，若子树为空，则查找失败。
代码实现：
template <typename T> T get(BSTNode *node, int key) { if (node->key == key) return node->val; else if (node->key > key) return get(node->left, key); //左子树递归查找 else return get(node->right, key); //右子树递归查找 }二叉查找树的查找在理论情况下，n个结点的完美二叉查找树的高度为\(log_2(n+1)-1\)，因此一般的二叉查找树的查找次数\(\lceil log_2(n+1)\rceil\)，在最坏情况下，二叉查找树的每一层只有一个结点查找次数为n，因此二叉查找树的时间复杂度在\(O(logn)\sim O(n)\)
-
插入(递归实现)
二叉查找树的插入操作与查询操作基本相同，比较键值是否相等，相等则返回，表示已经存在，不相等则根据大小在左右子树递归查找，直到找到相等键值的结点，或者子结点为空时，插入空节点的位置
代码实现：
template <typename T> BSTNode *put(BSTNode *node, int key, T val) { if (node == NULL) return new BSTNode(key, val, 1); if (node->key == key) node->val = val; else if (node->key > key) node->left = put(node->left, key, val); else node->right = put(node->right, key, val); node->N = 1 + size(node->left) + size(node->right); return node; } -
删除(递归实现)
删除的操作较为复杂，分为三种情况
-
叶子结点
删除叶子结点并不会影响二叉查找树的结构，直接将指向待删除结点的链接指向空即可
-
结点只有左子树或者右子树
只要将指向待删除结点的链接指向左子树或者右子树
-
结点有左右子树
删除这种类型的结点有可能会破坏平衡二叉查找树的结构，在删除这个结点之后我们需要处理两个子树，我们只需要找到该结点的后继结点(右子树的最小结点)，将指向该结点的链接指向后继结点即可
代码实现：
BSTNode *delKey(BSTNode *node, int key) { if (node == nullptr) return nullptr; if (key < node->key) { node->left = delKey(node->left, key); } else if (key > node->key) { node->right = delKey(node->right, key); } else { if (node->left == nullptr || node->right == nullptr) //叶子结点和只有一个子树的结点 { BSTNode *temp = node; node = (node->left != nullptr) ? node->left : node->right; delete temp; } else //有左右子树的结点 { BSTNode *temp = getMin(node->right); //查找后继结点 temp->right = delMin(node->right); //后继结点的右子树为删除后继结点后的右子树 temp->left = node->left; } } node->N = size(node->left) + size(node->right) + 1; return node; }在前两种情况下，删除结点的操作复杂度都是常数级，第三种情况查找后继结点为内部查询操作，相当于两个层次的查询操作，因此总复杂度仍为\(O(logn)\sim O(n)\)；
-
-
总结
二叉查找树的查询，插入，删除性能都与树的高度相关，如果能将二叉查找树更加平衡一些，减少线性结构，能有效提高性能。
代码附录
#include <iostream> #include <vector> #include <queue> using namespace std; template <typename T> class BSTree { private: class BSTNode //结点定义 { public: int key; T val; BSTNode *left, *right; int N; BSTNode(int k, T v, int n) : key(k), val(v), N(1), left(NULL), right(NULL) { } BSTNode(BSTNode *node) { key = node->key; val = node->val; left = node->left; right = node->right; N = node->N; } }; BSTNode *root; //根节点 int size(BSTNode *node) { if (node == NULL) return 0; else return root->N; } T get(BSTNode *node, int key) { if (node->key == key) return node->val; else if (node->key > key) return get(node->left, key); else return get(node->right, key); } BSTNode *put(BSTNode *node, int key, T val) { if (node == NULL) return new BSTNode(key, val, 1); if (node->key == key) node->val = val; else if (node->key > key) node->left = put(node->left, key, val); else node->right = put(node->right, key, val); node->N = 1 + size(node->left) + size(node->right); return node; } BSTNode *delMin(BSTNode *node) { if (node->left == NULL) return node->right; node->left = delMin(node->left); node->N = size(node->left) + size(node->right); return node; } BSTNode *getMin(BSTNode *node) { while (node->left != NULL) node = node->left; return node; } BSTNode *delKey(BSTNode *node, int key) { if (node == nullptr) return nullptr; if (key < node->key) { node->left = delKey(node->left, key); } else if (key > node->key) { node->right = delKey(node->right, key); } else { if (node->left == nullptr || node->right == nullptr) { BSTNode *temp = node; node = (node->left != nullptr) ? node->left : node->right; delete temp; } else { BSTNode *temp = getMin(node->right); temp->right = delMin(node->right); temp->left = node->left; } } node->N = size(node->left) + size(node->right) + 1; return node; } public: BSTree() { root = nullptr; } int size() { return size(root); } T get(int key) //查询操作 { return get(root, key); } void put(int key, T val) //插入操作 { root = put(root, key, val); } void delMin() //删除最小值 { root = delMin(root); } void delKey(int key) //删除操作 { root = delKey(root, key); } void print() //输出二叉查找树 { vector<int> BFS; queue<BSTNode *> BiQueue; BiQueue.push(root); while (!BiQueue.empty()) { BSTNode *temp = BiQueue.front(); BiQueue.pop(); BFS.push_back(temp->key); if (temp->left != NULL) BiQueue.push(temp->left); if (temp->right != NULL) BiQueue.push(temp->right); ; } for (auto &ch : BFS) { cout << ch << " "; } cout << endl; } }; int main() { BSTree<int> *bitree = new BSTree<int>(); for (int i = 0; i < 10; i++) { int t = rand() % 100; cout << t << endl; bitree->put(t, i); } bitree->print(); bitree->delKey(0); bitree->print(); }
2.平衡二叉查找树(AVL树)
平衡二叉查找树，它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均查找长度。
AVL树的性质：
- 左子树与右子树高度之差的绝对值不超过1
- 树的每个左子树和右子树都是AVL树
- 每一个节点都有一个平衡因子（balance factor），任一节点的平衡因子是-1、0、1（每一个节点的平衡因子 = 右子树高度 - 左子树高度）
-
AVL树的结点设计
AVL树的结点与二叉查找树的结点相似，多了一个值来作为平衡因子判断结点是否平衡
代码实现：
template <typename T> class AVLTreeNode { public: T key; int height; AVLTreeNode *left; AVLTreeNode *right; AVLTreeNode(T val, AVLTreeNode *l, AVLTreeNode *r) : key(val), height(0), left(l), right(r) {} }; -
AVL树的自平衡操作——旋转
-
右旋(LL)
将pivot变为根节点，root变为pivot的右子树，pivot的右子树变为root的左子树
代码实现
AVLTreeNode *LL(AVLTreeNode *node) //左左 { AVLTreeNode *new_root = node->left; node->left = new_root->right; new_root->right = node; node->height = max(height(node->left), height(node->right)) + 1; new_root->height = max(height(new_root->left), height(new_root->right)) + 1; return new_root; } -
左旋(RR)
与LL情况相反即可，将pivot变为根节点，root变为pivot的左子树，pivot的左子树变为root的右子树
代码实现
AVLTreeNode *RR(AVLTreeNode *node) //右右 { AVLTreeNode *new_root = node->right; node->right = new_root->left; new_root->left = node; node->height = max(height(node->left), height(node->right)) + 1; new_root->height = max(height(new_root->left), height(new_root->right)) + 1; return new_root; } -
左右旋转(LR)
两次旋转，第一次是对root的左旋，第二次是对原来root的父母结点进行右旋
代码实现
AVLTreeNode *LR(AVLTreeNode *node) //左右 { node->left = LL(node->left); return LL(node); } -
右左旋转(RL)
两次旋转，第一次是对root的右旋，第二次是对原来root的父母结点进行左旋
代码实现
AVLTreeNode *RL(AVLTreeNode *node) //右左 { node->right = LL(node->right); return RR(node); }
-
-
插入操作
AVL本身也是二叉查找树，因此插入操作与二叉查找树类似，只需要加上旋转的操作来调整高度。当给一个平衡的AVL树进行插入一个新结点P时，从P到根结点的路径上，每个子树的高度都有可能+1，所以要对路径上的每一个结点进行调整。
代码实现
AVLTreeNode *insert(AVLTreeNode *node, T key) { if (node == NULL) { AVLTreeNode *temp = new AVLTreeNode(key, NULL, NULL); node = temp; } else if (key < node->key) { node->left = insert(node->left, key); if (height(node->left) - height(node->right) == 2) { if (key < node->left->key) node = LL(node); else node = LR(node); } } else if (key > node->key) { node->right = insert(node->right, key); if (height(node->right) - height(node->left) == 2) { if (key > node->right->key) node = RR(node); else node = RL(node); } } node->height = max(height(node->right), height(node->left)) + 1; return node; } -
删除操作
同样，AVL树的删除操作与二叉查找树的删除操作相似，只需要加上旋转的操作来调整高度。
代码实现
AVLTreeNode *remove(AVLTreeNode *node, AVLTreeNode *delnode) { if (node == nullptr || delnode == nullptr) return nullptr; if (delnode->key < node->key) { node->left = remove(node->left, delnode); if (height(node->right) - height(node->left) == 2) { if (height(node->right->left) > height(node->right->right)) node = RL(node); else node = RR(node); } } else if (delnode->key > node->key) { node->right = remove(node->right, delnode); if (height(node->left) - height(node->right) == 2) { if (height(node->left->right) > height(node->left->left)) node = LR(node); else node = LL(node); } } else { if (node->left == nullptr || node->right == nullptr) { AVLTreeNode *temp = node; node = (node->left != nullptr) ? node->left : node->right; delete temp; } else { if (height(node->left) > height(node->right)) { AVLTreeNode *max = getMax(node->left); node->key = max->key; node->left = remove(node->left, max); } else { AVLTreeNode *min = getMin(node->right); node->key = min->key; node->right = remove(node->right, min); } } } return node; } -
总结
在AVL树中，不管我们进行执行插入还是删除操作，都要进行旋转来调整平衡，而调整是非常耗时的，因此AVL适合用于插入删除次数较少，查询次数较多的情况。