做网站虚拟主机哪里有,在线支付网站建设,吉林 网站备案 照相,住房建设部网站C++学习笔记---022 C++之AVL树旋转操作的详细图解1、AVL树的简单介绍1.1、基本概念1.2、平衡因子1.3、AVL树的特性2、C++中pair的介绍2.1、定义和初始化2.2、访问元素2.3、作为容器的元素2.4、作为函数的返回值3、AVL树节点的定义4、AVL的插入规则探究5、AVL树的旋转操作5.1、R… C++学习笔记---022 C++之AVL树旋转操作的详细图解1、AVL树的简单介绍1.1、基本概念1.2、平衡因子1.3、AVL树的特性 2、C++中pair的介绍2.1、定义和初始化2.2、访问元素2.3、作为容器的元素2.4、作为函数的返回值 3、AVL树节点的定义4、AVL的插入规则探究5、AVL树的旋转操作5.1、RotateL左旋操作5.2、RotateR右旋操作5.3、不单纯的右边高或左边高的情况：LR双旋 或 RL双旋 6、AVL树的性能分析 C++之AVL树旋转操作的详细图解
前言： 前面篇章学习了C++对于map的认知和了解，接下来继续学习，C++的AVL树旋转插入操作等知识。 /知识点汇总/
1、AVL树的简单介绍
1.1、基本概念 AVL树（Adelson-Velsky和Landis发明的树）是一种自平衡的二叉搜索树（BST）。它在二叉搜索树的基础上添加了平衡的条件，以确保树的搜索、插入和删除操作都能保持较高的效率。 AVL树是一种特殊的二叉搜索树，其中每个节点的左子树和右子树的高度差（平衡因子）的绝对值不超过1。这个特性使得AVL树在插入或删除节点后，通过一系列的旋转操作可以保持其平衡性。 1.2、平衡因子 平衡因子：对于AVL树中的每个节点，其平衡因子定义为左子树的高度减去右子树的高度。平衡因子的值只能是-1、0或1。 1.3、AVL树的特性 它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1 / 0 / 1) 如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2n)，搜索时间复杂度O( l o g 2 n log_2 n log2n)。 2、C++中pair的介绍 在C++中，std::pair 是一个模板类，用于将两个值组合成一个单一的对象。这通常用于需要同时处理两个值的情况，例如在STL（Standard Template Library）中的 std::map，其元素就是键值对（key-value pairs）。 2.1、定义和初始化 可以直接使用花括号初始化一个 std::pair 对象，或者使用 make_pair 函数来创建。 std::pairint, std::string p1(1, "one"); // 直接初始化
std::pairint, std::string p2 = {2, "two"}; // 使用花括号初始化
std::pairint, std::string p3 = std
