数据结构中的 AA 树

2025年4月20日 | 阅读 13 分钟

AA 树简介

由 **Arne Anderson** 发明的 **AA 树** 是一种自平衡二叉搜索树，旨在简化和加速实现。在二叉搜索树 (BST) 中，每个节点最多可以有两个子节点，并且父节点左侧的每个节点都小于父节点，右侧的每个节点都大于父节点。BST 的问题在于，它们会随着插入和删除的集合而**失衡**，导致搜索、插入和删除等操作的性能下降。通过旋转和保持简单结构，AA 树可以保持**高性能**。

基本属性

AA 树通过几个关键概念与其他二叉搜索树区分开来。它们是：

层级：AA 树的每个节点都有一个附加属性**“层级”**（类似于**红黑树**中的“**黑高**”概念）。叶子节点的层级为 1，非叶子节点的层级比其子节点层级的最小值大 1。
倾斜：这种情况发生在右子节点的层级与其父节点相同，这在 AA 树中是不允许的。为了纠正倾斜，会执行左旋转。
分裂：当一个节点在同一层级有两个右**子节点**时，就会出现此问题。为了纠正分裂，会执行右旋转，并增加节点的层级。

方法一：递归方法

在这种方法中，**插入、删除和遍历**等基本操作都是递归执行的。每个操作都会接受树，递归地遍历它，对节点进行分层，调整它们，并在满足 AA 树条件时实现倾斜和分裂。这是最简单的方法，尤其适用于小型到中型树。

程序

#include <iostream>
using namespace std;
// Node structure for the AA tree
struct Node {
    int key;        // Key value
    int level;      // Level of the node
    Node *left, *right; // Pointers to left and right children
    // Constructor to initialize a node with a key
    Node(int k) : key(k), level(1), left(nullptr), right(nullptr) {}
};
class AATree {
private:
    Node *root; // Pointer to the root of the tree
    // Skew operation to maintain the AA tree properties
    Node* skew(Node *node) {
        if (node == nullptr) return nullptr;
        if (node->left != nullptr && node->left->level == node->level) {
            Node *leftChild = node->left;
            node->left = leftChild->right;
            leftChild->right = node;
            return leftChild;
        }
        return node;
    }
    // Split operation to maintain the AA tree properties
    Node* split(Node *node) {
        if (node == nullptr) return nullptr;
        if (node->right != nullptr && node->right->right != nullptr && node->right->right->level == node->level) {
            Node *rightChild = node->right;
            node->right = rightChild->left;
            rightChild->left = node;
            rightChild->level++;
            return rightChild;
        }
        return node;
    }
    // Recursive function to insert a node into the tree
    Node* insertNode(Node *node, int key) {
        if (node == nullptr) {
            return new Node(key); // Create a new node if the current node is null
        }
        if (key < node->key) {
            node->left = insertNode(node->left, key); // Insert into the left subtree
        } else if (key > node->key) {
            node->right = insertNode(node->right, key); // Insert into the right subtree
        } else {
            // Duplicate keys are not allowed
            return node;
        }
        // Rebalance the tree after insertion
        node = skew(node);
        node = split(node);
        return node;
    }
    // Recursive function to remove a node with a given key from the tree
    Node* removeNode(Node *node, int key) {
        if (node == nullptr) {
            return nullptr; // Key not found
        }
        if (key < node->key) {
            node->left = removeNode(node->left, key); // Remove from the left subtree
        } else if (key > node->key) {
            node->right = removeNode(node->right, key); // Remove from the right subtree
        } else {
            // Key found, perform deletion
            if (node->left == nullptr && node->right == nullptr) {
                delete node; // Node has no children
                return nullptr;
            } else if (node->left == nullptr) {
                Node *temp = node->right;
                delete node; // Node has only right child
                return temp;
            } else if (node->right == nullptr) {
                Node *temp = node->left;
                delete node; // Node has only left child
                return temp;
            } else {
                // Node has both left and right children
                Node *successor = node->right;
                while (successor->left != nullptr) {
                    successor = successor->left;
                }
                node->key = successor->key;
                node->right = removeNode(node->right, successor->key);
            }
        }
        // Rebalance the tree after deletion
        if (node != nullptr) {
            node = skew(node);
            node->right = skew(node->right);
            if (node->right != nullptr) {
                node->right->right = skew(node->right->right);
            }
            node = split(node);
            node->right = split(node->right);
        }
        return node;
    }
    // Recursive function to perform inorder traversal of the tree
    void inorderTraversal(Node *node) {
        if (node != nullptr) {
            inorderTraversal(node->left);
            cout << node->key << " ";
            inorderTraversal(node->right);
        }
    }
public:
    // Constructor to initialize an empty tree
    AATree() : root(nullptr) {}

    // Public function to insert a key into the tree
    void insert(int key) {
        root = insertNode(root, key);
    }
    // Public function to remove a key from the tree
    void remove(int key) {
        root = removeNode(root, key);
    }
    // Public function to perform inorder traversal of the tree
    void traverseInorder() {
        inorderTraversal(root);
    }
};
// Main function to test the AA tree implementation
int main() {
    AATree aaTree;
    // Insert some keys into the tree
    aaTree.insert(5);
    aaTree.insert(3);
    aaTree.insert(7);
    aaTree.insert(2);
    aaTree.insert(4);
    aaTree.insert(6);
    aaTree.insert(8);
    // Display the inorder traversal of the tree after insertion
    cout << "Inorder traversal of AA tree after insertion: ";
    aaTree.traverseInorder();
    cout << endl;
    // Remove a key from the tree
    aaTree.remove(3);
    // Display the inorder traversal of the tree after deletion
    cout << "Inorder traversal of AA tree after deletion: ";
    aaTree.traverseInorder();
    cout << endl;
    return 0;
}

输出

Inorder traversal of AA tree after insertion: 2 3 4 5 6 7 8 
Inorder traversal of AA tree after deletion: 2 4 5 6 7 8

说明

节点结构 (struct Node)

此结构模仿了 AA 树中的一个节点。

它包含三个主要属性：

key：节点键的值。
level：节点在树中的层级。
left 和 right：指向左右节点的指针。

构造函数使用提供的键初始化节点，并设置层级和子节点指针的默认值。

AATree 类

AA 树在此类中实现，并提供执行**插入、删除**和**遍历操作**的方法。

私有成员变量

root：树的根指针。

倾斜和分裂操作

**倾斜**和**分裂**，即私有成员，用于保持 AA 树的属性。skew 对给定节点执行倾斜操作，必要时调整树结构以保持层级顺序属性。split 对给定节点执行分裂操作，也重新排列树结构以维护层级顺序属性。

递归插入 (insertNode)

这个**私有成员函数**将一个带有指定键的新节点插入到**树中**。它利用递归来探索树并找到要插入的位置。然后，执行倾斜和分裂操作来重新平衡树。

递归方法

递归删除 (removeNode)

通过这个私有成员函数，可以从树中删除带有给定键的节点。它使用递归来查找要删除的节点，然后根据三种情况执行删除：节点没有子节点、节点只有一个父节点、链接具有其**后代**的子节点（由其后继替换），并在删除后通过执行倾斜和分裂操作来重新平衡树。

中序遍历 (inorderTraversal)

这个私有成员函数对树应用**中序遍历**。它递归地遍历左子树，然后访问当前节点，最后递归地遍历右子树。它遍历**节点**，并在打印**排序的**键的同时完成操作。

公共成员函数

insert：使用**insertNode**方法实现新键的插入。

remove：使用**removeNode**函数从树中删除一个权重。

traverseInorder：调用 `inorderTraversal` 函数来启动树的中序遍历。

主函数

在实例级别实例化 AATree 类。实际上，一些键将被从树中删除。输出是插入后的树的中序遍历。从树中删除一个键。显示删除后树的中序遍历。

复杂度分析

时间复杂度

插入

在 AA 树中，插入的时间复杂度为**O(log n)**，其中 n 是树中的节点数。这种**层次结构**源于初始时将根分成两部分，然后向下直到将新元素插入到叶子中，以及倾斜和分裂操作以确保 AA 树的属性得到维护。

删除

类似地，AA 树中删除的时间复杂度为**O(log(n)**，其中 n 表示树中的节点数。与插入类似，删除步骤是通过移动到存在要删除节点的根节点，并且**删除**会留下内部倾斜和分裂操作来保留 AA 树的属性。

遍历

**中序遍历**的时间复杂度为**O(n)**，n 是树中的节点数。这是因为在遍历过程中，树中的每个节点都必须只访问一次。

空间复杂度

所提供 AA 树的**空间复杂度**为**O(n)**，其中 n 是树中的节点数。这部分空间主要用于在内存中存储树节点。此外，插入和删除操作可能会导致递归函数调用，这会在调用堆栈上占用额外的内存。但是，总的空间复杂度仍然是**O(n)**。

方法二：迭代方法

这种方法避免了复制，并通过使用循环或**堆栈**或**队列**数据结构来**迭代**地执行基本操作。例如，在循环中，它需要调整节点。与递归方法相比，递归方法可能更复杂，但对于非常深的树可能更有效，因为递归调用的减少带来了开销的降低。

程序

#include <iostream>
#include <stack>
using namespace std;
// Node structure for the AA tree
struct Node {
    int key;
    int level;
    Node *left, *right;
    Node(int k) : key(k), level(1), left(nullptr), right(nullptr) {}
};
class AATree {
private:
    Node *root;
    // Skew operation to maintain the AA tree properties
    Node* skew(Node *node) {
        if (node == nullptr) return nullptr;
        if (node->left != nullptr && node->left->level == node->level) {
            Node *leftChild = node->left;
            node->left = leftChild->right;
            leftChild->right = node;
            return leftChild;
        }
        return node;
    }
    // Split operation to maintain the AA tree properties
    Node* split(Node *node) {
        if (node == nullptr) return nullptr;
        if (node->right != nullptr && node->right->right != nullptr && node->right->right->level == node->level) {
            Node *rightChild = node->right;
            node->right = rightChild->left;
            rightChild->left = node;
            rightChild->level++;
            return rightChild;
        }
        return node;
    }
public:
    AATree() : root(nullptr) {}
    // Iterative insertion method
    void insert(int key) {
        Node *newNode = new Node(key);
        if (root == nullptr) {
            root = newNode;
            return;
        }
        // Iterative insertion without recursion
        Node *current = root;
        stack<Node*> s;
        while (current != nullptr || !s.empty()) {
            while (current != nullptr) {
                s.push(current);
                current = current->left;
            }
            current = s.top();
            s.pop();
            if (key < current->key) {
                if (current->left == nullptr) {
                    current->left = newNode;
                    break;
                }
                current = current->left;
            } else if (key > current->key) {
                if (current->right == nullptr) {
                    current->right = newNode;
                    break;
                }
                current = current->right;
            } else {
                delete newNode;
                return; // Duplicate keys are not allowed
            }
        }
        // Rebalance the tree iteratively
        while (!s.empty()) {
            current = s.top();
            s.pop();
            current = skew(current);
            current = split(current);
            if (!s.empty()) {
                Node *parent = s.top();
                if (parent->left == current) {
                    parent->left = current;
                } else {
                    parent->right = current;
                }
            }
        }
        root = skew(root);
        root = split(root);
    }
    // Iterative deletion method
    void remove(int key) {
        // Empty tree
        if (root == nullptr) return;
        Node *current = root;
        Node *parent = nullptr;
        stack<Node*> s;
        // Search for the node to be deleted
        while (current != nullptr) {
            s.push(current);
            parent = current;
            if (key < current->key) {
                current = current->left;
            } else if (key > current->key) {
                current = current->right;
            } else {
                break; // Node found
            }
        }
        // Node not found
        if (current == nullptr) return;
        // Case 1: Node has no children
        if (current->left == nullptr && current->right == nullptr) {
            if (parent == nullptr) {
                delete root;
                root = nullptr;
            } else if (parent->left == current) {
                delete parent->left;
                parent->left = nullptr;
            } else {
                delete parent->right;
                parent->right = nullptr;
            }
        }
        // Case 2: Node has only one child (right child)
        else if (current->left == nullptr) {
            if (parent == nullptr) {
                root = current->right;
            } else if (parent->left == current) {
                parent->left = current->right;
            } else {
                parent->right = current->right;
            }
            delete current;
        }
        // Case 3: Node has only one child (left child)
        else if (current->right == nullptr) {
            if (parent == nullptr) {
                root = current->left;
            } else if (parent->left == current) {
                parent->left = current->left;
            } else {
                parent->right = current->left;
            }
            delete current;
        }
        // Case 4: Node has both left and right children
        else {
            Node *successor = current->right;
            s.push(successor);
            while (successor->left != nullptr) {
                successor = successor->left;
                s.push(successor);
            }
            current->key = successor->key;
            Node *successorParent = s.top();
            if (successorParent->left == successor) {
                successorParent->left = successor->right;
            } else {
                successorParent->right = successor->right;
            }
            delete successor;
            while (!s.empty()) {
                Node *node = s.top();
                s.pop();
                node = skew(node);
                node = split(node);
                if (!s.empty()) {
                    Node *parent = s.top();
                    if (parent->left == node) {
                        parent->left = node;
                    } else {
                        parent->right = node;
                    }
                }
            }
            root = skew(root);
            root = split(root);
        }
    }
    // Iterative inorder traversal method
    void traverseInorder() {
        stack<Node*> s;
        Node *current = root;
        while (current != nullptr || !s.empty()) {
            while (current != nullptr) {
                s.push(current);
                current = current->left;
            }
            current = s.top();
            s.pop();
            cout << current->key << " ";
            current = current->right;
        }
    }
    // Method to display the tree structure
    void display() {
        cout << "Inorder traversal of AA tree: ";
        traverseInorder();
        cout << endl;
    }
};
int main() {
    AATree aaTree;
    // Insert some keys into the tree
    aaTree.insert(6);
    aaTree.insert(3);
    aaTree.insert(4);
    aaTree.insert(2);
    aaTree.insert(10);
    aaTree.insert(15);
    // Display the tree structure after insertion
    cout << "After insertion:" << endl;
    aaTree.display();
    // Remove a key from the tree
    aaTree.remove(2);
    // Display the tree structure after deletion
    cout << "After deletion:" << endl;
    aaTree.display();
    return 0;
}

输出

After insertion:
Inorder traversal of AA tree: 2 10 15 3 4 6 
After deletion:
Inorder traversal of AA tree: 1 0 10 15 3 4 6

说明

AATree 类

它包括迭代插入（insert）、迭代删除（remove）、迭代**中序遍历**（traverseInorder）以及打印树的显示结构的过程。root 成员变量用于保存树的根节点的位置。

倾斜操作

skew 函数用于执行倾斜操作以保持 AA 树的属性。它以一个节点作为输入，并在需要倾斜转换时执行。

分裂操作

负责分裂的方法确保了**AA 树**的特性。它需要一个节点（供进一步处理）。否则，它执行分裂转换。

迭代插入

AA 树通过 insert 方法扩展其新键。它使用递归树遍历、一个堆栈将相关节点压入堆栈，最后将节点插入到适当的位置。更新后，通过以**迭代方式**应用倾斜和分裂操作来重新平衡树。

迭代删除

remove 方法涉及从 AA 树中提取键。它使用堆栈递归地查找该键节点。它使用堆栈递归地查找该键节点。在此过程中，根据情况（无子节点、一个子节点或两个子节点），它会删除节点并使用倾斜和分裂操作以迭代方式重新平衡树。

迭代方法

该方法避免了**复制**，并通过使用循环或堆栈或队列数据结构来**迭代**地执行基本操作。例如，在循环中，它需要调整节点。与递归方法相比，递归方法可能更复杂，但对于非常深的树可能更有效，因为**递归调用的减少**带来了开销的降低。

迭代中序遍历

**traverseInorder** 方法在不使用递归函数的情况下执行树的中序遍历。它使用堆栈来记录遍历的节点，并按遍历的升序打印键。

结果

print 方法提供 AA 树的中序遍历，从而按排序顺序打印键。

主函数

在 main 函数中，代码创建了 **AATree 类的实例并将键插入到类中。它显示了**插入**发生时重新排列的树结构。接下来，它查找要从树中删除的键，然后显示删除后树的结构。

复杂度分析

时间复杂度

插入

**迭代插入**意味着插入以类似的方式进行，树被迭代遍历。作为**O(log n)**的平均复杂度，遍历过程所需的时间与树中的节点数 n 成正比。需要注意的另一件事是，使用倾斜和分裂操作重新平衡树都需要**O(log n**）时间。因此，插入的总时间复杂度等于**O(log n)**。

删除

就像插入一样，迭代删除的特点是迭代搜索要删除的节点，这需要平均 log n 的时间。删除节点并使用倾斜和分裂操作重新平衡树也需要**O(log n)**。因此，删除复杂度为**O(log n)**。

遍历

**迭代中序**遍历方法遍历树中的每个节点，每个节点只访问一次。因此，遍历操作的复杂度为**O(n)**，其中 n 是树中的节点数。

空间复杂度

该实现的**空间复杂度**主要包括用于迭代遍历和重新平衡操作的堆栈的空间。由于它用作节点指针，因此堆栈内存的最大大小与树的高度成正比。对于 AA 树，在最坏情况下，高度为**O(log n)**，其中 n 是节点总数。因此，该算法的实现具有**O(log n)**的空间复杂度。

下一个主题图数据结构

← 上一个下一个 →

我们提供所有技术（如 Java 教程、Android、Java 框架）的教程和面试问题

联系信息

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

hr@tpointtech.com

+91-9599086977

关注我们

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

数据结构中的 AA 树

AA 树简介

基本属性

方法一：递归方法

程序

说明

复杂度分析

方法二：迭代方法

程序

说明

复杂度分析

相关帖子

二叉树

二叉搜索树

AVL 树

红黑树

B 树

B+ 树

树 (数据结构)

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器