7.3.1.3 二叉排序树的构造

教材导航 · 第7章

原书定位

印刷页P285起,对应PDF第297页。下文为目视整理的知识提要;完整内容见原书对照。

从空树开始依输入次序逐个插入。相同关键字集合可以因输入顺序不同形成不同树,许多不同输入序列也可能形成同一棵树。

有序输入会令普通 BST 退化成单支链;查找、插入最坏线性,逐个构造最坏 O(n2)O(n^2)。要保证对数性能需要平衡机制或其他构造方式。

二叉排序树构造过程

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

对应练习

7.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P285,PDF第297页