数据结构查找：动态查找表(BST, AVL)

#内容归纳

查找

• 查找的基本概念
  • 静态查找表——基于线性表的查找法（二分查找）
  • 动态查找表——基于树表的查找法（二叉排序树、平衡二叉树、B树、红黑树）
  • 哈希表——计算式查找法

动态查找表——基于树表的查找法

动态查找表的特性：
在查找操作过程中，表结构能够实时生成。具体而言，当给定一个值 key 时，若表中存在与 key 相匹配的关键字记录，则判定查找成功；反之，若未找到对应记录，则将关键字等于 key 的新记录添加至表中。

动态查找表的核心操作
- 建立与释放
- 检索、添加及移除
- 遍历

二叉排序树定义与特性

定义：
二叉排序树可以表现为一种空树结构， 或者是一种满足特定条件的二叉树结构：
1. 当其左子树非空时， 左子树中所有节点的数值均小于根节点的数值；
2. 当其右子树非空时， 右子树中所有节点的数值均大于根节点的数值；
3. 其左、右子树本身也必须符合二叉排