数据结构,树,数据结构1713: 数据结构-平衡二叉树的基本操作题解

为你而来永不停止 算法基础篇 89 0
题库丰富多样,涵盖各个领域,全网最全C++题库,让您在练习中不断成长!
平衡二叉树又称AVL树,它是一种具有平衡因子的特殊二叉排序树,平衡二叉树或者是一棵空树,或者是具有以下几条性质的二叉树:。通过平衡二叉树的性质不难得知,其插入、删除、查询都操作的时间复杂度均为O,在本题中,读入一串整数,首先利用这些整数构造一棵平衡二叉树,另外给定多次查询,利用构造出的平衡二叉树,判断每一次查询是否成功。

平衡二叉树又称AVL树,它是一种具有平衡因子的特殊二叉排序树。平衡二叉树或者是一棵空树,或者是具有以下几条性质的二叉树: 1.       若它的左子树不空,则左子树上所有结点的值均小于它的根节点的值; 2.       若它的右子树不空,则右子树上所有结点的值均大于它的根节点的值; 3.       它的左右子树也分别为平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。 若将二叉树上结点的平衡因子定义为该结点的左子树深度减去它的右子树的深度,则平衡二叉树上的所有结点的平衡因子只可能为-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则这棵二叉树就是不平衡的。 通过平衡二叉树的性质不难得知,其插入、删除、查询都操作的时间复杂度均为O(log2n)。 维持平衡二叉树性质的操作可以被称为旋转。其中平衡二叉树的右旋处理可以描述如下: 而其左旋处理与右旋正好相反,可以描述如下: 在本题中,读入一串整数,首先利用这些整数构造一棵平衡二叉树。另外给定多次查询,利用构造出的平衡二叉树,判断每一次查询是否成功。

数据结构,树,数据结构1713: 数据结构-平衡二叉树的基本操作题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
不断学习,不断挑战,才能在编程领域中脱颖而出!全网最全C++题库,助您成为编程高手!

标签: 数据结构 数据结构1713: 数据结构-平衡二叉树的基本操作题解