[数据结构与算法]四、高级数据结构和算法：二叉搜索树（BST树）、平衡二叉树（AVL树）

4 二叉查找树（BST树）、平衡二叉树（AVL树）

4.1 二叉查找树（BST树）

二叉查找树(Binary Search Tree, BST)，又被称为二叉搜索树

4.1.1 特点

（1）若节点的左子树不空, 则左子树上所有节点的key均小于它的根节点的key
（2）若节点的右子树不空, 则右子树上所有节点的key均大于它的根节点的key
（3）任意节点的左,右子树也分别为二叉查找树
（4）没有key相等的节点

二叉查找树进行中序遍历，可以得到一个递增的有序序列

• 实例

#include <iostream>
using namespace std;
class Node{
public:
    char val;
    Node* left;
    Node* right;
    Node(char val):val(val),left(nullptr),right(nullptr){}
    Node(char val,Node* left,Node* right):val(val),left(left),right(right){}
};
class BSTtree{
private:
    Node* m_root = nullptr;
    void inorder(Node* root){
    	if(nullptr == root) return;
		inorder(root->left);
		cout << root->val << " ";
		inorder(root->right);
    }
    Node* Insert(Node* root,char val){
    	if(nullptr ==  root) return new Node(val);
		if(root->val > val){
	    	root->left = Insert(root->left,val);
		}else{
	   		root->right = Insert(root->right,val);
		}
		return root;
    }
public:
    void Insert(char val){
		m_root = Insert(m_root,val);
    }
    void Print(){
    	inorder(m_root);//二叉查找树进行中序遍历，可以得到一个递增的有序序列
		cout << endl;
    }
};
int main(){
    BSTtree root;
    root.Insert('T');
    root.Insert('E');
    root.Insert('B');
    root.Insert('F');
    root.Insert('Y');
    root.Insert('X');
    root.Insert('Z');
    
    root.Print();
}

树的结构：

结果：B E F T X Y Z
分析：递增序列

4.1.2 结构

二叉搜索树通常使用链式存储孩子表示法。

class Node{
public:
    char val;
    Node* left;
    Node* right;
    Node(char val):val(val),left(nullptr),right(nullptr){}
    Node(char val,Node* left,Node* right):val(val),left(left),right(right){}
};

4.1.3 操作（插入、查找和删除）

4.1.3.1 插入

• 步骤
  （1）如果二叉查找树为空，则直接插入。
  （2）如果插入节点key小于根结点key，则插入到左子树中；大于根结点key，则插入到右子树中。
  （3）依次类推，直到找到插入位置。
  
• 实例

#include <iostream>
using namespace std;
template <typename T> 
class _Node{
public:
    T val;
    _Node* left;
    _Node* right;
    _Node(T val):val(val),left(nullptr),right(nullptr){}
    _Node(T val,_Node* left,_Node* right):val(val),left(left),right(right){}
};
template <typename T>
class BSTtree{
private:
    typedef _Node<T> Node;
    Node* m_root = nullptr;
    void inorder(Node* root){
    	if(nullptr == root) return;
		inorder(root->left);
		cout << root->val << " ";
		inorder(root->right);
    }
    void preorder(const Node* root){
    	if(nullptr == root) return;
    	if(root->left) cout << root->val << "--" << root->left->val << endl;
    	if(root->right) cout << root->val << "--" << root->right->val << endl;
    	preorder(root->left);
    	preorder(root->right);
    }
    Node* Insert(Node* root,T val){
    	if(nullptr ==  root) return new Node(val);
		if(root->val > val){
	    	root->left = Insert(root->left,val);
		}else{
	    	root->right = Insert(root->right,val);
		}
		return root;
    }
public:
    void Insert(T val){
   		if(Search(val)) return;
		m_root = Insert(m_root,val);
    }
    void Print(){
    	inorder(m_root);//二叉查找树进行中序遍历，可以得到一个递增的有序序列
		cout << endl;
    	preorder(m_root);
    }
};
int main(){
    BSTtree<int> root;
    root.Insert(15);
    root.Insert(4);
    root.Insert(20);
    root.Insert(17);
    root.Insert(19);
    
    root.Print();
}

树的结构：

结果：

4 15 17 19 20 
15--4
15--20
20--17
17--19

4.1.3.2 查找

• 查找指定key的节点
  （1）从根结点开始，若二叉树非空，将给定值与根结点的关键字比较，若相等，则查找成功；
  （2）若不等，则当给定值小于根结点关键字时，在根结点的左子树中查找，否则在根结点的右子树中查找。

• 实例

#include <iostream>
using namespace std;
template <typename T> 
class _Node{
public:
    T val;
    _Node* left;
    _Node* right;
    _Node(T val):val(val),left(nullptr),right(nullptr){}
    _Node(T val,_Node* left,_Node* right):val(val),left(left),right(right){}
};
template <typename T>
class BSTtree{
private:
    typedef _Node<T> Node;
    Node* m_root = nullptr;
    bool Search(Node* root,T val){
    	if(nullptr == root) return false;
		if(root->val == val) return true;
		if(root->val < val){
	    	Search(root->right,val);
		}else{
	    	Search(root->left,val);
		}
    }
    void inorder(Node* root){
    	if(nullptr == root) return;
		inorder(root->left);
		cout << root->val << " ";
		inorder(root->right);
    }
    void preorder(const Node* root){
    	if(nullptr == root) return;
    	if(root->left) cout << root->val << "--" << root->left->val << endl;
    	if(root->right) cout << root->val << "--" << root->right->val << endl;
    	preorder(root->left);
    	preorder(root->right);
    }
    Node* Insert(Node* root,T val){
    	if(nullptr ==  root) return new Node(val);
		if(root->val > val){
	    	root->left = Insert(root->left,val);
		}else{
		    root->right = Insert(root->right,val);
		}
		return root;
    }
public:
    bool Search(T val){
    	return Search(m_root,val);
    }
    void Insert(T val){
   		if(Search(val)) return;
		m_root = Insert(m_root,val);
    }
    void Print(){
    	inorder(m_root);//二叉查找树进行中序遍历，可以得到一个递增的有序序列
		cout << endl;
    	preorder(m_root);
    }
};
int main(){
    BSTtree<int> root;
    root.Insert(15);
    root.Insert(4);
    root.Insert(20);
    root.Insert(17);
    root.Insert(19);
    
    root.Print();

    cout << root.Search(1) << " " << root.Search(19) << endl;
}

4.1.3.3 删除

二叉查找树的删除操作是相对复杂一点，它要按 3 种情况来处理：

（1）被删除结点是叶子结点，直接删除。

（2）结点只有左子树或只有右子树，则让子树替代；

（3）结点既有左子树，又有右子树，有两种处理方式
a）合并删除，右子树合并到左子树的最大值的右子树上；或者左子树合并到右子树最小值的左子树上。
b）替代删除，后继代替删除节点，然后删除后继；或者前驱代替删除节点，然后删除前驱。（常用）

• 实例

#include <iostream>
using namespace std;
template <typename T>
class _Node {
public:
    T val;
    _Node* left;
    _Node* right;
    _Node(T val):val(val),left(nullptr),right(nullptr) {}
    _Node(T val,_Node* left,_Node* right):val(val),left(left),right(right) {}
};
template <typename T>
class BSTtree {
private:
    typedef _Node<T> Node;
    Node* m_root = nullptr;
    bool Search(Node* root,T val) {
        if(nullptr == root) return false;
        if(root->val == val) return true;
        if(root->val < val) {
            return Search(root->right,val);
        } else {
            return Search(root->left,val);
        }
    }
    void inorder(Node* root) {
        if(nullptr == root) return;
        inorder(root->left);
        cout << root->val << " ";
        inorder(root->right);
    }
    void preorder(const Node* root) {
        if(nullptr == root) return;
        if(root->left) cout << root->val << "--" << root->left->val << endl;
        if(root->right) cout << root->val << "--" << root->right->val << endl;
        preorder(root->left);
        preorder(root->right);
    }
    Node* Insert(Node* root,T val) {
        if(nullptr ==  root) return new Node(val);
        if(root->val > val) {
            root->left = Insert(root->left,val);
        } else {
            root->right = Insert(root->right,val);
        }
        return root;
    }
    Node* Remove(Node* root,T val) {
        if(nullptr == root) return nullptr;
        if(root->val < val) {
            root->right = Remove(root->right,val);
        } else if(root->val > val) {
            root->left = Remove(root->left,val);
        } else {
            //删除结点为叶子节点，直接删除
            //左右子树都为空
            if(nullptr == root->right && nullptr == root->left) {
                delete root;
                return nullptr;
            }
            //结点只有左子树或只有右子树，则让子树替代
            //右子树为空，左子树作为根结点
            if(nullptr == root->right) {
                Node* left = root->left;
                delete root;
                return left;
            }
            //左子树为空，右子树作为根结点
            if(nullptr == root->left) {
                Node* right = root->right;
                delete root;
                return right;
            }
            //左右子树都不为空，右子树中找到最小值，替换掉根结点
            T minval = Minimum(root->right);
            root->val = minval;
            //root->right = Remove(root->right,minval);
            root->right = DeleteMin(root->right);
        }
        return root;
    }
    int Minimum(Node* root) {
        if(nullptr == root) throw runtime_error("root is null");
        while(nullptr != root->left) {
            root = root->left;
        }
        return root->val;
    }
    Node* DeleteMin(Node* root) {
        if(nullptr == root) throw runtime_error("root is null");
        Node* prev = nullptr;
        Node* cur = root;
        while(nullptr != cur->left) {
            prev = cur;
            cur = cur->left;
        }
		prev->left = nullptr;
        delete cur;
		return root;
    }
public:
    bool Search(T val) {
        return Search(m_root,val);
    }
    void Insert(T val) {
        if(Search(val)) return;
        m_root = Insert(m_root,val);
    }
    void Print() {
        inorder(m_root);//二叉查找树进行中序遍历，可以得到一个递增的有序序列
        cout << endl;
        preorder(m_root);
    }
    void Remove(T val) {
        m_root = Remove(m_root,val);
    }
};
int main() {
    BSTtree<int> root;
    root.Insert(15);
    root.Insert(10);
    root.Insert(30);
    root.Insert(5);
    root.Insert(11);
    root.Insert(12);
    root.Insert(20);
    root.Insert(40);

    root.Remove(15);
    root.Print();

}

树的可视化工具：GraphvizOnline

删除前

删除结点15后

删除结点5后

删除结点11后

4.1.4 优缺点

• 优点

• 缺点
  二叉搜索树构造顺序影响操作的时间复杂度。

4.2 平衡二叉树（AVL树）

解决BST树的缺点：不平衡

如果数据连续，则BST树退化成链表的形式，导致查找效率低。
此时，采用AVL树可解决BST树的缺点。

平衡二叉树/自平衡二叉查找树(Balanced Binary Tree)： 也称为AVL树。
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

• 特点
  （1）左右子树深度之差的绝对值不超过1(任意节点的两子树的高度最大差别为1).
  （2）左右子树仍然为平衡二叉树.

4.2.1 判断平衡

平衡因子BF(Balance Factor)：左树深度减去右树深度的值。平衡因子BF = 左子树深度－右子树深度。
平衡二叉树每个结点的平衡因子只能是1，0，-1。若其绝对值超过1，则该二叉排序树就是不平衡的。当BF为-1、0、1时，二叉树平衡；反之，不平衡。

（1）（3）不是
（2）（4）是

4.2.2 操作

AVL树的操作基本和二叉查找树一样，这里我们关注的是两个变化很大的操作：插入和删除！

4.2.3 旋转

旋转条件：当最小不平衡子树根节点BF>1,右旋；BF<-1,左旋。

当P的A、B节点插入新结点，导致Q点不平衡，左重右轻，右旋。
当Q的B、C节点插入新结点，导致P点不平衡，右重左轻，左旋。
旋转点上升，不平衡点向轻的一侧旋转。

• 旋转步骤：
  （1）获取旋转节点
  （2）旋转节点的子节点替换父节点的旋转节点
  （3）旋转节点父节点做旋转节点子节点
  （4）返回旋转节点

例:

（1）依次插入1,2,3
（2）依次插入3,2,1

（3）依次插入2,1,3或2,3,1

（4）依次插入1,3,2

（5）依次插入3,1,2

（6）依次插入4,5
（7）依次插入6,7

4.2.4 插入

插入时的不平衡的四种情况：
LL：插入一个新节点到不平衡节点的左子树（Left）的左子树（Left），导致不平衡节点的平衡因子由1变为2

RR：插入一个新节点到不平衡节点的右子树（Right）的右子树（Right），导致不平衡节点的平衡因子由-1变为-2

LR：插入一个新节点到不平衡节点的左子树（Left）的右子树（Right），导致不平衡节点的平衡因子由1变为2

RL：插入一个新节点到不平衡节点的右子树（Right）的左子树（Left），导致不平衡节点的平衡因子由-1变为-2

• 不平衡处理方法
  （1）单向右旋平衡处理LL
  （2）单向左旋平衡处理RR
  （3）双向旋转（先左后右）平衡处理LR
  （4）双向旋转（先右后左）平衡处理RL

• 实例

#include <iostream>
#include <stack>
#include <queue>
using namespace std;
template <typename T>
class _Node{
public:
    T val;
    _Node* left;
    _Node* right;
    _Node(const T& val):val(val),left(nullptr),right(nullptr){}
    _Node(const T& val,_Node* left,_Node* right):val(val),left(left),right(right){}
};
//    P         Q
//   / \       / \
//  Q   C     A   P
// / \           / \
//A   B         B   C
typedef _Node<int> Node;
Node* RotateRight(Node* root){
    Node* p = root;
    Node* q = root->left;
    Node* b = q->right;
    q->right = p;
    p->left = b;
    return q;
}
//    P         Q
//   / \       / \
//  A   Q     P   C
//     / \   / \       
//    B   C A   B
Node* RotateLeft(Node* root){
    Node* p = root;
    Node* q = root->right;
    Node* b = q->left;
    q->left = p;
    p->right = b;
    return q;
}
void Preorder(Node* root){
     if(nullptr == root) return;
     if(root->left) cout << root->val << "--" << root->left->val << endl;
     if(root->right) cout << root->val << "--" << root->right->val << endl;
     Preorder(root->left);
     Preorder(root->right);
} 
int main(){
    cout << "左旋:" << endl;
{
    Node a(1);
    Node b(2);
    Node c(3);
	
    a.right = &b;
    b.right = &c;

    Preorder(&a);
    Node* root = RotateLeft(&a); //左旋
    Preorder(root);
}
cout << "右旋:" << endl;
{
    Node a(1);
    Node b(2);
    Node c(3);
	
    c.left = &b;
    b.left = &a;

    Preorder(&c);
    Node* root = RotateRight(&c); //左旋
    Preorder(root);

}
cout << "右旋左旋:" << endl;
{
    Node a(1);
    Node b(2);
    Node c(3);
	
    a.right = &c;
    c.left = &b;
    Node* root = &a;

    Preorder(root);
    root->right = RotateRight(root->right);
    Preorder(root);
    root = RotateLeft(root); //左旋
    Preorder(root);

}
cout << "左旋右旋:" << endl;
{
    Node a(1);
    Node b(2);
    Node c(3);
	
    c.left = &a;
    a.right = &b;

    Node* root = &c;
    Preorder(root);
    root->left = RotateLeft(root->left);
    Preorder(root);
    root = RotateRight(root); //左旋
    Preorder(root);
}
}

结果：

左旋:
1--2
2--3
2--1
2--3
右旋:
3--2
2--1
2--1
2--3
右旋左旋:
1--3`在这里插入代码片`
3--2
1--2
2--3
2--1
2--3
左旋右旋:
3--1
1--2
3--2
2--1
2--1
2--3

4.2.5 删除

• 删除节点有三种情况
  （1）删除叶子节点。
  （2）删除只有一棵子树的节点。
  （3）删除有两棵子树的节点。

AVL删除与BST删除方式一致，在BST删除结点的基础上增加平衡操作即可。

• 实例

#include <iostream>
#include <stack>
#include <vector>
#include <queue>
using namespace std;

template <typename T>
class _Node {
public:
    T val;
    _Node* left;
    _Node* right;
    _Node(const T& val):val(val),left(nullptr),right(nullptr) {}
    _Node(const T& val,_Node* left,_Node* right):val(val),left(left),right(right) {}
};

template <typename T>
class AVLTree {
    typedef _Node<T> Node;
    Node* m_root = nullptr;
public:
    bool Search(const T& val) {
        return Search(m_root,val);
    }
    void Insert(const T& val) {
        if(Search(val)) return;
        m_root = Insert(m_root,val);
    }
    void Remove(const T& val) {
        m_root = Remove(m_root,val);
    }
    void Print() {
        preorder(m_root);
    }
private:
    bool Search(Node* root,const T& val) {
        if(nullptr == root) return false;
        if(root->val == val) return true;
        if(root->val < val) {
            return Search(root->right,val);
        } else {
            return Search(root->left,val);
        }
        // return Search(root->val<val?root->right:root->left,val);
    }
    Node* Remove(Node* root,const T& val) {
        if(nullptr == root) return nullptr;
        if(root->val < val) root->right = Remove(root->right,val);
        else if(root->val > val) root->left = Remove(root->left,val);
        else {
            if(nullptr == root->right && nullptr == root->left) {
                delete root;
                return nullptr;
            }
            if(nullptr == root->right) {
                Node* left = root->left;
                delete root;
                return left;
            }
            if(nullptr == root->left) {
                Node* right = root->right;
                delete root;
                return right;
            }
            T minval = Minimun(root->right);
            root->val = minval;
            root->right = Remove(root->right,minval);
            // root->right = DeleteMin(root->right);
        }
        return Balance(root);
    }
    Node* DeleteMin(Node* root) {
        if(nullptr == root) throw runtime_error("root is null");
        Node* prev = nullptr;
        Node* cur = root;
        while(nullptr != cur->left) {
            prev = cur;
            cur = cur->left;
        }
        delete cur;
        return root;
    }
    T Minimun(Node* root) {
        if(nullptr == root) throw runtime_error("root is null");
        while(nullptr != root->left) root = root->left;
        return root->val;
    }
    T Maximun(Node* root) {
        if(nullptr == root) throw runtime_error("root is null");
        while(nullptr != root->right) root = root->right;
        return root->val;
    }
    Node* Insert(Node* root,const T& val) {
        if(nullptr == root) return new Node(val);
        if(root->val>val) {
            root->left = Insert(root->left,val);
        } else {
            root->right = Insert(root->right,val);
        }
        return Balance(root);
    }
    void preorder(const Node* root) {
        if(nullptr == root) return;
        if(root->left) cout << root->val << "--" << root->left->val << endl;
        if(root->right) cout << root->val << "--" << root->right->val<< endl;
        preorder(root->left);
        preorder(root->right);
    }
//     P          Q
//    / \        / \
//   Q   C      A   P
//  / \            / \
// A   B          B   C
    Node* RotateRight(Node* root) {
        Node* p = root;
        Node* q = p->left;
        Node* b = q->right;
        q->right = p;
        p->left = b;
        return q;
    }
//   P            Q
//  / \          / \
// A   Q        P   C
//    / \      / \
//   B   C    A   B
    Node* RotateLeft(Node* root) {
        Node* p = root;
        Node* q = p->right;
        Node* b = q->left;
        q->left = p;
        p->right = b;
        return q;
    }
    int Balancefactory(Node* root) {
        return Depth(root->left)-Depth(root->right);
    }

    Node* Balance(Node* root) {
        int bf = Balancefactory(root);
        if(bf == -2) {
            if(Balancefactory(root->right)>0) {
                root->right = RotateRight(root->right);
            }
            root = RotateLeft(root);
        } else if(bf == 2) {
            if(Balancefactory(root->left)<0) {
                root->left = RotateLeft(root->left);
            }
            root = RotateRight(root);
        }
        return root;
    }

    int Depth(Node* root){
        if(nullptr == root) return 0;
		return max(Depth(root->left),Depth(root->right))+1;
    }
};
int main() {
    AVLTree<int> intbst;
    int n;
    while(cin >> n) {
        intbst.Insert(n);
    }
    intbst.Print();
}

输入1 2 3 4 5，结果为：

[root@localhost avl]# ./a.out 
1
2
3
4
5
2--1
2--4
4--3
4--5

画出树的结构，可以看出，插入数据后，树会自动保持平衡

移除结点1，仍然保持平衡

4.3 BST vs. AVL

区别：AVL的插入和删除操作在BST的基础上加入平衡操作。