weixin_40725706

这个屌丝很懒，什么也没留下！

热门标签

数据结构与算法：C++实现平衡二叉树_平衡树c++

作者：weixin_40725706 | 2024-05-27 13:20:52

踩

平衡树c++

二叉搜索树的引入

普通二叉搜索树的API分为两种： 静态方法和动态方法。

静态方法不会对二叉树做修改，而仅仅是获取相关的信息，如根据key获取val、获取最大key、获取最小key。

动态方法则会修改树中结点，并进一步影响二叉树的结构，如插入和删除。

插入的顺序影响二叉搜索树的构造

如果按照完全正序或者逆序输入，二叉搜索树的形状就会退化成一个链表。

二叉搜索树查找和二分查找类似，借助于本身的结构，在遍历的过程中跳过一些不必要的结点的比较，从而实现高效的查找。但是，在这种情况下，查找一个结点将要像链表一样遍历它经过的所有结点，这就是最坏的情况。

同样，删除的操作也可能使得原来分布得比较均匀的结点，在删除部分结点之后，整体的分布变得不均匀了，并影响到未来操作的性能。

引入二叉搜索树的 “平衡”的概念： “二叉搜索树各结点分布均匀、各种操作都较为高效”。

在进行插入和删除时，能够通过一些指标，对二叉树的形状变化进行监督，当发现树的形状开始变得不平衡的时候，立即修正二叉树的形状。通过这种方式，不断地使得二叉树的形状和构造维持着一个“平衡”的状态，添加了这种维护机制的二叉搜索树，就是平衡二叉树。

二叉搜索树的定义

说到“监督”，那就有一个用于判断当前二叉树平不平衡的指标。这个监督的指标，就是平衡因子（Balance Factor）。

平衡因子：结点的左子树的高度减去右子树的高度得到的差值。

平衡二叉树(AVL) ：所有结点的平衡因子的绝对值都不超过1。即对平衡二叉树每个结点来说，其左子树的高度 - 右子树高度得到的差值只能为 1， 0 ， -1 这三个值。取得小于 -1或者大于1的值，都被视为打破了二叉树的平衡。

平衡二叉树的实现：

插入/删除的过程中，需要平衡因子作为“指标”，去监督当前这颗二叉树的构造是否符合预期，即——是否是一颗平衡二叉树。而平衡因子BF的计算需要用到该节点的孩子结点的高度属性，这也就意味着，要从node类的实例变量入手，为每个结点设置height属性，并在二叉树结构发生变化时，更新并维护height的正确性。

node类定义如下：


 struct Node {
        int key, val;
        Node *left, *right;
        int height;
        Node(int key, int val) : key(key), val(val), left(nullptr), right(nullptr), height(1) {}
    };

height属性的维护和更新

让我们思考一下， 结点height属性在什么时候会发生变化： 当然是在二叉树结构发生变化的时候，具体表现为：

在插入结点时（put），沿插入的路径更新结点的高度值（不一定会加1 ，要重新计算）
在删除结点时（delete）,沿删除的路径更新结点的高度值（不一定减1，要重新计算）
在发现二叉树变得不平衡的时候，通过“旋转”使其平衡，这时候要更新相关结点的高度值


void updateHeight(Node* node) {
        node->height = 1 + std::max(height(node->left), height(node->right));
} 
 
int height(Node* node) {
        return node ? node->height : 0;
}
Node* put(Node* node, int key, int val) {
        if (!node) return new Node(key, val);
        if (key < node->key) node->left = put(node->left, key, val);
        else if (key > node->key) node->right = put(node->right, key, val);
        else node->val = val;
        updateHeight(node);
      ....
}
Node* deleteNode(int key, Node* node) {
        if (!node) return nullptr;
 
        if (key < node->key) node->left = deleteNode(key, node->left);
        else if (key > node->key) node->right = deleteNode(key, node->right);
        else {
            if (!node->left || !node->right) {
                Node* temp = node->left ? node->left : node->right;
                if (!temp) {
                    temp = node;
                    node = nullptr;
                } else *node = *temp; // Copy contents
                delete temp;
            } else {
                Node* temp = minValueNode(node->right);
                node->key = temp->key;
                node->val = temp->val;
                node->right = deleteNode(temp->key, node->right);
            }
        }
        if (!node) return node;
        updateHeight(node);
....
}

在BST操作的基础上加上更新高度值。

只要能正确维护每个结点的height，就能计算每个节点平衡因子（BF），从而判断当前的平衡二叉树的状态


   int getBalance(Node* node) {
        return node ? height(node->left) - height(node->right) : 0;
    }

当计算出某个结点的平衡因子的绝对值超过1时，我们就要对其进行修正，即通过平衡化的处理，使得不平衡的二叉树重新变得平衡。

左旋和右旋

二叉树的平衡化有两大基础操作：左旋和右旋

1. 左旋，即是逆时针旋转；右旋，即是顺时针旋转

2. 这种旋转在整个平衡化过程中可能进行一次或多次

3.且是从失去平衡的最小子树根结点开始的(即离插入结点最近的、平衡因子超过1的祖先结点)


  Node* rotateRight(Node* y) {
        Node* x = y->left;
        Node* T2 = x->right;
        // Perform rotation
        x->right = y;
        y->left = T2;
        // Update heights
        updateHeight(y);
        updateHeight(x);
        // Return new root
        return x;
    }
    Node* rotateLeft(Node* x) {
        Node* y = x->right;
        Node* T2 = y->left;
        // Perform rotation
        y->left = x;
        x->right = T2;
        // Update heights
        updateHeight(x);
        updateHeight(y);
        // Return new root
        return y;
    }

以左旋操作和右旋操作为基础，构成了平衡化操作的四种情况

假设由于在二叉排序树上插入结点而失去平衡的最小子树的根结点为a （即a是离插入结点最近的、平衡因子超过1的祖先结点)，则失去平衡后的调整操作分为以下4种情况：

LL，RR，LR，RL调整。

1. 单次右旋： 由于在a的左子树的根结点的左子树上插入结点（LL），使a的平衡因子由1变成2，导致以a为根的子树失去平衡，则需进行一次的向右的顺时针旋转操作。

2. 单次左旋： 由于在a的右子树根结点的右子树上插入结点（RR），a的平衡因子由-1变成-2，导致以a为根结点的子树失去平衡，则需要进行一次向左的逆时针旋转操作。

3. 两次旋转、先左旋后右旋： 由于在a的左子树根结点的右子树上插入结点（LR），导致a的平衡因子由1变成2，导致以a为根结点的子树失去平衡，需要进行两次旋转，先左旋后右旋。

4.两次旋转，先右旋后左旋： 由于在a的右子树根结点的左子树上插入结点（RL）， a的平衡因子由-1变成-2，导致以a为根结点的子树失去平衡，则需要进行两次旋转，先右旋后左旋。

根据当前破坏平衡的结点的平衡因子，以及其孩子结点的平衡因子来判断是哪种情况。

根据上面的代码写平衡操作的函数：


  Node* reBalance(Node* node) {
        int balance = getBalance(node);
        // Left Left Case
        if (balance > 1 && getBalance(node->left) >= 0)
            return rotateRight(node);
        // Left Right Case
        if (balance > 1 && getBalance(node->left) < 0) {
            node->left = rotateLeft(node->left);
            return rotateRight(node);
        }
        // Right Right Case
        if (balance < -1 && getBalance(node->right) <= 0)
            return rotateLeft(node);
        // Right Left Case
        if (balance < -1 && getBalance(node->right) > 0) {
            node->right = rotateRight(node->right);
            return rotateLeft(node);
        }
        return node;
    }

二叉平衡树完整C++的代码：


#include <iostream>
#include <algorithm>
#include <queue>
class AVL {
public:
    struct Node {
        int key, val;
        Node *left, *right;
        int height;
        Node(int key, int val) : key(key), val(val), left(nullptr), right(nullptr), height(1) {}
    };
    Node* root = nullptr;
    // Public interface for inserting a key-value pair
    void put(int key, int val) {
        root = put(root, key, val);
    }
    // Public interface for deleting the minimum key
    void deleteMin() {
        root = deleteMin(root);
    }
    // Public interface for deleting a key
    void deleteKey(int key) {
        root = deleteNode(key, root);
    }
    // Public interface for printing the tree level by level
    void levelIterator() {
        if (!root) return;
        std::queue<Node*> queue;
        queue.push(root);
        while (!queue.empty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                Node* current = queue.front();
                queue.pop();
                std::cout << current->val << "-->";
                if (current->left) queue.push(current->left);
                if (current->right) queue.push(current->right);
            }
            std::cout << "\n";
        }
    }
 
private:
    // Utility methods translated from the Java code, adapted to C++ style
    Node* put(Node* node, int key, int val) {
        if (!node) return new Node(key, val);
        if (key < node->key) node->left = put(node->left, key, val);
        else if (key > node->key) node->right = put(node->right, key, val);
        else node->val = val;
        updateHeight(node);
        return reBalance(node);
    }
    Node* deleteMin(Node* node) {
        if (!node->left) {
            Node* rightChild = node->right;
            delete node;
            return rightChild;
        }
        node->left = deleteMin(node->left);
        updateHeight(node);
        return reBalance(node);
    }
    Node* deleteNode(int key, Node* node) {
        if (!node) return nullptr;
 
        if (key < node->key) node->left = deleteNode(key, node->left);
        else if (key > node->key) node->right = deleteNode(key, node->right);
        else {
            if (!node->left || !node->right) {
                Node* temp = node->left ? node->left : node->right;
                if (!temp) {
                    temp = node;
                    node = nullptr;
                } else *node = *temp; // Copy contents
                delete temp;
            } else {
                Node* temp = minValueNode(node->right);
                node->key = temp->key;
                node->val = temp->val;
                node->right = deleteNode(temp->key, node->right);
            }
        }
        if (!node) return node;
        updateHeight(node);
        return reBalance(node);
    }
    Node* minValueNode(Node* node) {
        Node* current = node;
        while (current && current->left) current = current->left;
        return current;
    }
    void updateHeight(Node* node) {
        node->height = 1 + std::max(height(node->left), height(node->right));
    }
    int height(Node* node) {
        return node ? node->height : 0;
    }
    int getBalance(Node* node) {
        return node ? height(node->left) - height(node->right) : 0;
    }
    Node* rotateRight(Node* y) {
        Node* x = y->left;
        Node* T2 = x->right;
        // Perform rotation
        x->right = y;
        y->left = T2;
        // Update heights
        updateHeight(y);
        updateHeight(x);
        // Return new root
        return x;
    }
    Node* rotateLeft(Node* x) {
        Node* y = x->right;
        Node* T2 = y->left;
        // Perform rotation
        y->left = x;
        x->right = T2;
        // Update heights
        updateHeight(x);
        updateHeight(y);
        // Return new root
        return y;
    }
    Node* reBalance(Node* node) {
        int balance = getBalance(node);
        // Left Left Case
        if (balance > 1 && getBalance(node->left) >= 0)
            return rotateRight(node);
        // Left Right Case
        if (balance > 1 && getBalance(node->left) < 0) {
            node->left = rotateLeft(node->left);
            return rotateRight(node);
        }
        // Right Right Case
        if (balance < -1 && getBalance(node->right) <= 0)
            return rotateLeft(node);
        // Right Left Case
        if (balance < -1 && getBalance(node->right) > 0) {
            node->right = rotateRight(node->right);
            return rotateLeft(node);
        }
        return node;
    }
};

测试：


#include "AVL/avl.h"
int main() {
    AVL tree;
    tree.put(1, 11);
    tree.put(2, 22);
    tree.put(3, 33);
    tree.put(4, 44);
    tree.put(5, 55);
    tree.put(6, 66);
    tree.levelIterator();
    return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/632204

数据结构与算法：C++实现 平衡二叉树_平衡树c++

二叉搜索树的引入

二叉搜索树的定义

平衡二叉树的实现：

数据结构与算法：C++实现平衡二叉树_平衡树c++