AVL tree基本概念AVL树前提是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。平衡因子BF（balance Factor）：二叉树结点的左子树深度与右子树深度的值，AVL树上所有节点的BF只能是-1、0、1，如果二叉树上有一个节点的BF的绝对值大于1，那么这个二叉树就是不平衡的。最小不平衡子树：距离插入节点最近的，且平衡因子的绝对值 …
avl树
书节上回，我们接着聊二叉树，N叉树，以及树的存储。01、满二叉树如果一个二叉树，除最后一层节点外，每一层的节点数都达到最大值，即每个节点都有两个子节点，同时所有叶子节点都在最后一层，则这个二叉树为满二叉树。因此可以得到满二叉树有以下性质：（1）树的最大层数为k(k>=0，即层数从0开始),则第i层的节点总数为2^i，树的叶子节点总数为2^k，树的总节点 …
二叉树是一种常见的数据结构，它是由节点组成的一种树形结构，其中每个节点最多有两个子节点。二叉树的一个节点通常包含三部分：存储数据的变量、指向左子节点的指针和指向右子节点的指针。二叉树可以用于多种算法和操作，如搜索、排序和遍历。在这里插入图片描述二叉树遍历遍历方式 顺序 C#递归实现核心代码前序遍历 根 → 左 → 右 Console.Write(root.v …
数据结构 --- B树在我前面几篇文章中介绍了一系列自平衡二叉树，今天我们来学习一个特殊类型的自平衡搜索树，但它不是二叉树，它的每个节点可以存储超过一个key值，你可以认为它是一颗二叉搜索树的广义形式。这就是B树。下图所示的就是一颗B树。前面我们学习的自平衡二叉树，如AVL树，红黑树性能都不错，为什么还要B树呢？假设你要开发一个操作系统，对磁盘的管理是操作系 …
AVL树是一种自平衡二叉搜索树，它的名称来自于它的发明者Adelson-Velsky和Landis。AVL树的特点是每个节点的左子树和右子树的高度最多相差1，即任意节点的左子树和右子树的高度差的绝对值不超过1。AVL树的自平衡性质是通过对树进行旋转操作来实现的。当插入或删除一个节点后，如果AVL树不满足平衡条件，就需要进行旋转操作来调整树的结构，使之重新满足 …
前言索引，相信大多数人已经相当熟悉了，很多人都知道 MySQL 的索引主要以 B+ 树为主，但是要问到为什么用 B+ 树，恐怕很少有人能把前因后果讲述完整。本文就来从头到尾介绍下数据库的索引。索引是一种数据结构，用于帮助我们在大量数据中快速定位到我们想要查找的数据。索引最形象的比喻就是图书的目录了。注意这里的大量，数据量大了索引才显得有意义，如果我想要在 [ …
前言在《一文彻底掌握二叉查找树，非史上最全总结（多图，附代码） 》我们讲了二叉查找树，在文章的最后我们也提到了，二叉查找树查找的效率受到树的深度的影响，最坏情况是O(N)。而二叉查找树的深度是根据数据插入的顺序不同而表现出不同的。那么有没有可能让树的深度尽可能低，从而提高我们查询的效率呢？答案就是今天要讲的平衡二叉树（AVL树）。定义AVL树是二叉查找树的一 …
AVL树比红黑树保持更加严格的平衡。AVL树中从根到最深叶的路径最多为~1.44 lg（n + 2），而在红黑树中最多为~2 lg（n + 1）。因此，在AVL树中查找通常更快，但这是以更多旋转操作导致更慢的插入和删除为代价的。因此，如果您希望查找次数主导树的更新次数，请使用AVL树。AVL以及RedBlack树是高度平衡的树数据结构。它们非常相似，真正的区 …
- 1