跳转至

排序

查找

考点一 线性表的查找

image-20260803203332602

image-20260803203937533

image-20260803204145883

image-20260803204536911

image-20260803204733830

image-20260803204955766

考点二 二叉排序树

image-20260803210029279

image-20260804151137152

image-20260804151147633image-20260804151224945

考点三 二叉平衡树

image-20260804151857348

image-20260804151918899

image-20260804152238996

image-20260804152515550

image-20260804153019106

若所有非叶结点的平衡因子均为1，则当前结点最少。

考点四 B树与B+树

image-20260804154559981

image-20260804154612386

image-20260804154833117image-20260804155345269

image-20260804155715584

image-20260804160702380

考点五 散列表

  1. 影响一个散列表的查找效率的因素有：装填因子、散列函数、处理冲突的方法。虽然装填因子是由关键字个数和表长得出，但是查找效率和他俩其中之一是没有关系的。

image-20260804162818278

image-20260804163328664

image-20260804163701635

如果删了可能会导致查找失败。

image-20260804164016121

image-20260804164048187

image-20260804164352477

image-20260804164516370

考点六 红黑树

红黑树和AVL的插入、删除时间复杂度都是O(logn)

image-20260804165543916

红结点数量最多可为黑结点的两倍。

image-20260804165856130

image-20260804170629369

父红且叔红：叔叔、父亲、祖父都要染色，然后根据祖父是否是根节点再做判断。

image-20260804171355453