二叉查找树与二叉平衡树

二叉查找树

二叉查找树(二叉搜索树,二叉排序树)若它的左子树不为空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不为空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树。

二叉平衡树

平衡二叉树也称作AVL树,AVL树本质还是一棵二叉查找树,只是在二叉查找树的基础上增加了“平衡”的要求。所谓平衡要求是指,对AVL树的任意结点来说,其左子树与右子树的高度之差的绝对值不超过1,其中左子树与右子树的高度因子之差称为平衡因子。

评论

暂无评论