树表示法视觉表示树的视觉表示用倒置分支树的形式表示，如下图是直观的树表达的表示。它的特点是对树的逻辑结构的描述非常直观。是数据结构中最常用的树形描述方法。嵌套集合表示法。所谓嵌套集合，是指一些集合的集合。相交，或者一个包含另一个。用嵌套集合的形式表示一棵树，就是把根节点看成一个大集合，它的若干个子树构成了这个大集合中若干个不相交的子集，这样嵌套就构成了树的嵌套。集合表示的集合。如下图所示，凹形符号主要用于树的屏幕输出和打印输出。广义表符号树用广义表来表示，即把根写成表左边的子树森林组成的表名，这样树就会被表示出来。如下图(A(B(D,E(H,I),F),C)G)))term节点表示树中的元素，包括数据项和几个分支节点指向其子树的度数节点拥有的子树的数量称为该节点的度。叶子节点度为0的节点称为叶子节点，或终端节点。分支节点度不为0的节点称为节点。分支节点，或非终端节点。一棵树的节点除了叶子节点外，都是分支节点children、parents、brothers。如果一棵树中节点A的子树的根节点是B，则B称为A的子节点，称A为B的父节点。具有相同父节点的子节点称为兄弟路径，而B的长度路径如下。如果一棵树的一系列节点$n_1,n_2,...n_k$有如下关??系，即节点$n_i$是$n_{i+1}$的父节点（1<=i=1）在图1中，第四层的节点正好是$2^{4-1}=8$个节点的性质2一棵深度为k的树在二叉树中，至多有$2^k-1$个节点。在图1中，二叉树的深度为4，它正好有$2^4-1=15$个节点。性质3对于一棵非空二叉树，如果叶子节点的个数为$n_0$，则度为2的节点个数为$n_2$，则$n_0=n_2+1$，在图1中，二叉树有：H,I,J,K,L,M,N,O一共8个节点，度数为2的节点有：A,B,C,D,E,F,G,一共7个节点。n个节点的完全二叉树的性质4深度k为$log2^n+1$图2中一共有10个节点，其深度恰好为$log_2{10}+1=4$性质5对于a有n个节点的完全二叉树，若按照从上到下，从左到右，将二叉树中的所有节点从1开始依次编号，则对于任意序号为i的节点，有：若i>1、那么序号为i的节点，其父节点的序号为i/2；若i=1，则该节点为根节点，若无父节点，若2i<=n，则序号为i的节点的左子节点序号为2i；如果2i>n，序号为i的节点没有左子节点。若2i+1<=n，则序号为i的右子节点序号为2i+1；如果2i+1>n，则序号为i的节点没有右子节点对于以上性质，可以参考图2理解上图中二叉树的遍历为例，三者的结果遍历方法如下在左子树中依次遍历根节点的右子树输出：ABDCin-ordertraversal(LDR)根节点左子树中序遍历访问根节点in-ordertraversal根节点右子树Output:BDACpost-ordertraversal(LRD)后序遍历根节点左子树的后序遍历根节点右子树访问根节点输出：DBCAB树定义B树也是一棵多路平衡搜索树。我们在描述一棵B树的时候，一般会指定它的顺序，顺序代表一个节点最多有多少个子节点？通常，顺序由字母m表示。当m=2时，也就是我们所说的二叉搜索树。m阶B树定义如下：树中每个节点至多有m个子节点如果树的根节点不是叶节点，则至少有两棵子树除根外，且都是非叶节点节点至少有[m/2]个子树。所有非叶子节点都包含以下信息数据($n,p_0,k_1,p_1,p_2,...,k_n,p_n$)，$k_i$为关键字，$k_i$<$k_{i+1}$,$p_i$是指向子树根节点的指针，$p_i$指向的子树中所有节点的关键字都小于$k_{i+1}$,$p_i$是指针到根结点，$p_i$指向的子树中所有结点的关键字小于$k_{i+1}$且大于$k_i$的词，n为关键字个数所有叶子结点出现在同一层级，且从根节点到每个叶子节点的长度都相同B+树定义B树的变形树。B+树上的叶子节点存放关键字和对应记录的地址。叶节点上方的层用作索引。m阶B+树定义如下，每个节点至多有m个节点，除根节点外，每个节点至少有[m/2]个孩子，根节点至少有2个孩子。有k个孩子的节点必须有k个关键字。B+树搜索与B树不同，当索引中某个节点的关键字等于被搜索的关键字时，搜索不会停止，指向关键字左边的指针要继续向下，直到叶子查找关键字所在的节点。下面是B树结构的演示视频[100,200,300,400,500,600,700,800,900]插入过程500查询400删除B树和B+树对比B+树磁盘读写成本较低的内部结点没有指向关键字具体信息的指针，所以它的内部结点比B树小。如果同一个内部节点的所有关键字都存储在同一个磁盘块中，那么磁盘块可以容纳的关键字数量越大，IO读写次数越少，搜索速度越快。B+树查询效率更稳定。因为非叶子节点并不是最终指向文件内容的节点，而只是叶子节点索引的关键字。因此，在B+树中搜索任何关键字，都必须走一条从根节点到叶子节点的路径。所有关键字查询的路径长度相同，导致每条数据的查询效率相同。每个节点都有特定的数据，所以它的查询速度是不稳定的，可能很快，也可能很慢。B+树方便范围查询。B树在提高IO性能的同时，并没有解决元素遍历效率低下的问题。为了解决这个问题，B+树应运而生。B+树只需要遍历叶子节点就可以实现整棵树的遍历（B+树的叶子节点维护一个有序的链表。基于范围的查找在数据库中也很频繁，所以MySQL的Innodb引擎使用了B+树作为其索引[100,200,300,400,500,600,700,800,900]的数据结构的基本形式插入过程500查询400删除红??黑树定义红黑树是具体的二叉树的类型，它是计算机科学中用于组织数据块（例如数字）的结构。红黑树是平衡二叉搜索树的变体。它的左右子树之间的高度差可能更大大于1，所以红黑树不是严格意义上的平衡二叉树（AVL），但是平衡它的代价很低，平均统计性能比AVL强。因为每棵红黑树是二叉排序树，因此，在进行红黑树搜索时，可以使用应用于普通二叉树的搜索算法。在搜索过程中，不需要颜色信息。属性节点为红色或黑色。根节点是黑色的。所有叶子都是黑色的（叶子是NIL节点）。每个红色节点点的两个单词节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）从任何节点到它的每个叶子的所有路径都包含相同的数据黑色的基本形状node[100,200,300,400,500,600,700,800,900]插入进程500的查询400的链接删除原文
