二叉排序树(BST)、平衡二叉树(AVL)、B-树、B+树_平衡bst

作者：笔触狂放9 | 2024-05-28 21:30:35

踩

平衡bst

二叉排序树(BST)，又叫二叉查找树，亦称二叉搜索树，它或者是一颗空树，或者是具有以下性质的二叉树：

1)若它的左子树不空，则左子树上所有关键字的值均小于根关键字的值；

2)若它的右子树不空，则右子树上所有关键字的值均大于根关键字的值；

3)左右子树又各是一颗二叉排序树；

注：由二叉排序树的定义可知，如果输出二叉排序树的中序遍历序列，则这个序列是递增有序的。

(1)插入

插入过程比较简单，首先判断当前要插入的值是否已经存在于二叉排序树中，如果已经存在，则直接返回；如果不存在，则找到适当的位置，将其插入。注意插入的新节点一定是叶子节点；

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/639342