基于改进的AVL树的重复键值倒排索引的建立、使...

纸上谈兵：AVL树⼆叉搜索树的深度与搜索效率我们在中提到，⼀个有n个节点的⼆叉树，它的最⼩深度为log(n)，最⼤深度为n。

⽐如下⾯两个⼆叉树:深度为n的⼆叉树深度为log(n)的⼆叉树这两个⼆叉树同时也是⼆叉搜索树(参考)。

注意，log以2为基底。

log(n)是指深度的量级。

根据我们对深度的定义，精确的最⼩深度为floor(log(n)+1)。

我们将处于同⼀深度的节点归为⼀层。

如果除最后⼀层外的其他层都被节点填满时，⼆叉树有最⼩深度log(n)。

⼆叉搜索树的深度越⼩，那么搜索所需要的运算时间越⼩。

⼀个深度为log(n)的⼆叉搜索树，搜索算法的时间复杂度也是log(n)。

然⽽，我们在中已经实现的插⼊和删除操作并不能让保持log(n)的深度。

如果我们按照8，7，6，5，4，3，2，1的顺序插⼊节点，那么就是⼀个深度为n的⼆叉树。

那么，搜索算法的时间复杂度为n。

n和log(n)的时间复杂度意味着什么呢？时间复杂度代表了完成算法所需要的运算次数。

时间复杂度越⼩，算法的速度越快。

可以看到，随着元素的增加，log(n)的时间复杂度的增长要远⼩于n。

所以，我们⾃然希望⼆叉搜索树能尽可能保持log(n)的深度。

在上⾯深度为n的例⼦中，我们发现，每个节点只有左节点被填满。

树的每⼀层都有很多空位。

能不能尽可能减少每⼀层的空位呢？ (相应的，减少树的深度)“紧致”的树⼀种想法是先填满⼀层，再去填充下⼀层，这样就是⼀个完全⼆叉树(complete binary tree)。

这样的⼆叉树实现插⼊算法会⽐较复杂。

我们将介绍⼀种思路相似，但⽐较容易实现的树状数据结构——AVL树。

AVL树AVL树是根据它的发明者G. M. A delson-V elskii和E. M. L andis命名的。

它是⼀种特殊的⼆叉搜索树。

AVL树要求: 任⼀节点的左⼦树深度和右⼦树深度相差不超过1(空树的深度为0。

注意，有的教材中，采⽤了不同的深度定义⽅法，所以空树的深度为-1)下⾯是AVL树:AVL树的特性让⼆叉搜索树的节点实现平衡(balance)：节点相对均匀分布，⽽不是偏向某⼀侧。

r树索引的基本原理和算法-回复R树索引是一种用于高效检索空间数据的索引结构，它能够有效地支持范围查询和近邻查询等操作。

本文将从基本原理、算法以及具体使用方法等方面来介绍R树索引的工作原理。

R树索引是在B树的基础上进行改进而来的，主要用于处理多维空间数据，如地理信息系统、地图数据等。

R树索引的基本原理是通过构建一棵多叉树来组织空间数据，其中每个叶子结点代表一个空间对象，而每个非叶子结点代表这些对象的最小外包矩形（Minimum Bounding Rectangle，简称MBR）。

R树的基本结构类似于B树，但是在插入和删除操作时有所不同。

当需要插入一个新的空间对象时，R树会根据一定的策略选择一个合适的叶子结点将其插入其中。

如果插入导致某个结点的子结点数目超过了预定的上限，就需要进行结点的分裂操作。

而删除操作则是将叶子结点中的对象删除，并保持树的平衡。

R树的搜索操作也是非常高效的。

当需要查找某个范围内的空间对象时，可以首先从根结点开始搜索，逐级向下，只访问与范围相交的子结点，避免了不必要的比较操作，从而减少了搜索的时间复杂度。

除了范围查询，R树索引还能够支持近邻查询，即找出最接近给定点的对象。

这是通过使用一种特殊的搜索策略来实现的。

首先，在树的深度优先遍历过程中，对于每个子结点，计算其MBR与目标点的最小距离。

然后，根据距离的大小对子结点进行排序，使得距离最小的子结点排在前面。

最后，根据排序的顺序逐一访问子结点，找到最接近目标点的对象。

R树索引的算法包括构建和维护两个步骤。

构建过程通常从一个空的R树开始，逐步将空间对象插入其中，直到达到一定的填充因子。

在插入过程中，根据一定的规则选择合适的位置进行插入，并更新相关结点的MBR。

而维护过程则主要涉及结点的分裂和合并操作，以保持树的平衡性。

对于R树索引的具体使用方法，可以将空间数据结构化为层次化的树结构，每个结点代表一个矩形区域。

通过R树索引，可以快速地搜索和检索这些空间对象，提高查询的效率。

C平衡⼆叉树（AVL）创建和删除 AVL是最先发明的⾃平衡⼆叉查找树算法。

在AVL中任何节点的两个⼉⼦⼦树的⾼度最⼤差别为⼀，所以它也被称为⾼度平衡树，n个结点的AVL树最⼤深度约1.44log2n。

查找、插⼊和删除在平均和最坏情况下都是O（log n）。

增加和删除可能需要通过⼀次或多次树旋转来重新平衡这个树。

定义 ⽤LH，EH，RH分别表⽰左⼦树⾼，等⾼，右⼦树⾼，即平衡因⼦1、0、-1#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#define LH 1 // 左⾼#define EH 0 // 等⾼#define RH -1 // 右⾼typedef struct TreeNode{int data;int bf;struct TreeNode *left, *right;}TreeNode; 旋转处理 左旋和右旋，记住“左逆右顺”就可以/************************************************* 对以*p为根的⼆叉排序树作右旋处理，处理之后p指向新的树根结点，* A B* / / \* B 旋转后变为 C A* / \ /* C D D* 即旋转处理之前的左⼦树的结点。

************************************************/void r_rotate(TreeNode **p){TreeNode *l = (*p)->left;(*p)->left = l->right;l->right = (*p);*p = l;}/************************************************* 对以*p为根的⼆叉排序树作左旋处理，处理之后p指向新的树根结点，* A B* \ / \* B 旋转后变为 A D* / \ \* C D C* 即旋转处理之前的右⼦树的结点。

Java篇：树和MapJava篇：树和Map每次涉及到集合就想将Map拎出来单独看看，每次开始了解⼜似乎觉得没必要，⽽每次想到相关问题⼜只有隐隐约约的印象。

⽽提到Map就会想到TreeMap，就会想到红⿊树。

有关于树的概念我也总是这个状态，所以⼀起拎出来看看总结下加深印象。

概念部分皆参考⾃列在参考链接中的博⽂。

1、数据结构：树树的部分主要参考：1.1 树作为计算机中常⽤的数据机构--树(Tree)，随着在计算机中应⽤越发⼴泛，衍⽣出了许多结构：树、⼆叉树、⼆叉查找树、平衡⼆叉树(AVL 树)、红⿊树、哈夫曼树(Huffman Tree)、多路查找树、B树、B+树、B*树、R树。

在计算机科学中，树（英语：tree）是⼀种抽象数据类型或是实现这种抽象数据类型的数据结构，⽤来模拟具有树状结构性质的数据集合。

它是由n（n>0）个有限节点组成⼀个具有层次关系的集合。

把它叫做“树”是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。

它具有以下的特点：①每个节点有零个或多个⼦节点；②没有⽗节点的节点称为根节点；③每⼀个⾮根节点有且只有⼀个⽗节点；④除了根节点外，每个⼦节点可以分为多个不相交的⼦树；然后你要知道⼀⼤堆关于树的术语：度，叶⼦节点，根节点，⽗节点，⼦节点，深度，⾼度。

1.2 ⼆叉树1.2.1 ⼆叉树⼆叉树：每个节点最多含有两个⼦树的树称为⼆叉树。

（我们⼀般在书中试题中见到的树是⼆叉树，但并不意味着所有的树都是⼆叉树。

）在⼆叉树的概念下⼜衍⽣出满⼆叉树和完全⼆叉树的概念满⼆叉树：除最后⼀层⽆任何⼦节点外，每⼀层上的所有结点都有两个⼦结点。

也可以这样理解，除叶⼦结点外的所有结点均有两个⼦结点。

节点数达到最⼤值，所有叶⼦结点必须在同⼀层上完全⼆叉树：若设⼆叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最⼤个数，第h层所有的结点都连续集中在最左边，这就是完全⼆叉树。

AVL树的插⼊和删除⼀、AVL 树 在计算机科学中，AVL树是最早被发明的⾃平衡⼆叉查找树。

在AVL树中，任⼀节点对应的两棵⼦树的最⼤⾼度差为 1，因此它也被称为⾼度平衡树。

查找、插⼊和删除在平均和最坏情况下的时间复杂度都是 O(log(n))。

插⼊和删除元素的操作则可能需要借由⼀次或多次树旋转，以实现树的重新平衡。

节点的平衡因⼦是它的左⼦树的⾼度减去它的右⼦树的⾼度（有时相反）。

带有平衡因⼦ 1、0 或 -1 的节点被认为是平衡的。

带有平衡因⼦ -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。

平衡因⼦可以直接存储在每个节点中，或从可能存储在节点中的⼦树⾼度计算出来。

⼤多数 BST 操作（例如，搜索，最⼤，最⼩，插⼊，删除等）花费 O(h) 时间，其中 h 是 BST 的⾼度。

对于偏斜的⼆叉树，这些操作的成本可能变为O(n)。

如果确保每次插⼊和删除后树的⾼度都保持 O(log2n)，则可以保证所有这些操作的 O(log2n)上限。

AVL树的⾼度始终为 O(log2n)，其中 n 是树中的节点数。

⼆、AVL 树的旋转 AVL 树在普通的插⼊和删除节点时都会使得树失去平衡，这时我们需要⼀些操作来把树恢复平衡，这些操作叫做AVL树的旋转，分为左旋和右旋。

T1，T2 和 T3 是树 y(左边) 或 x(右边) 的⼦树：y x/ \ Right Rotation / \x T3 - - - - - - - > T1 y/ \ < - - - - - - - / \T1 T2 Left Rotation T2 T3 以上两个树中的键都遵循以下顺序（⼆叉查找树的性质）： keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)。

1/**2 * 右旋转以y为根的⼦树3 *4 * @param y5 * @return6*/7private Node rightRoate(Node y) {8 Node x = y.left;9 Node T2 = x.right;1011/* 执⾏旋转 */12 x.right = y;13 y.left = T2;1415/* 更新⾼度 */16 y.height = max(height(y.left), height(y.right)) + 1;17 x.height = max(height(x.left), height(x.right)) + 1;1819return x;20 }2122/**23 * 左旋转以x为根的⼦树24 *25 * @param x26 * @return27*/28private Node leftRoate(Node x) {29 Node y = x.right;30 Node T2 = y.left;3132/* 执⾏旋转 */33 y.left = x;34 x.right = T2;3536/* 更新⾼度 */37 x.height = max(height(x.left), height(x.right)) + 1;38 y.height = max(height(y.left), height(y.right)) + 1;3940return y;41 }三、AVL 树的插⼊操作插⼊要遵循的步骤： 新插⼊的节点为 w 2）从 w 开始，向上移动并找到第⼀个不平衡节点。

avl方案1. 引言AVL树是一种自平衡二叉查找树，它在操作过程中保持树的高度平衡，从而保证了各种基本操作的时间复杂度为O(log n)。

本文将介绍AVL树的原理、实现方法以及应用场景。

2. AVL树的原理AVL树是由G.M. Adelson-Velsky和E.M. Landis在1962年提出的，它的名称取自于他们的名字的首字母。

AVL树的特点是每个节点的左子树和右子树的高度差不超过1，即保证了树的高度平衡。

AVL树的插入和删除操作会导致树的失衡，为了维持树的平衡，AVL树使用了旋转操作。

旋转操作主要包括左旋和右旋，通过重新调整子树的结构来使得树重新达到平衡。

3. 实现AVL树实现AVL树可以采用递归或迭代的方式，这里以递归方式为例进行说明。

3.1 AVL树节点定义首先需要定义AVL树的节点结构，一个简单的AVL树节点可以包括以下几个字段：class AVLNode:def__init__(self, key):self.key = keyself.left =Noneself.right =Noneself.height =1其中，key字段用于存储节点的键值，left和right字段分别指向节点的左子树和右子树，height字段表示节点的高度。

3.2 AVL树的插入操作AVL树的插入操作分为以下几个步骤：1.找到插入位置，若树为空，则直接插入新节点。

2.根据插入节点的键值与当前节点的键值进行比较，决定向左子树或右子树递归插入。

行旋转操作。

4.若当前节点失衡，根据失衡情况选择合适的旋转操作进行平衡调整。

下面是插入操作的递归实现代码：def insert(root, key):if not root:return AVLNode(key)elif key < root.key:root.left = insert(root.left, key)else:root.right = insert(root.right, key)root.height =1+ max(get_height(root.left), get_height(root.right)) balance = get_balance(root)# 左旋if balance >1and key < root.left.key:return rotate_right(root)# 右旋if balance <-1and key > root.right.key:return rotate_left(root)# 左右旋if balance >1and key > root.left.key:root.left = rotate_left(root.left)return rotate_right(root)# 右左旋if balance <-1and key < root.right.key:root.right = rotate_right(root.right)return rotate_left(root)return root3.3 AVL树的删除操作AVL树的删除操作也需要进行树的平衡调整，它分为以下几个步骤：1.找到待删除的节点。

AVL树原理AVL树原理介绍我们知道在⼆叉查找树中，如果插⼊元素的顺序接近有序，那么⼆叉查找树将退化为链表，从⽽导致⼆叉查找树的查找效率⼤为降低。

如何使得⼆叉查找树⽆论在什么样情况下都能使它的形态最⼤限度地接近满⼆叉树以保证它的查找效率呢？前苏联科学家G.M. Adelson-Velskii 和 E.M. Landis给出了答案。

他们在1962年发表的⼀篇名为《An algorithm for the organization of information》的⽂章中提出了⼀种⾃平衡⼆叉查找树（self-balancing binary search tree）。

这种⼆叉查找树在插⼊和删除操作中，可以通过⼀系列的旋转操作来保持平衡，从⽽保证了⼆叉查找树的查找效率。

最终这种⼆叉查找树以他们的名字命名为“AVL-Tree”，它也被称为平衡⼆叉树（Balanced Binary Tree）。

这⾥所说的平衡使我们想到了中庸之道，但有句话说得好，“中不偏，庸不易”。

学会这种平衡术是⼀个相当痛苦的过程。

什么是平衡为了保证平衡，AVL树中的每个结点都有⼀个平衡因⼦（balance factor，以下⽤BF表⽰），它表⽰这个结点的左、右⼦树的⾼度差，也就是左⼦树的⾼度减去右⼦树的⾼度的结果值。

AVL 树上所有结点的BF值只能是-1、0、1。

反之，只要⼆叉树上⼀个结点的BF的绝对值⼤于1，则该⼆叉树就不是平衡⼆叉树。

图1演⽰了平衡⼆叉树和⾮平衡⼆叉树。

AVL树的构造如何构造⼀棵平衡⼆叉树呢？动态地调整⼆叉查找树平衡的⽅法为：每插⼊⼀个结点后，⾸先检查是否破坏了树的平衡性，如果因插⼊结点⽽破坏了⼆叉查找树的平衡，则找出离插⼊点最近的不平衡结点，然后将该不平衡结点为根的⼦树进⾏旋转操作，我们称该不平衡结点为旋转根，以该旋转根为根的⼦树称为最⼩不平衡⼦树。

失衡状态可归纳为4种，它们对应着4种旋转类型AVL树上结点的插⼊AVL算法的思想理解起来还是不太困难的，但如果真要使⽤代码实现就没那么简单了，它拥有超⾼的算法实现复杂度。

常见基本数据结构——树，⼆叉树，⼆叉查找树，AVL树常见数据结构——树处理⼤量的数据时，链表的线性时间太慢了，不宜使⽤。

在树的数据结构中，其⼤部分的运⾏时间平均为O(logN)。

并且通过对树结构的修改，我们能够保证它的最坏情形下上述的时间界。

树的定义有很多种⽅式。

定义树的⾃然的⽅式是递归的⽅式。

⼀棵树是⼀些节点的集合，这个集合可以是空集，若⾮空集，则⼀棵树是由根节点r以及0个或多个⾮空⼦树T1,T2,T3,......,Tk组成，这些⼦树中每⼀棵的根都有来⾃根r的⼀条有向的边所连接。

从递归的定义中，我们发现⼀棵树是N个节点和N-1条边组成的，每⼀个节点都有⼀条边连接⽗节点，但是根节点除外。

具有相同⽗亲的节点为兄弟，类似的⽅法可以定义祖⽗和孙⼦的关系。

从节点n1到nk的路径定义为节点n1，n2，...，nk的⼀个序列，并且ni是ni+1的⽗亲。

这个路径的长是路径上的边数，即k-1。

每个节点到⾃⼰有⼀条长为0的路径。

⼀棵树从根到叶⼦节点恰好存在⼀条路径。

对于任意的节点ni，ni的深度为从根到ni的唯⼀路径长。

ni的⾼是从ni到⼀⽚叶⼦的最长路径的长。

因此，所有的树叶的⾼度都是0，⼀棵树的⾼等于它的根节点的⾼。

⼀棵树的深度总是等于它最深叶⼦的深度；该深度等于这棵树的⾼度。

树的实现实现树的⼀种⽅法可以是在每⼀个节点除数据外还要有⼀些指针，使得该节点的每⼀个⼉⼦都有⼀个指针指向它。

但是由于每个节点的⼉⼦树可以变化很⼤⽽且事先不知道，故在各个节点建⽴⼦节点的链接是不可⾏的，这样将会浪费⼤量的空间。

实际的做法很简单：将每个节点的所有⼉⼦都放在树节点的链表中。

下⾯是典型的声明：typedef struct TreeNode *PtrToNodestruct TreeNode{ ElementType Element; PtrToNode FirstChild; PtrToNode NextSibling}下⾯是⼉⼦兄弟表⽰法的图⽰：树的遍历及应⽤⼀个常见的使⽤是操作系统中的⽬录结构。

avl树java代码实现一、什么是AVL树？AVL树是一种自平衡二叉搜索树，它的名字来自于它的发明者Adelson-Velskii和Landis。

AVL树的特点在于每个节点的左子树和右子树的高度差最多为1，这样可以保证在插入或删除节点时能够自动调整以保持平衡性。

二、AVL树的实现1. AVLNode类首先需要定义一个AVLNode类，用于表示AVL树中的节点。

每个节点包含三个属性：值val、左子节点left和右子节点right，以及一个表示该节点所在子树高度的height属性。

public class AVLNode {public int val;public AVLNode left;public AVLNode right;public int height;public AVLNode(int val) {this.val = val;this.height = 1;}}2. AVLTree类接下来定义一个AVLTree类，用于实现插入、删除等操作。

该类包含两个属性：根节点root和size（表示该AVLTree中元素数量）。

public class AVLTree {private AVLNode root;private int size;//构造函数public AVLTree() {root = null;size = 0;}3. 插入操作插入操作是向AVL树中添加新元素的过程。

由于要保持平衡性，因此需要在插入后对整棵树进行调整。

public void insert(int val) {root = insert(root, val);}private AVLNode insert(AVLNode node, int val) {if (node == null) {size++;return new AVLNode(val);}if (val < node.val) {node.left = insert(node.left, val);} else if (val > node.val) {node.right = insert(node.right, val);} else { //如果val已经存在于AVL树中，则不需要插入return node;}//更新节点高度node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));//计算平衡因子int balanceFactor = getBalanceFactor(node);//LL旋转if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) { return rightRotate(node);}//RR旋转if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {return leftRotate(node);}//LR旋转if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) { node.left = leftRotate(node.left);return rightRotate(node);}//RL旋转if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) { node.right = rightRotate(node.right);return leftRotate(node);}return node;}在插入节点时，需要递归地遍历整棵树，找到插入位置。

数据结构九：AVL树（O（logn））AVL树来自"NOCOW"跳转到: 导航, 搜索本文在GNU自由文档许可证之条款下提供在计算机科学中，AVL树是最先发明的自平衡二叉查找树。

在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。

查找、插入和删除在平均和最坏情况下都是O(log n)。

增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在1962年的论文"An algorithm for the organization of information" 中发表了它。

节点的平衡因子是它的右子树的高度减去它的左子树的高度。

带有平衡因子 1、0 或 -1 的节点被认为是平衡的。

带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。

平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

目录[隐藏]•1操作o 1.1插入o 1.2删除o 1.3查找•2参考实现•3使用高度替代平衡因子•4平衡因子的推算[编辑] 操作AVL树的基本操作一般涉及运做同在不平衡的二叉查找树所运做的同样的算法。

但是要进行预先或随后做一次或多次所谓的"AVL 旋转"。

假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a(即a是离插入点最近，且平衡因子绝对值超过1的祖先结点)，则失去平衡后进行进行的规律可归纳为下列四种情况：1.单向右旋平衡处理RR：由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次右旋转操作；2.单向左旋平衡处理LL：由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行一次左旋转操作；3.双向旋转（先左后右）平衡处理LR：由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。

indexedfreelists binarytreedictionary -回复在计算机科学领域中，我们经常需要处理和操作各种数据结构。

其中一个常见的数据结构是二叉树，它被广泛用于实现诸如搜索树和字典等应用。

本文将探讨如何使用二叉树来实现一个索引的自由列表（Indexed Free Lists）和二叉树字典（Binary Tree Dictionary）的概念。

首先，我们来了解一下什么是索引的自由列表。

索引的自由列表是一种数据结构，它允许我们有效地插入、删除和查找元素。

与传统的线性列表不同，索引的自由列表使用索引来存储元素的位置，而不是依赖于逐个遍历的方式。

为了实现索引的自由列表，我们可以使用二叉树这个数据结构。

二叉树是由节点组成的树结构，每个节点最多有两个子节点。

通过适当地安排节点的位置和值，我们可以利用二叉树的特性来快速查找、插入和删除元素。

接下来，我们将介绍如何使用二叉树来实现索引的自由列表。

首先，我们需要定义一个节点类。

节点包含一个值，一个左子节点和一个右子节点。

节点类还包含一个索引值，用于表示节点在自由列表中的位置。

class Node:def __init__(self, value):self.value = valueself.left = Noneself.right = Noneself.index = None在创建索引的自由列表时，我们首先创建一个根节点，将其索引设为0。

然后，我们按照二叉树的排序规则，逐个插入元素。

对于每个要插入的元素，我们从根节点开始，比较元素的值和当前节点的值。

如果元素的值小于当前节点的值，则将元素插入当前节点的左子树；如果元素的值大于当前节点的值，则将元素插入当前节点的右子树。

在插入的过程中，我们需要更新每个节点的索引值，以保证它们在自由列表中的正确位置。

下面是一个将元素插入索引的自由列表的示例代码：class IndexedFreeList:def __init__(self):self.root = Noneself.size = 0def insert(self, value):if self.root is None:self.root = Node(value)self.root.index = 0else:self._insert_helper(value, self.root) self.size += 1def _insert_helper(self, value, node):if value < node.value:if node.left is None:node.left = Node(value)node.left.index = node.index * 2 + 1 else:self._insert_helper(value, node.left) else:if node.right is None:node.right = Node(value)node.right.index = node.index * 2 + 2 else:self._insert_helper(value, node.right)通过这样的插入过程，我们可以在O(log n)的时间复杂度内将元素插入到索引的自由列表中，其中n是列表中的元素数量。

Oracle反向索引（反转建索引）理解⼀反向索引1.1 反向索引的定义反向索引作为B-tree索引的⼀个分⽀，主要是在创建索引时，针对索引列的索引键值进⾏字节反转，进⽽实现分散存放到不同叶⼦节点块的⽬的。

1.2 反向索引针对的问题使⽤传统的B-tree索引，当索引的列是按顺序产⽣时，相应的索引键值会基本分布在同⼀个叶块中。

当⽤户对该列进⾏操作时，难免会发⽣索引块的争⽤。

使⽤反向索引，将索引列的键值进⾏反转，实现顺序的键值分散到不同的叶块中，从⽽减少索引块的争⽤。

例如：键值1001、1002、1003，反转后1001、2001、3001，进⽽分散到不⽤的叶⼦节点块中。

1.3 反向索引应⽤场景索引块成为热点块rac环境rac环境下中多节点访问访问数据呈现密集且集中的特点，索引热块的产⽣较⾼。

在范围检索不⾼的rac环境中使⽤反向索引可有效提⾼性能。

1.4 反向索引的优点与缺点优点：降低索引叶⼦块的争⽤问题，提升系统性能。

缺点：对于范围检索，例如：between，>，<时，反向索引⽆法引⽤，进⽽导致全表扫⾯的产⽣，降低系统性能。

1.5 反向索引⽰例说明-- 创建两张相同结构的表，内部结构及数据均引⽤scott⽤户下的emp表SQL> select count(*) from test01;COUNT(*)----------SQL>select count(*) from test02;COUNT(*)------------针对表TEST01的empno列，添加B-tree索引SQL>create index PK_TEST01 on TEST01(EMPNO);Index created.--针对表TEST02的empno列，添加反向索引SQL>create index PK_REV_TEST02 on TEST02(EMPNO) REVERSE;Index created.--验证上⾯的索引，NORMAL/REV表明为反向索引SQL>select TABLE_NAME,INDEX_NAME,INDEX_TYPE from user_indexes where INDEX_NAME like'%TEST%';TABLE_NAME INDEX_NAME INDEX_TYPE-------------------- -------------------- --------------------TEST01 PK_TEST01 NORMALTEST02 PK_REV_TEST02 NORMAL/REV--打开会话追踪SQL>set autotrace traceonly--相同条件查询，观察两表的执⾏计划SQL>select*from TEST01 where empno=7369;Execution Plan----------------------------------------------------------Plan hash value: 515586510-----------------------------------------------------------------------------------------| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |-----------------------------------------------------------------------------------------|0|SELECT STATEMENT ||1|87|2 (0)|00:00:01||1|TABLE ACCESS BY INDEX ROWID| TEST01 |1|87|2 (0)|00:00:01| |*2|INDEX RANGE SCAN | PK_TEST01 |1||1 (0)|00:00:01|-----------------------------------------------------------------------------------------Predicate Information (identified by operation id):---------------------------------------------------- access("EMPNO"=7369)Note------ dynamic sampling used for this statement (level=2)Statistics----------------------------------------------------------recursive callsdb block getsconsistent getsphysical readsredo sizebytes sent via SQL*Net to clientbytes received via SQL*Net from clientSQL*Net roundtrips to/from clientsorts (memory)sorts (disk)rows processedSQL>select*from TEST02 where empno=7369;Execution Plan----------------------------------------------------------Plan hash value: 1053012716---------------------------------------------------------------------------------------------| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |---------------------------------------------------------------------------------------------|0|SELECT STATEMENT ||1|87|2 (0)|00:00:01||1|TABLE ACCESS BY INDEX ROWID| TEST02 |1|87|2 (0)|00:00:01| |*2|INDEX RANGE SCAN | PK_REV_TEST02 |1||1 (0)|00:00:01| ---------------------------------------------------------------------------------------------Predicate Information (identified by operation id):---------------------------------------------------- access("EMPNO"=7369)Note------ dynamic sampling used for this statement (level=2)Statistics----------------------------------------------------------recursive callsdb block getsconsistent getsphysical readsredo sizebytes sent via SQL*Net to clientbytes received via SQL*Net from clientSQL*Net roundtrips to/from clientsorts (memory)sorts (disk)rows processed-- 相同范围条件查询，观察两表的执⾏计划SQL>select*from TEST01 where empno between7350and7500;Execution Plan----------------------------------------------------------Plan hash value: 515586510-----------------------------------------------------------------------------------------| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |-----------------------------------------------------------------------------------------|0|SELECT STATEMENT ||2|174|2 (0)|00:00:01||1|TABLE ACCESS BY INDEX ROWID| TEST01 |2|174|2 (0)|00:00:01||*2|INDEX RANGE SCAN | PK_TEST01 |2||1 (0)|00:00:01|-----------------------------------------------------------------------------------------Predicate Information (identified by operation id):---------------------------------------------------- access("EMPNO">=7350AND "EMPNO"<=7500)Note------ dynamic sampling used for this statement (level=2)Statistics----------------------------------------------------------recursive callsdb block getsconsistent getsphysical readsredo sizebytes sent via SQL*Net to clientbytes received via SQL*Net from clientSQL*Net roundtrips to/from clientsorts (memory)sorts (disk)rows processedSQL>select*from TEST02 where empno between7350and7500;Execution Plan----------------------------------------------------------Plan hash value: 3294238222----------------------------------------------------------------------------| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |----------------------------------------------------------------------------|0|SELECT STATEMENT ||2|174|3 (0)|00:00:01||*1|TABLE ACCESS FULL| TEST02 |2|174|3 (0)|00:00:01|----------------------------------------------------------------------------Predicate Information (identified by operation id):---------------------------------------------------- filter("EMPNO">=7350AND "EMPNO"<=7500)Note------ dynamic sampling used for this statement (level=2)Statistics----------------------------------------------------------recursive callsdb block getsconsistent gets0 redo sizebytes sent via SQL*Net to clientbytes received via SQL*Net from clientSQL*Net roundtrips to/from clientsorts (memory)sorts (disk)rows processed通过上⾯的⽰例可以看到，当使⽤between条件进⾏范围查询时，采⽤反向索引的表，并没有使⽤索引，⽽是采⽤了全表扫⾯的⽅式进⾏检索。

树结构调研个人资料一、查找树（Search Trees）之AVL树（平衡二叉树）（1）概述AVL树是最先发明的自平衡二叉查找树。

在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。

增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

丨图片来源：CSDN“带翅膀的猫”博客：详细图文——AVL树（2）数据结构&特点AVL树本质上还是一棵二叉搜索树，它的特点是：1.本身首先是一棵二叉搜索树。

2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。

（3）基本操作1）插入节点（旋转）假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a（即a是离插入点最近，且平衡因子绝对值超过1的祖先结点），则失去平衡后进行的规律可归纳为下列四种情况：丨参考资料：百度百科，AVL树①LL（右旋）由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次右旋转操作。

实现代码：丨图片来源：CSDN“带翅膀的猫”博客：详细图文——AVL树②RR左旋由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行一次左旋转操作。

实现代码：丨图片来源：CSDN“带翅膀的猫”博客：详细图文——AVL树③LR（先左后右）由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。

丨图片来源：CSDN“带翅膀的猫”博客：详细图文——AVL树④RL（先右后左）由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。

丨图片来源：CSDN“带翅膀的猫”博客：详细图文——AVL树2）删除从AVL树中删除可以通过把要删除的节点向下旋转成一个叶子节点，接着直接剪除这个叶子节点来完成。