7.3.1.3 二叉排序树的构造
原书定位
印刷页P285起,对应PDF第297页。下文为目视整理的知识提要;完整内容见原书对照。
从空树开始依输入次序逐个插入。相同关键字集合可以因输入顺序不同形成不同树,许多不同输入序列也可能形成同一棵树。
有序输入会令普通 BST 退化成单支链;查找、插入最坏线性,逐个构造最坏 。要保证对数性能需要平衡机制或其他构造方式。

二叉排序树构造过程,原书P285。
对应练习
关联知识
原书对照
展开原书对照截图

原书定位
印刷页P285起,对应PDF第297页。下文为目视整理的知识提要;完整内容见原书对照。
从空树开始依输入次序逐个插入。相同关键字集合可以因输入顺序不同形成不同树,许多不同输入序列也可能形成同一棵树。
有序输入会令普通 BST 退化成单支链;查找、插入最坏线性,逐个构造最坏 。要保证对数性能需要平衡机制或其他构造方式。

二叉排序树构造过程,原书P285。
