赞
踩
AVL树的名字来源于它的发明作者G.M. Adelson-Velsky 和 E.M. Landis。AVL树是最先发明的自平衡二叉查找树(Self-Balancing Binary Search Tree,简称平衡二叉树)。
平衡二叉树定义(AVL):它或者是一颗空树,或者具有以下性质的二叉排序树:它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。
一棵AVL树有如下必要条件:
条件一:它必须是二叉查找树。
条件二:每个节点的左子树和右子树的高度差至多为1。
图一中左边二叉树的节点45的左孩子46比45大,不满足二叉搜索树的条件,因此它也不是一棵平衡二叉树。
右边二叉树满足二叉搜索树的条件,同时它满足条件二,因此它是一棵平衡二叉树。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。