1. Toy模板网首页
  2. > Toy博客

数据结构07：查找[C++][平衡二叉排序树AVL]

7月前 作者：梅头脑_ 分类：Toy博客 阅读(35) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构07：查找[C++][平衡二叉排序树AVL]。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构07：查找[C++][平衡二叉排序树AVL]

图源：文心一言

考研笔记整理1w+字，小白友好、代码可跑，请小伙伴放心食用~~🥝🥝

第1版：查资料、写BUG、画导图、画配图~🧩🧩

参考用书：王道考研《2024年 数据结构考研复习指导》

参考用书配套视频：7.3_2 平衡二叉树_哔哩哔哩_bilibili

特别感谢： Chat GPT老师、文心一言老师~

📇目录

📇目录

🦮思维导图 

🧵基本概念

⏲️定义

🌰推算举栗

⌨️代码实现

🧵分段代码

 🔯P0：调用库文件

 🔯P1：定义结点

 🔯P2：读取、写入结点的高度

 🔯P3：计算结点的平衡因子

 🔯P4：结点旋转操作

 🔯P5：调整平衡操作 

 🔯P6：插入结点

 🔯P0-P6附录：构造二叉树

 🔯P7：寻找最小结点

 🔯P8：结点删除

 🔯P9：树的遍历

 🔯P10：main函数

🧵完整代码

 🔯P0：完整代码

 🔯P1：执行结果

🔚结语

🦮思维导图 

数据结构07：查找[C++][平衡二叉排序树AVL]

备注：

  • 思维导图为整理王道教材第7章 查找的所有内容；
  • 本篇仅涉及到平衡二叉排序树（AVL）的代码；
  • 系列博文有朴素二叉排序树的说明🌸数据结构07：查找[C++][朴素二叉排序树BST]，后期会在博文列表中整理红黑树的相关内容[交可爱Ada小助手布置的红黑树作业]，也可能会增加B树、线性查找的相关内容~ //咳咳，上篇博文800阅读+2个赞+2个收藏足以让一个菜鸟博主开心得老~泪~纵~横~了~~

🧵基本概念

⏲️定义

  • 平衡二叉排序树，若树非空，满足下列特性：
    • 是一棵朴素二叉排序树🌸数据结构07：查找[C++][朴素二叉排序树BST]；
    • 在插入和删除结点时，要保证任意结点的左、右子树高度差的绝对值不能超过1。

树的插入操作：

  • 与结点进行比较，小于则向左子树遍历，大于则向右子树遍历，直到遍历为空结点时，为叶子结点的预插入路径。
  • 需要检查插入结点后是否会导致树不平衡。如果导致不平衡，需要调整子树的形态，直到其满足平衡二叉树定义为止。

 平衡树的定义，可见🌸数据结构05：树与二叉树[C++]

🌰推算举栗

  • 输入序列为{15、3、7、10、9、8}：
    • 插入结点时，若不调整平衡度，有时容易形成度为1的长树，如左图；
    • 插入结点时，若调整平衡度，可每次近似形成度为2的宽树，如右图~

数据结构07：查找[C++][平衡二叉排序树AVL]

// 备注：至于左侧这棵树调整为右侧这棵树的过程，我们会在本博文代码块“插入”操作中介绍~ 

  • ASL：平均查找长度，计算方式为 Σ（第 i 层结点数 x i 的层高）/ （结点个数），表示整棵树所有查找过程中，进行关键字比较次数的平均值~
  • 通过图中比较，可知：
    • 左侧树的查找：接近链表，与顺序查找相似，时间复杂度近似O(n)；
    • 右侧树的查找：接近平衡树，与折半查找相似，时间复杂度近似O(log n)；
  • 因此，朴素二叉排序树的查找的时间复杂度接近O(log n)~

下面我们以图中左侧的小树为例，说明如何创建及遍历平衡二叉排序树~

数据结构07：查找[C++][平衡二叉排序树AVL]

图源：文心一言

⌨️代码实现

🧵分段代码

 🔯P0：调用库文件

  • 输入输出流文件iostream{本代码用于输入与输出}；
  • 动态数组的向量文件vector{本代码用于创建树结点的动态数组}；
  • 基础算法函数文件algorithm{本代码用于计算比较结点子树的高度}~
#include <iostream>
#include <vector>
#include <algorithm>

 🔯P1：定义结点

相比朴素二叉排序树，平衡二叉排序树需要增加结点的1个属性height：以当前结点为根结点的子树高度，以保证树的平衡性~

struct AVLNode {
    int data;    //数据域
    int height;       //子树高度
    AVLNode* left;    //左孩子指针
    AVLNode* right;   //右孩子指针

    AVLNode(int value) : data(value), height(1), left(nullptr), right(nullptr) {}
};    //将构造函数的参数value赋给data，height初始化为1，左left、右孩子right置空

树的高度计算有点类似于这样子：查询左、右子树的高度，选择较高的子树+1作为本结点的高度~

数据结构07：查找[C++][平衡二叉排序树AVL]

 🔯P2：读取、写入结点的高度

  • 读取树的高度：查询结点中的node属性~
  • 写入树的高度：查询左子树的高度与右子树的高度，左、右子树中更高的值，并+1返回到本结点的高度~
// 读取结点的高度
int getHeight(AVLNode* node) {
    if (node == nullptr)
        return 0;
    return node->height;    //查询结点node中height属性的高度
}

// 更新结点的高度
void updateHeight(AVLNode* node) {
    if (node == nullptr)
        return;
    node->height = std::max(getHeight(node->left), getHeight(node->right)) + 1;    //将左子树、右子树中更高的height赋值到当前结点
}

 🔯P3：计算结点的平衡因子

  • 结点平衡因子 = 左子树高度 - 右子树高度；
int getBalanceFactor(AVLNode* node) {
    if (node == nullptr)
        return 0;
    return getHeight(node->left) - getHeight(node->right);    //返回左子树高度-右子树高度
}

 🔯P4：结点旋转操作

当子树的高度不平衡时（子树的平衡度>|1|），会出现度为1的现象，需要对树进行调整，目的是让树变宽；而平衡调整的基本操作是旋转，如下——

  • 左子树不平衡：当前结点移动到右子树的位置，在图中类似于右旋的操作~
  • 右子树不平衡：当前结点移动到左子树的位置，在图中类似于左旋的操作~

如果我没有理解错的话，非常简单版本的左旋、右旋，大概是这样的——

数据结构07：查找[C++][平衡二叉排序树AVL]

注意：括号内是平衡因子，计算公式=左子树高-右子树高~

// 右旋操作
AVLNode* rotateRight(AVLNode* node) {
    AVLNode* leftChild = node->left;    //定义左孩子结点
    node->left = leftChild->right;    //将当前结点的左指针指向左子结点的右指针
    leftChild->right = node;          //将左孩子结点的右指针指向当前结点

    updateHeight(node);            //更新当前结点高度
    updateHeight(leftChild);       //更新左子结点高度

    return leftChild;        //返回左子结点
}

// 左旋操作
AVLNode* rotateLeft(AVLNode* node) {
    AVLNode* rightChild = node->right;    //定义右孩子结点
    node->right = rightChild->left;    //将当前结点的右指针指向右子结点的左指针
    rightChild->left = node;           //将右孩子结点的左指针指向当前结点

    updateHeight(node);            //更新当前结点高度
    updateHeight(rightChild);      //更新右子结点高度

    return rightChild;       //返回右子结点
}

 🔯P5：调整平衡操作 

封装旋转的操作以后，此处我们正式介绍一下，当树出现不平衡时应该怎么调整~

因为是二叉树，只有两个孩子，所以插入结点可以汇总为四种情况——

  • 左左型：插入到结点左子树的左子树，导致不平衡，需要右旋；
  • 左右型：插入到结点左子树的右子树，导致不平衡，需要先左旋后右旋；
  • 右左型：插入到结点右子树的左子树，导致不平衡，需要先右旋后左旋；
  • 右右型：插入到结点右子树的右子树，导致不平衡，需要左旋；

考虑到左左型、右右型互为镜像操作 ，左右型、右左型互为镜像操作，此处以左左型与左右型举栗简单说明树的旋转调整过程~

左左型举栗：以下图为例，稍微复杂一点的左左型树，例如结点1插在结点2的左孩子导致不平衡，根结点向右旋转的操作分为3步：

  • 结点4挂到结点5的左孩子；
  • 结点5挂到结点3的右孩子；
  • 更新子树高度，返回根结点~

数据结构07：查找[C++][平衡二叉排序树AVL]

 以上都是调用P4右旋结点的操作完成~

注意：此处新增结点无论是挂在结点2的左孩子或是右孩子，都属于左左型；根据二叉排序树的性质，挂在结点2的左孩子数值m满足“m<2”，挂在结点2右孩子数值n满足“2<n<3”~

左右型举栗：以下图为例，稍微复杂一点的左右型树，例如结点3插在结点4的左孩子导致不平衡，需要根结点的左孩子先向左旋转，根结点再向右旋转：

  • 结点2左旋，使结点4可以挂在结点5的下方，具体操作如下：
    • 结点3挂到结点2的右孩子；
    • 结点2挂到结点4的左孩子；
    • 结点4挂到结点5的左孩子；
  • 结点5右旋，使整棵树达到平衡，此处操作同左左型旋转~
  • 更新子树高度，返回根结点~

数据结构07：查找[C++][平衡二叉排序树AVL]

注意：此处新增结点无论是挂在结点4的左孩子或是右孩子，都属于左右型；根据二叉树的性质，挂在结点4的左孩子数值m满足“2<m<4”，挂在结点4右孩子数值n满足“4<n<5”~

// 平衡操作
AVLNode* balanceNode(AVLNode* node) {
    if (node == nullptr)
        return nullptr;

    updateHeight(node);

    // 检查平衡因子
    int balanceFactor = getBalanceFactor(node);

    // 左左型，进行右旋
    if (balanceFactor > 1 && getBalanceFactor(node->left) >= 0)
        return rotateRight(node);

    // 右右型，进行左旋
    if (balanceFactor < -1 && getBalanceFactor(node->right) <= 0)
        return rotateLeft(node);

    // 左右型，先左旋再右旋
    if (balanceFactor > 1 && getBalanceFactor(node->left) < 0) {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }

    // 右左型，先右旋再左旋
    if (balanceFactor < -1 && getBalanceFactor(node->right) > 0) {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }

    // 结点平衡，无需调整
    return node;
}

 🔯P6：插入结点

同朴素二叉树，采用递归的方式创建树，插入的结点通常为叶节点，然后完成调整平衡：

  • 若二叉排序树为空，则创建根结点；若结点为空，则插入结点。
  • 若二叉树不为空：
    • 关键字 = 根结点值，树中已有此元素；
    • 关键字＜根结点值，继续遍历左子树；
    • 关键字＞根结点值，继续遍历右子树。
AVLNode* insertNode(AVLNode* root, int data) {
    if (root == nullptr)
        return new AVLNode(data);

    if (data < root->data)
        root->left = insertNode(root->left, data);
    else if (data > root->data)
        root->right = insertNode(root->right, data);
    else
        return root; // 重复值，不进行插入

    return balanceNode(root);
}

 🔯P0-P6附录：构造二叉树

本来想封装个构造二叉树的函数，但是封装函数在调用插入结点函数时一直在报奇怪的编译错误，因此本次代码在main中写入，实际操作就是把一个数组的内的元素分别执行插入结点的操作~

    AVLNode* root = nullptr;
    std::vector<int> data = {15, 3, 7, 10, 9, 8};

    // 插入结点
    for (int i = 0; i < data.size(); i++) {
        root = insertNode(root, data[i]);
    }

具体的创建过程嗯...大概是下图这样的（括号内依然为平衡因子）~

数据结构07：查找[C++][平衡二叉排序树AVL]

 🔯P7：寻找最小结点

利用二叉排序树左<根<右的性质，采用递归方式一直向左寻找，就可以找到最小值结点~

AVLNode* findMinNode(AVLNode* node) {
    if (node == nullptr || node->left == nullptr)    //如果结点或其左孩子不为空
        return node;    //返回结点
    return findMinNode(node->left);    //否则，递归调用本函数向左查询
}

 🔯P8：结点删除

传入树的根结点root和关键字data，此处偷懒采用递归的方式删除 {执行效率很低，胜在代码少好理解，不然就又要人工左旋、右旋，如果不平衡性向上传导又得旋，旋转这么多，实在是太太太头晕啦😢😢} ，可分为以下4种情况考虑——

// PS：考研的同学可以参考王道视频，我记得好像是有删除的单独章节说明...如果需要我整理非递归删除的话也可以在评论区留言，有时间我试试...

  • 特殊情况：
    • 根结点为空，则直接返回空指针；
  • 删除的数据 < 根节点：
    • 递归调用deleteNode函数，将左子树作为新的根节点进行操作；
  • 删除的数据 > 根节点：
    • 递归调用deleteNode函数，将右子树作为新的根节点进行操作；
  • 删除的数据 = 根节点：
    • 树仅有根结点，直接删除，将根指针设为空指针；
    • 树仅有左孩子结点，交换与左孩子结点的位置，删除左孩子结点；
    • 树仅有右孩子结点，交换与右孩子结点的位置，删除右孩子结点；
    • 树具有双子树结点，找到右子树中的最小值节点，将其值赋给当前根节点。然后递归调用deleteNode函数，在右子树中删除最小值节点。
  • 执行删除后，使用balance函数调整平衡。 
AVLNode* deleteNode(AVLNode* root, int data) {
    if (root == nullptr)    //根结点为空
        return root;

    if (data < root->data)    //删除数据 < 根结点
        root->left = deleteNode(root->left, data);    //左子树递归调用deletenode函数
    else if (data > root->data)    //删除数据 > 根结点
        root->right = deleteNode(root->right, data);    //右子树递归调用deletenode函数
    else {    //删除数据 = 根结点
        if (root->left == nullptr && root->right == nullptr) {    //仅有根结点
            delete root;
            root = nullptr;
        } else if (root->left == nullptr) {    //根结点仅有右子树
            AVLNode* temp = root;
            root = root->right;    //交换根结点与右子树
            delete temp;    //删除根结点
        } else if (root->right == nullptr) {   //根结点仅有左子树
            AVLNode* temp = root;
            root = root->left;    //交换根结点与左子树
            delete temp;    //删除根结点
        } else {    //根结点具有双子树
            AVLNode* minRight = findMinNode(root->right);    //寻找右子树的最小值
            root->data = minRight->data;    //右子树的最小值替换根结点
            root->right = deleteNode(root->right, minRight->data);    //右子树递归调用deletenode函数
        }
    }

    return balanceNode(root);    //执行平衡子树的操作
}

 🔯P9：树的遍历

传入树的根结点内存地址，由于二叉树遵循：“左＜根＜右” 的原则，因此可以通过二叉树的中序遍历完成，此处采用递归方式完成~

void inOrderTraversal(AVLNode* root) {
    if (root == nullptr)
        return;

    InOrderTraversal(root->lchild);    //遍历左子树

    std::cout << root->data << " ";    //输出当前结点的值

    InOrderTraversal(root->rchild);    //遍历右子树
}

敲黑板中序遍历这个已经写过很多次此处不再赘述了~ 🌸数据结构05：树与二叉树[C++]

 🔯P10：main函数

main函数除了P0~P9的函数调用，就创建了1棵树，以及示意性地增加删除结点的操作~

int main() {
    AVLNode* root = nullptr;
    std::vector<int> data = {15, 3, 7, 10, 9, 8};    //树中结点

    // 以插入结点的方式创建树
    for (int i = 0; i < data.size(); i++) {
        root = insertNode(root, data[i]);
    }

    // 中序遍历输出
    std::cout << "中序遍历结果: ";
    inOrderTraversal(root);
    std::cout << std::endl;

    // 删除结点7
    root = deleteNode(root, 7);

    // 中序遍历输出
    std::cout << "删除结点后的中序遍历结果: ";
    inOrderTraversal(root);
    std::cout << std::endl;

    return 0;
}

🧵完整代码

 🔯P0：完整代码

按照惯例，为了凑本文的字数，我这里贴一下整体的代码，删掉了细部注释~🫥🫥

// 头文件
#include <iostream>
#include <vector>
#include <algorithm>

// 二叉平衡树结点定义与初始化
struct AVLNode {
    int data;
    int height;
    AVLNode* left;
    AVLNode* right;

    AVLNode(int value) : data(value), height(1), left(nullptr), right(nullptr) {}
};

// 读取结点的高度
int getHeight(AVLNode* node) {
    if (node == nullptr)
        return 0;
    return node->height;
}

// 写入结点的高度
void updateHeight(AVLNode* node) {
    if (node == nullptr)
        return;
    node->height = std::max(getHeight(node->left), getHeight(node->right)) + 1;
}

// 计算结点的平衡因子
int getBalanceFactor(AVLNode* node) {
    if (node == nullptr)
        return 0;
    return getHeight(node->left) - getHeight(node->right);
}

// 右旋操作
AVLNode* rotateRight(AVLNode* node) {
    AVLNode* leftChild = node->left;
    node->left = leftChild->right;
    leftChild->right = node;

    updateHeight(node);
    updateHeight(leftChild);

    return leftChild;
}

// 左旋操作
AVLNode* rotateLeft(AVLNode* node) {
    AVLNode* rightChild = node->right;
    node->right = rightChild->left;
    rightChild->left = node;

    updateHeight(node);
    updateHeight(rightChild);

    return rightChild;
}

// 平衡操作
AVLNode* balanceNode(AVLNode* node) {
    if (node == nullptr)
        return nullptr;

    updateHeight(node);

    int balanceFactor = getBalanceFactor(node);

    if (balanceFactor > 1 && getBalanceFactor(node->left) >= 0)
        return rotateRight(node);

    if (balanceFactor < -1 && getBalanceFactor(node->right) <= 0)
        return rotateLeft(node);

    if (balanceFactor > 1 && getBalanceFactor(node->left) < 0) {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }

    if (balanceFactor < -1 && getBalanceFactor(node->right) > 0) {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }

    return node;
}

// 插入结点
AVLNode* insertNode(AVLNode* root, int data) {
    if (root == nullptr)
        return new AVLNode(data);

    if (data < root->data)
        root->left = insertNode(root->left, data);
    else if (data > root->data)
        root->right = insertNode(root->right, data);
    else
        return root; // 重复值，不进行插入

    return balanceNode(root);
}

// 查找最小结点
AVLNode* findMinNode(AVLNode* node) {
    if (node == nullptr || node->left == nullptr)
        return node;
    return findMinNode(node->left);
}

// 删除结点
AVLNode* deleteNode(AVLNode* root, int data) {
    if (root == nullptr)
        return root;

    if (data < root->data)
        root->left = deleteNode(root->left, data);
    else if (data > root->data)
        root->right = deleteNode(root->right, data);
    else {
        if (root->left == nullptr && root->right == nullptr) {
            delete root;
            root = nullptr;
        } else if (root->left == nullptr) {
            AVLNode* temp = root;
            root = root->right;
            delete temp;
        } else if (root->right == nullptr) {
            AVLNode* temp = root;
            root = root->left;
            delete temp;
        } else {
            AVLNode* minRight = findMinNode(root->right);
            root->data = minRight->data;
            root->right = deleteNode(root->right, minRight->data);
        }
    }

    return balanceNode(root);
}

// 中序遍历
void inOrderTraversal(AVLNode* root) {
    if (root == nullptr)
        return;

    inOrderTraversal(root->left);
    std::cout << root->data << " ";
    inOrderTraversal(root->right);
}

int main() {
    AVLNode* root = nullptr;
    std::vector<int> data = {15, 3, 7, 10, 9, 8};

    for (int i = 0; i < data.size(); i++) {
        root = insertNode(root, data[i]);
    }

    std::cout << "中序遍历结果: ";
    inOrderTraversal(root);
    std::cout << std::endl;

    root = deleteNode(root, 7);

    std::cout << "删除结点后的中序遍历结果: ";
    inOrderTraversal(root);
    std::cout << std::endl;

    return 0;
}

 🔯P1：执行结果

运行结果如下图所示~

数据结构07：查找[C++][平衡二叉排序树AVL]

🔚结语

博文到此结束，写得模糊或者有误之处，欢迎小伙伴留言讨论与批评，督促博主优化内容，不限于以下内容~😶‍🌫️😶‍🌫️

  • 有错误：这段注释南辕北辙，理解错误，需要更改~
  • 难理解：这段代码雾里看花，需要更换排版、增加语法、逻辑注释或配图~
  • 不简洁：这段代码瘠义肥辞，好像一座尸米山，需要更改逻辑；如果是C++语言，调用某库某语法还可以简化~
  • 缺功能：这段代码败絮其中，能跑，然而不能用，想在实际运行或者通过考试需要增加功能~
  • 跑不动：这不可能——好吧，如果真不能跑，告诉我哪里不能跑我再回去试试...

博文若有帮助，欢迎小伙伴动动可爱的小手默默给个赞支持一下~🌟🌟文章来源地址https://www.toymoban.com/news/detail-502021.html

到了这里，关于数据结构07：查找[C++][平衡二叉排序树AVL]的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构奇妙旅程之二叉平衡树进阶---AVL树

    数据结构奇妙旅程之二叉平衡树进阶---AVL树

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好，我是xiaoxie.希望你看完之后,有不足之处请多多谅解，让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页：xiaoxieʕ̯

    2024年03月13日
    浏览(73)
  • 【数据结构】平衡二叉搜索树（AVL树）——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改

    【数据结构】平衡二叉搜索树（AVL树）——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改

      为什么要引入平衡二叉搜索树？   在之前我们学习了二叉搜索树，二叉搜索树的结构类似于一个倒置的树，而左子树的值小于根节点的值，右节点的值大于根节点的值，这种结构使得二叉搜索树在处理有序数据时非常高效。但是如果 在传入的数据为有序或接近有序，

    2024年02月07日
    浏览(34)
  • 【数据结构】二叉查找树和平衡二叉树，以及二者的区别

    【数据结构】二叉查找树和平衡二叉树，以及二者的区别

    目录 1、二叉查找树 1.1、定义  1.2、查找二叉树的优点  1.2、查找二叉树的弊端 2、平衡二叉树 2.1、定义 2.2、 实现树结构平衡的方法（旋转机制） 2.2.1、左旋 2.2.2、右旋 3、总结        二叉查找树又名二叉排序树，亦称二叉搜索树。是每个结点最多有两个子树的树结构

    2024年02月20日
    浏览(34)
  • C++数据结构之平衡二叉搜索树（一）——AVL的实现（zig与zag/左右双旋/3+4重构）

    C++数据结构之平衡二叉搜索树（一）——AVL的实现（zig与zag/左右双旋/3+4重构）

    本文是介绍众多平衡二叉搜索树（BBST）的第一篇——介绍AVL树。故先来引入BBST的概念。由于上一篇介绍的二叉搜索树（BST）在极度退化的情况下，十分不平衡，不平衡到只朝一侧偏，成为一条链表，复杂度可达 O ( n ) O(n) O ( n ) ，所以我们要在“平衡”方面做一些约束，以防

    2024年02月13日
    浏览(24)
  • 数据结构【DS】Ch7 查找：平衡二叉树

    数据结构【DS】Ch7 查找：平衡二叉树

    2024年01月20日
    浏览(29)
  • Java学数据结构（2）——树Tree & 二叉树binary tree & 二叉查找树 & AVL树 & 树的遍历

    Java学数据结构（2）——树Tree & 二叉树binary tree & 二叉查找树 & AVL树 & 树的遍历

    1.树的出现：解决链表线性访问时间太慢，树的时间复杂度O(logN)； 2.二叉树的定义，最多两个儿子节点； 3.二叉查找树，左小，右大，中居中；remove方法，两种，只有一个儿子节点，有两个儿子节点； 4.AVL树，在二叉查找树基础上加平衡条件，旋转方法，单旋转，双旋转；

    2024年02月10日
    浏览(39)
  • 【数据结构】二叉排序树——平衡二叉树的调整

    【数据结构】二叉排序树——平衡二叉树的调整

    参考视频： 懒猫老师-数据结构-(59)平衡二叉树【互动视频】 （1）什么是平衡二叉树 平衡二叉树（Balanced Binary Tree）是一种特殊的二叉查找树，它的目的是保持树的高度尽量平衡，以保证查找、插入、删除等操作的时间复杂度为 O(log n)。 常见的平衡二叉树算法包括 AVL 树、红

    2024年02月04日
    浏览(32)
  • 数据结构-各种树（二叉树、二叉查找树、平衡二叉树、红黑树、B树、B+树）

    数据结构-各种树（二叉树、二叉查找树、平衡二叉树、红黑树、B树、B+树）

    概念：二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树 特点：每个

    2024年02月09日
    浏览(36)
  • Java常见的数据结构：栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树

    Java常见的数据结构：栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树

    数据结构是计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。 通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率 栈 队列 数组 链表 二叉树 二叉查找树 平衡二叉树 红黑树... 后进先出，先进后出 数据进入栈模型的过程称为

    2024年02月07日
    浏览(28)

  • 数据结构课设（五）二叉排序树与平衡二叉树的实现

    假定二叉排序树与平题所处理数据均为整型。分别采用二叉链表和顺序表作存储结构,实现对二叉衡二叉树的操作。具体要求如下: （1）用二叉链表作存储结构: ①读入一个整数序列L(要求该整数序列从磁盘文件读取),生成一棵二叉排序树②对二叉排序树T作中序遍历，输出结果

    2024年02月12日
    浏览(31)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包