二叉查找树与二叉平衡树
文章目录
二叉查找树
二叉查找树(二叉搜索树,二叉排序树)若它的左子树不为空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不为空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树。
二叉平衡树
平衡二叉树也称作AVL树,AVL树本质还是一棵二叉查找树,只是在二叉查找树的基础上增加了“平衡”的要求。所谓平衡要求是指,对AVL树的任意结点来说,其左子树与右子树的高度之差的绝对值不超过1,其中左子树与右子树的高度因子之差称为平衡因子。
二叉查找树(二叉搜索树,二叉排序树)若它的左子树不为空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不为空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树。
平衡二叉树也称作AVL树,AVL树本质还是一棵二叉查找树,只是在二叉查找树的基础上增加了“平衡”的要求。所谓平衡要求是指,对AVL树的任意结点来说,其左子树与右子树的高度之差的绝对值不超过1,其中左子树与右子树的高度因子之差称为平衡因子。
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论