7.3 树形查找

概念

1. 二叉排序树（BST）
   

二叉排序树（Binary Sort Tree，BST），又称为二叉查找（搜索）树（Binary Search Tree），是一种特殊的二叉树，它具有以下性质：

1. 若它的左子树非空，则左子树上所有结点的值均小于根结点的值。
2. 若它的右子树非空，则右子树上所有结点的值均大于根结点的值。
3. 左、右子树本身又各是一棵二叉排序树，即具有递归性。

这些性质使得二叉排序树在进行查找、插入和删除操作时都能保持较高的效率。例如，在查找操作中，从根节点开始，如果待查找的值小于当前节点的值，则在左子树中继续查找；如果待查找的值大于当前节点的值，则在右子树中继续查找。这种查找方式的时间复杂度与树的高度相关，理想情况下可以达到O(log n)的复杂度。

二叉排序树的插入操作也很高效。在插入新元素时，可以从根节点开始，比较新元素与当前节点的值，根据大小关系决定向左子树还是右子树进行插入，直到找到合适的位置。

此外，由于二叉排序树的中序遍历序列是一个递增有序序列，因此它也可以用于对元素进行排序。

需要注意的是，当插入的元素正好是有序的时，二叉排序树可能会退化成链表，导致查找效率降低。因此，在实际应用中，可能需要采取一些措施来避免这种情况的发生，如使用平衡二叉树等数据结构。

2. 平衡二叉树
   

平衡二叉树（Balanced Binary Tree），又称为AVL树，是一种特殊的二叉搜索树（Binary Search Tree）结构。它对于任意节点，其左子树和右子树的高度之差不超过1，并且左子树和右子树也都是平衡二叉树。平衡二叉树的设计目的是为了解决普通二叉搜索树在插入、删除等操作时产生不平衡的问题，导致树的高度过高，从而影响搜索的效率。

平衡二叉树具有广泛的应用场景，包括：

1. 查找和排序：平衡二叉树可以用于快速查找和排序数据。由于其特殊的结构，它可以在O(log n)的时间内完成查找和排序操作，这比线性搜索更为高效。
2. 实现字典：平衡二叉树可以用来实现字典，其中键是树中的节点，值是与该键相关联的数据。在这种情况下，平衡二叉树的节点将按照键的顺序排列，因此查找特定键的值是非常快速的。
3. 数据库：平衡二叉树可以用于实现数据库中的索引。索引可以帮助加速数据库的查询操作。平衡二叉树可以在不需要扫描整个数据库的情况下快速定位特定的记录。
4. 线性数据结构的实现：平衡二叉树可以用于实现一些常见的线性数据结构，如栈、队列和优先队列。这是通过在树的一侧添加新节点并在另一侧移除节点来实现的，从而保持平衡性。

此外，平衡二叉树还有一些常用的算法，如红黑树、AVL、Treap等，用于构造和调整平衡二叉树。

总的来说，平衡二叉树通过保持树的平衡性，提高了搜索、插入和删除操作的效率，在各种应用场景中都发挥着重要作用。

• 调整最小不平衡子树旋转概述：原父为最小不平衡点

    1.  RR：对儿子：左旋L，左孩变原父右
  
    2.  LL：对儿子：右旋R，右孩变原父左
  
    3.  RL：对孙子：先右旋再左旋RL
  
    4.  LR：对孙子：先左旋再右旋LR
  

3. 红黑树

红黑树（Red Black Tree）是一种自平衡的二叉查找树，在计算机科学中常用作一种数据结构，其典型的用途是实现关联数组。红黑树是平衡二叉查找树的变体，它在保持平衡的同时，允许其左右子树的高度差有可能大于1，但不超过一倍。这种设计使得红黑树在插入和删除节点时能够保持较低的平衡代价，并因此获得较高的查找性能。

红黑树具有五大性质，这些性质保证了其结构的平衡性和搜索效率：

1. 每个节点要么是黑色，要么是红色。
2. 根节点是黑色。
3. 每个叶节点（Nil或空值）都是黑色。
4. 每个红色节点的两个子节点一定都是黑色（但黑色节点的子节点可以也是黑色）。
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

这些性质确保了红黑树在插入、删除和查找操作中的效率。在最坏情况下，红黑树的运行时间也非常良好，可以在O(log n)时间内完成查找、插入和删除操作，其中n是树中元素的数目。

与平衡二叉树（AVL树）相比，红黑树在追求平衡的策略上有所不同。红黑树放弃了追求完全平衡，转而追求大致平衡。这使得红黑树在插入新节点时，最多只需要三次旋转就能达到平衡，实现起来更为简单。而平衡二叉树追求绝对平衡，每次插入新节点后可能需要多次旋转，旋转的次数不能预知。

总的来说，红黑树是一种高效且实用的数据结构，能够在保持平衡的同时提供快速的查找、插入和删除操作。

红黑树的查找：与二叉树BST、AVL相同，从根出发，左小右大，若查找到一个叶结点，则查找失败

理解

1. 二叉排序树操作复杂度主要与树的高度有关，如果是平衡二叉排序树，则复杂度是O(log₂n)，如果是只有单侧树，即n个结点排成一条线，复杂度是O(n)

2. 二叉排序树的数据结构

名称	左指针	权值	右指针
作用	指向比自己小的结点	结点的值	指向比自己大的结点

3. 平衡二叉树结点最少的情况

   1. 左右子树相差一个结点，可以递归

   2. 高度为0，最少0个结点；高度为1，最少1个结点

   3. 高度为h，最少结点数n_(h)=n_(h-1)+n_(h-2)+1

   4. 平衡二叉树结点最少的情况下，每个非叶结点的平衡因子都是1

4. 对于任意一棵非空二叉排序树T1，如果删除某个结点v之后形成二叉排序树T2，再将v结点插入T2形成二叉排序树T3则有

   1. 若v是T1的叶结点，则T1与T3相同

   2. 若v不是T1叶结点，则T1和T3不同

5. 对于任意一棵非空平衡二叉树T1，如果删除某个结点v之后形成平衡二叉树T2，再将v结点插入T2形成平衡二叉树T3则有

   1. 若v是T1的叶结点，则T1与T3未必相同

   2. 若v不是T1叶结点，则T1和T3未必相同

技巧

1. 二叉排序树查找序列的规律：以2，252，401，398，330，…为例

次数	比较	说明	序列规律
1	2	访问根结点2
2	252，252>2	访问左子树252	2后是结点2的左子树，后面的值都应该>2
3	401，401>252	访问左子树401	252后是结点252的左子树，后面的值都应该>252
4	398，398<401	访问右子树398	401后是结点401的右子树，后面的值都应该<401
…	…	……	……