二分查找法

定义: 将记录按有序化递增或递减排列,在查找过程中采用跳跃方式进行查找,即先以有序的中间位置为比较对象,如果要查找的值小于中点元素,则将待查序列缩小为左半部分,否则为右半部分

从图中可以看出,用了3次就查到了48这个数. 如果是顺序查找则需要8次.

二叉树

定义: 在二叉树中,左子树的值总是小于根的值,右子树的值总是大于根的值

查找方式为先查根,比根小查左子树,比根大查右子树

如图,这是一个效率很低的二叉树, 二叉树若想最大性能的构造,需要这颗二叉树是平衡的(平衡二叉树)

定义: 首先符合二叉树的定义, 其次必须满足任何节点的两个子树的高度最大差为1

平衡二叉树的性能比较高,但是简历和维护一个平衡二叉树需要大量的操作
如下图所示, 当用户需要插入一个新的值为9的节点时,需要做如下变动

如上图向一颗平衡二叉树插入一个新的节点后,平衡二叉树需要做的旋转操作很多, 平衡二叉树多用于内存结构对象中, 维护的开销相对比较小