数据结构_平衡二叉树

结点类

构造函数分为有参和无参，相同点都是初始化树高为1

class Node
{
public:
    int data;  // 用于输出
    int val;   // 数据域，用于排序
    int height; // 树高
    Node* left;
    Node* right;

    Node();
    Node(int v, int d);
    static int max(int a, int b);
};

Node::Node()
{
    data = -1;
    val = -1;
    height = 1;
    left = nullptr;
    right = nullptr;
}

Node::Node(int v, int d)
{
    data = d;
    val = v;
    height = 1;
    left = nullptr;
    right = nullptr;
}

int Node::max(int a, int b)
{
    return (a > b) ? a : b;
}

获取平衡因子

左子树树高减去右子树树高

int getB(Node* n)
{
    int leftHeight = (n->left) ? n->left->height : 0;
    int rightHeight = (n->right) ? n->right->height : 0;
    return leftHeight - rightHeight;
}

解决RR型不平衡，左旋

• 新的根节点为当前根节点的右子树
• 当前根结点的右子树的左子树，改变后为当前根结点的右子树（如果存在的话）
• 当前根节点变为新的根节点的左子树
• 最后要更新改变前后两个新旧根节点的树高，都等于1 + 左右子树的树高比较后的最大值

Node* leftRoatte(Node* n) // 左旋(RR)
{
    Node* newroot = n->right;
    Node* T2 = newroot->left;

    newroot->left = n;
    n->right = T2;

    // 更新树高
    n->height = 1 + Node::max(n->left ? n->left->height : 0, n->right ? n->right->height : 0);
    newroot->height = 1 + Node::max(newroot->left ? newroot->left->height : 0, newroot->right ? newroot->right->height : 0);
    return newroot;
}

解决LL型不平衡，右旋

实现方法与RR型大差不差

Node* rightRoatte(Node* n) // 右旋(LL)
{
    Node* newroot = n->left;
    Node* T2 = newroot->right;

    newroot->right = n;
    n->left = T2;

    // 更新树高
    n->height = 1 + Node::max(n->left ? n->left->height : 0, n->right ? n->right->height : 0);
    newroot->height = 1 + Node::max(newroot->left ? newroot->left->height : 0, newroot->right ? newroot->right->height : 0);
    return newroot;
}

结点的插入函数

• 如果传入进来的为空结点，即当前结点无数据，则需要把传入进来的用于排序和输出的值作为参数构造一个新的结点，然后返回出去
• 否则，则进行判断，判断当前结点的关键值与传入进来的关键值进行判断，如果传入进来的值比当前结点的值要小，则表示需要插入进当前结点的左子树，递归调用插入函数，参数是当前结点的左子树，关键值和数据域，返回后的结点赋值给当前结点的左子树
• 如果传入进来的关键值大于当前结点的关键值，则插入右子树，方法类似
• 如果当前结点的关键值等于传入进来的关键值，则表示这个值已经在树中存在，不需要插入，则直接将当前结点的返回出去
• 执行完插入结点的操作后，需要更新树高，方法一样
• 还需要更新平衡因子，因为当插入一个结点后，需要判断此时是否为平衡二叉树，根据不同结点的平衡因子进行不同的调整
• 首先获取当前根结点的平衡因子，如果当前根节点的平衡因子大于1，且当前结点的左子树根结点大于0，即他还有左子树，则为LL型，则调用右旋函数，返回调用后的结果
• 如果当前根节点的的平衡因子大于1，且当前根节点的左子树的根节点小于0，则其有右子树，为LR型，LR型首先要将当前结点的左子树为参数进行左旋，然后再将当前结点进行右旋，返回调用后的结果
• 其他两种情况类似
• 最后返回当前结点

Node* Insert(Node* now, int key, int data)
{
    if (now == nullptr)
    {
        return new Node(key, data);
    }

    if (key < now->val)
    {
        now->left = Insert(now->left, key, data);
    }
    else if (key > now->val)
    {
        now->right = Insert(now->right, key, data);
    }
    else
    {
        return now;  // Key already exists, don't insert duplicate
    }

    // 更新树高
    now->height = 1 + Node::max(now->left ? now->left->height : 0, now->right ? now->right->height : 0);

    // 获取当前结点的平衡因子
    int balance = getB(now);

    if (balance > 1 && getB(now->left) >= 0) // LL
    {
        return rightRoatte(now);
    }
    else if (balance > 1 && getB(now->left) < 0) // LR
    {
        now->left = leftRoatte(now->left);
        return rightRoatte(now);
    }
    else if (balance < -1 && getB(now->right) <= 0) // RR
    {
        return leftRoatte(now);
    }
    else if (balance < -1 && getB(now->right) > 0) // RL
    {
        now->right = rightRoatte(now->right);
        return leftRoatte(now);
    }

    return now;
}