0%

Java Map 和 Set（三）：排序二叉树

发表于 更新于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

1. 树和二叉树的概念

  • 树：在计算机程序中，一般而言，与现实相反，树是从上往下长的，也会分叉。有个根节点，每个节点可以有一个或多个孩子节点，没有孩子节点的节点一般称为叶子节点
  • 二叉树：是一棵树，每个节点最多有两个孩子节点，一左一右，左边的称为左孩子，右边的称为右孩子
  • 树有一个高度或深度的概念，是从根到叶子节点经过的节点个数的最大值

2. 排序二叉树的概念

  • 排序二叉树也是二叉树，但它没有重复元素，而且是有序的二叉树

3. 排序二叉树的有序是指什么顺序

  • 对每个节点而言
    • 如果左子树不为空，则左子树上的所有节点都小于该节点
    • 如果右子树不为空，则右子树上的所有节点都大于该节点
  • 简单来说，即：左小右大

4. 排序二叉树的查找算法

  • 查找元素时，很方便高效。与二分查找思路类似，如果二叉树比较平衡，则效率很高

    • 首先与根节点比较，如果相同，就找到了
    • 如果小于根节点，则到左子树中递归查找；如果大于根节点，则到右子树中递归查找

  • 另外，在排序二叉树中，可以方便地查找最大值和最小值。最小值即为最左边的节点，从根节点一路查找左孩子即可；最大值即为最右边的节点，从根节点一路查找右孩子即可

5. 排序二叉树的遍历算法

  • 用递归的方式按序遍历：前序遍历、中序遍历、后序遍历
  • 后继节点算法：第一个节点为最左边的节点，从第一个节点开始，依次找后继节点。给定一个节点，找其后继节点的算法为
    1. 如果该节点有右孩子，则后继节点为右子树中最小的节点
    2. 如果该节点没有右孩子，则后继节点为父节点或某个祖先节点，从当前节点往上找，如果它是父节点的右孩子，则继续找父节点，直到它不是右孩子或父节点为空，第一个非右孩子节点的父节点就是后继节点；如果找不到这样的祖先节点，则后继节点为空，遍历结束

6. 怎样构建排序二叉树

  • 可以在插入、删除元素的过程中保持
  • 排序二叉树的形状与插入和删除的顺序密切相关
  • 极端情况下，排序二叉树可能退化为一个链表

7. 排序二叉树的插入算法

  • 在排序二叉树中，插入元素首先要找插入位置，即新节点的父节点。与查找元素类似，从根节点开始往下找，步骤为
    1. 与当前节点比较，如果相同，表示已经存在了，不能再插入了
    2. 如果小于当前节点，则到左子树中寻找，如果左子树为空，则当前节点即为要找的父节点
    3. 如果大于当前节点，则到右子树中寻找，如果右子树为空，则当前节点即为要找的父节点
    4. 找到父节点后，即可插入，如果插入元素小于父节点，则作为左孩子插入，否则作为右孩子插入

8. 排序二叉树的删除算法

  • 从排序二叉树中删除一个节点要复杂一些，有三种情况
    • 节点为叶子节点：如果节点为叶子节点，则很简单，可以直接删除，修改父节点的对应孩子节点为空即可
    • 节点只有一个孩子节点：如果节点只有一个孩子节点，则替换待删节点为孩子节点，或者说，在待删节点的孩子节点和待删节点的父节点直接建立链接
    • 节点有两个孩子节点：如果节点有两个孩子节点，则首先找该节点的后继节点，找到之后，替换待删节点为后继节点的内容，然后再删除后继节点。后继节点没有左孩子，这就将两个孩子节点的情况转换为叶子节点或只有一个孩子节点的情况

9. 平衡的排序二叉树中的平衡是什么意思，平衡的具体定义是什么

  • 高度平衡：任何节点的左右子树的高度差最多为一
  • AVL 树：满足高度平衡的排序二叉树
    • AVL 树这个名字源于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis
    • 在他们的算法中，在插入和删除节点时，通过一次或多次旋转操作来重新平衡树
  • 平衡的作用：保证树的查找效率

10. 红黑树的概念

  • 定义：红黑树是一种大致平衡的排序二叉树

  • 原理

    • 与 AVL 树类似

      • 红黑树也是一种平衡的排序二叉树，也是在插入和删除节点时通过旋转操作来保持平衡的，但它不是高度平衡的 ，而是大致平衡的

    • 大致平衡

      • 它确保任意一条从根到叶子节点的路径，没有任何一条路径的长度会比其他路径长过两倍
* 原因
    * 红黑树减弱了对平衡的要求，但**降低了保持平衡需要的开销**
    * 在实际应用中，**统计性能要高于 AVL 树，在实际应用中更为广泛**


* 名称
    * 之所以叫红黑树，是因为它**对每个节点进行着色**，颜色或**黑**或**红**
    * 并**对节点的着色有一些约束**，满足这个约束即可以**保证树是大致平衡的**


* 应用
    * **`TreeMap` 的实现原理是红黑树**
    * **Java 8 中，当 `HashMap` 哈希冲突严重时，会把哈希表的单链表优化为一颗红黑树**

  • 特征：红黑树除了符合排序二叉树左小右大的基本特征外，还具有下列附加特征

    • 根节点是黑色
    • 其他节点是红色或黑色
    • 每个叶子节点都是黑色的空节点
    • 每个红色节点的两个孩子节点都是黑色（从每个叶子节点到根节点的所有路径上不能有两个连续的红色节点）
    • 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

  • 举例：
    红黑树

  • 调整

    • 变色：红变黑、黑变红
    • 旋转
      • 左旋转：逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。
      • 右旋转：顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。

  • 参考

11. 排序二叉树的特点

  • 排序二叉树保持了元素的顺序，而且是一种综合效率很高的数据结构（兼具数组和链表的优点）
  • 排序二叉树基本的保存、删除、查找元素操作的效率都为 O(h)，h 为数的高度。在树平衡的情况下，h = log2(N)，N 为树的节点数
  • 哈希和树是两种基本的思维方式：不需要排序，优先考虑哈希；需要排序，考虑树
  • 另外，数据库中的索引结构也是基于树的（基于 B 树，不是二叉树），而索引是能够在大量数据中快速访问数据的关键
-------------------- 本文结束感谢您的阅读 --------------------