计算机论文

java中二叉树的存储结构及其算法

时间：2022-07-11 09:39 所属分类：计算机论文 点击次数：

　　摘要：二叉树其实是一种应用，也是无歧义地表示代数、关系或逻辑的表达式。早在上个世纪20年代初期，波兰的逻辑学家们发明了一种命题逻辑的特殊表示方法，其中允许从公式中删除所有括号，并且称之为波兰表示法。但是，这样的方法与原来带括号的公式相比，使用波兰表示法降低了公式的可读性，因此导致了这种算法没有得到广泛的使用。

　　但是，在计算机出现后，这一表示法就很有用了，特别是用于编写编译器和解释器。二叉树(Binary tree)是树形结构的一个重要类型。其实许多实际问题可以抽象出来表示，其数据结构往往是以二叉树形式，即使一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。

　　二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

　　关键词：二叉树；命题逻辑；解释器；编译器；存储结构

　　二叉树算法也有很多应用场景，比如用的最多的应该是平衡二叉树，还有哈夫曼树编码方面的应用。以及B-Tree，B+-Tree在文件系统中的应用。Dijkstra算法是最短路径算法中为人熟知的一种，是单起点全路径算法。该算法被称为是“贪心算法”的成功典范。该算法如果不优化速度非常慢，但是使用二叉树算法后会提升优化效率，使它节省很多运算时间，类似的，很多人工智能算法都是用二叉树优化的。

　　二叉树支持动态的插入和查找，保证操作在O(height)时间内，帮助完成了哈希表中不便完成的工作，具有动态性。二叉树有可能出现worst-case，当如果输入的序列已经排序，则时间复杂度为O(N)，而平衡二叉树/红黑树就是为了将查找时所需要的时间复杂度保证在O(logN)范围内，保证时间复杂度不会超出预期值。如果输入结合确定，所需要的就是查询，那么则可以考虑使用哈希表，如果输入集合不确定，那么则考虑使用平衡二叉树/红黑树，以保证其达到最大效率。而平衡二叉树主要优点集中在快速查找。

　　一、平衡二叉树的概念：

　　(一)平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据来减少无关数据的检索，从而大大的提升了数据检索的速度;平衡二叉树的数据结构组装过程有以下规则：

　　(1)非叶子节点只能允许最多两个子节点存在。

　　(2)每一个非叶子节点数据分布规则为左边的子节点小当前节点的值，右边的子节点大于当前节点的值(这里值是基于自己的算法规则而定的，比如hash值);

　　平衡树的层级结构：因为平衡二叉树查询性能和树的层级(h高度)成反比，h值越小查询越快、当为了保证树的结构左右两端数据大致平衡降低二叉树的查询难度，则一般会采用一种算法机制来实现节点数据结构的平衡，其中实现这种算法的方式很多列如有Treap、红黑树，都是使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于1.，通过这样的方法避免树形结构由于删除增加或变成线性链表对查询效率影响，在保证数据平衡的情况下使得查找数据的速度近似于二分法查找;

　　二、平衡二叉树的优点：

　　(一)比较灵活，在空间上可以实现高效压缩存储

　　在构造二叉排序树的过程中，每插入一个结点时，首先检查是否因结点插入而破坏了树的平衡性，若是，则找出最小不平衡子树，在保持二叉排序树的特性前提下，调整最小不平衡子树中各结点的位置，进行相应旋转，使其成为新的平衡子树。

　　(二)使得二叉树的结构更好，提高了查找操作的速度。

　　设结点A为最小平衡树的根结点，对该子树进行平衡调整当新插入的结点是插在结点A的左孩子的左子树上，即为LL型。

　　设结点B是结点A的左子树的根结点，Bl、Br分别为结点B的左右子树，Ar为结点A的右子树，且Bl、Br、Ar三棵子树的深度均为h，将结点x插入到结点B的左子树Bl上，导致结点A的平衡因子由1变为2.使得以结点A为根的子树失去了平衡将支撑点由A改为B，相应的进行顺时针旋转，旋转后，结点A及其右子树Ar和结点B的右子树Br发生冲突，按旋转优先原则，结点A成为B的右孩子结点，结点B的右子树Br成为结点A的左子树，

　　三、平衡二叉树的缺点：

　　多场景下增删会使得性能降低

　　平衡二叉树在增删场景较多的场景下，性能表现不好，涉及到多次左旋、右旋。平衡树虽然解决了二叉查找树退化为近似链表的缺点，并且能够把查找所需要的时间控制在O(logn)，不过却不是最佳的，因为平衡树要求每个节点的左子树和右子树的高度相差值至多等于1.这个要求实在是太严了，因而导致在每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣。

　　四、总结

　　(一)若平衡二叉树为空树，则插入一个记录为x的新节点作为T的根节点，树的深度增加1.

　　(二)若x的关键字值和平衡二叉树T的根节点的关键字值相等，则不进行插入操作。

　　(三)若X的关键字值小于平衡二叉树的根节点的关键字值，则将x插入在该树的左子树上，并且当插入之后的左子树深度增加1时，则需要分别就下列不同情况进行处理：

　　1、若平衡二叉树的根节点的平衡因子为-1(右子树的深度大于左子树的深度)，则将根节点的平衡因子调整为0.并且树的深度不变

　　2、若平衡二叉树的根节点的平衡因子为0(左右子树的深度相等)。则将根节点的平衡因子调整为1.树的深度同时增加1

　　3、若平衡二叉树的根节点的平衡因子为1(左子树的深度大于右子树的深度)，则当该树的左子树的根节点的平衡因子为1时需要进行LL型平衡旋转;当该树的左子树的根节点的平衡因子为-1时需进行LR型平衡旋转

　　(四)若x的关键字值大于平衡二叉树的根节点的关键字值，则将x插入在该树的右子树上，并且当插入之后的右子树深度增加1时，分别就下列不同情况进行处理：

　　1、若平衡二叉树的根节点的平衡因子为-1时(右子树的深度大于左子树的深度)，则当该树的右子树的根节点的平衡因子为-1时需进行RR型平衡旋转;当该树的右子树的根节点的平衡因子为1时需进行RL型平衡旋转

　　2、若平衡二叉树的根节点的平衡因子为0时(左右子树的深度相等)，则将根节点的平衡因子调整为-1.树的深度同时增加1

　　3、若平衡二叉树的根节点的平衡因子为1时(左子树的深度大于右子树的深度)，则将根节点的平衡因子调整为0.并且树的深度保持不变

　　参考文献

　　1严蔚敏,吴伟民编著..数据结构 C语言版[M].北京:清华大学出版社,2002:334.

　　2蒋盛益主编..《数据结构》学习指导与训练[M].北京:中国水利水电出版社,2003:384.

　　3江涛,徐孝凯编..数据结构[M].北京:中央广播电视大学出版社,1993:260.