Data-Structure

本文整理一般二叉树、二叉搜索树（BST）与平衡树的概念；BST 的插入、查找、删除与中序遍历的 Go 实现见我的 leetcode 仓库 下的 tree/（bst.go、bst_test.go）。 二叉树 (Binary Tree) 二叉树 (Binary Tree) 是包含 n 个节点的有限集合，该集合或者为空集（此时，二叉树称为空树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。 二叉树中的节点至多包含两棵子树，分别称为左子树和右子树，而左子树和右子树又分别至多包含两棵子树。由上述的定义，二叉树的定义是一种递归的定义。 graph TD n1((1)) n2((2)) n3((3)) n4((4)) n5((5)) n7((7)) n10((10)) n11((11)) n14((14)) n1 --> n2 n1 --> n3 n2 --> n4 n2 --> n5 n3 --> n7 n5 --> n10 n5 --> n11 n7 --> n14 满二叉树 Full Binary Tree 对于一棵二叉树，如果每一个非叶子节点都存在左右子树，并且二叉树中所有的叶子节点都在同一层中，这样的二叉树称为满二叉树。 graph TD n1((1)) n2((2)) n3((3)) n4((4)) n5((5)) n6((6)) n7((7)) n8((8)) n9((9)) n10((10)) n11((11)) n12((12)) n13((13)) n14((14)) n15((15)) n1 --> n2 n1 --> n3 n2 --> n4 n2 --> n5 n3 --> n6 n3 --> n7 n4 --> n8 n4 --> n9 n5 --> n10 n5 --> n11 n6 --> n12 n6 --> n13 n7 --> n14 n7 --> n15 完全二叉树 Complete Binary Tree 对于一棵具有 n 个节点的二叉树按照层次编号，同时，左右子树按照先左后右编号，如果编号为 i 的节点与同样深度的满二叉树中编号为 i 的节点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。 ...

AVL 树是最早出现的自平衡二叉搜索树，由 G.M. Adelson-Velsky 和 E.M. Landis 于 1962 年在论文《An algorithm for the organization of information》中提出，因此得名 AVL（发明者姓氏首字母），也叫高度平衡树。 平衡二叉树的通用定义（平衡因子、失衡、单旋恢复平衡的例子）见 二叉树与二叉搜索树 §平衡二叉树 Balanced Binary Tree，本文只讲 AVL 特有的部分：严格平衡条件、四种失衡情况的旋转、插入删除的复杂度，以及和其他平衡树、常见平衡树家族的关系。 严格平衡条件 一棵 AVL 树满足以下条件（递归定义）： 左子树和右子树都是 AVL 树。 左子树和右子树的高度差不超过 1。 相比红黑树用颜色规则换取的"相对平衡"，AVL 树是严格平衡：任意结点的平衡因子（左子树高度 − 右子树高度）只能取 -1、0、1。这带来的好处是查找效率稳定，代价是插入、删除时更容易触发再平衡。 树高的维护 判断是否失衡需要知道每个结点的子树高度，通常在结点里额外记一个 height 字段： 空结点（NIL）的高度记为 -1 叶子结点的高度为 0 非叶子结点的高度 = max(左子树高度, 右子树高度) + 1 插入或删除一个结点后，从该结点沿父指针回溯到根，逐层重新计算高度；一旦某个祖先的平衡因子超出 [-1, 1]，该结点就是失衡点，需要旋转恢复平衡。 失衡的四种情况与旋转 失衡点的位置只有 4 种可能，分别对应不同的旋转方式： 情况 触发位置 旋转方式 LL（左左） 左子树的左子树过高 对失衡点做一次右旋 RR（右右） 右子树的右子树过高 对失衡点做一次左旋 LR（左右） 左子树的右子树过高 先对左子树左旋，再对失衡点右旋（双旋） RL（右左） 右子树的左子树过高 先对右子树右旋，再对失衡点左旋（双旋） RR 单旋的完整示例见 二叉树与二叉搜索树 §插入示例，LL 是它的镜像。下面补充一个 LR 双旋的例子。 ...

Hash 表也称散列表，也有直接译作哈希表，是一种特殊的数据结构，同数组、链表以及二叉排序树等相比较有很明显的区别：它能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。这源于 Hash 表设计的特殊性，它采用函数映射的思想将记录的存储位置与记录的关键字关联起来，从而能够很快速地进行查找。 java.util.Hashtable 是 Java 中最早的哈希表实现，自 JDK 1.0（1996 年）就已存在。在现代 Java 中它依然保留，但仅用于向后兼容旧代码：非线程安全场景推荐使用 HashMap，需要线程安全时推荐使用 ConcurrentHashMap，两者性能和易用性都更好，Hashtable 已不建议在新代码中使用。 Hash 表的设计思想 对于一般的线性表，比如链表，如果要存储联系人信息： 张三 13980593357 李四 15828662334 王五 13409821234 张帅 13890583472 可能会设计一个结构体包含姓名、手机号码这些信息，然后把 4 个联系人的信息存到一张链表中。当要查找“李四 15828662334”这条记录是否在这张链表中，或者想要得到李四的手机号码时，可能会从链表的头结点开始遍历，依次将每个结点中的姓名同“李四”进行比较，直到查找成功或者失败为止，这种做法的时间复杂度为 O(n)。即使采用二叉排序树进行存储，也最多为 O(logn)。假设能够通过“李四”这个信息直接获取到该记录在表中的存储位置，就能省掉中间关键字比较的这个环节，复杂度直接降到 O(1)。Hash 表就能够达到这样的效果。 Hash 表采用一个映射函数 f : key -> address 将关键字映射到该记录在表中的存储位置，从而在想要查找该记录时，可以直接根据关键字和映射关系计算出该记录在表中的存储位置。通常情况下，这种映射关系称作 Hash 函数，而通过 Hash 函数和关键字计算出来的存储位置（注意这里的存储位置只是表中的存储位置，并不是实际的物理地址）称作 Hash 地址。比如上述例子中，假如联系人信息采用 Hash 表存储，则当想要找到“李四”的信息时，直接根据“李四”和 Hash 函数计算出 Hash 地址即可。 hashCode 与 equals 的关系 有人会说，可以直接根据 hashCode 值判断两个对象是否相等吗？肯定是不可以的，因为不同的对象可能会生成相同的 hashCode 值。虽然不能根据 hashCode 值判断两个对象是否相等，但是可以直接根据 hashCode 值判断两个对象不等——如果两个对象的 hashCode 值不等，则必定是两个不同的对象。如果要判断两个对象是否真正相等，必须通过 equals 方法。 ...