二叉树学习笔记

春假已经过了两天啦!今天开始好好学习了!今天要看的是 Binary Tree!

Definition

A tree T is a set of nodes that form a directed acyclic graph (DAG).

换成人类语言就是树上的每个节点都只有上下两个方向,且向上有且只有一条路径,向下则无限制。

Height

The height of a node ni is the length of the longest path under ni’s subtree.

  • All leaves have a height of 0.

Depth

The depth of a node ni is the length of the path from the root to ni.

  • The root node has a depth of 0.
  • The depth of a tree is the depth of its deepest leaf.

Relationship

Height of Tree = Height of Root = Depth of Tree

Implementation

树的基本实现方法有三种:

  1. Vecotr of Children
    用 Vector 来保存所有子节点。这样做的好处是可以直接访问到每一个节点 node[i],但是需要事先算好最多会有多少子节点来决定是否需要更多空间。

    1
    2
    3
    4
    struct TreeNode {
    Object element;
    vector<TreeNode> children;
    }
  2. List of Children
    用 List 来保存所有子节点。这样做可以有一个动态的长度;我们就不需要事先算好子节点的个数。但这样做也会增加访问每个节点嗦耗费的时间。

    1
    2
    3
    4
    struct TreeNode {
    Object element;
    list<TreeNode> children;
    }
  3. “Left-Child, Right-Sibling” or “First-Child, Next-Sibling”
    以来类似链表的结构实现。这样会让每个节点都会维护两个指针分别指向其第一个子节点和下一个 兄妹 兄弟节点;我们就完全不需要担心子节点的个数了。但是同时访问时间也会变得与子节点的数量成正比。

    Left-Child, Right-Sibling

    1
    2
    3
    4
    5
    struct TreeNode {
    Object element;
    TreeNode firstChild;
    TreeNode nextSibling;
    }

Binary Tree

A binary tree is a tree where each node has no more than two children.

1
2
3
4
5
struct BinaryTreeNode {
Object element;
BinaryTreeNode leftChild;
BinaryTreeNode rightChild;
}

如果一个节点只有一个或没有子节点,那么子节点指针为 null

Binary Search Tree (BST)

对于 BST 上的任意节点,其左子节点比它小,其右子节点比它大;由此可以推导:一个节点的左节点及左节点的所有后代和兄弟节点均比该节点小,一个节点的右节点及右节点的所有后代和兄弟节点均比该节点大。我们称这种状态为 Symmetric Order。

Deletion

在 BST 中添加/插入一个节点并不是很难,但是删除会有一些复杂,主要分为以下三种情况:

  1. 该节点没有任何子节点:直接移除它
  2. 该节点有一个子节点:把子节点上移
  3. 该节点有两个子节点:找到其最大子节点并上移

搜索时要注意是否出现重复的元素,如果有重复的元素则在节点中维护一个 count 变量来保存该节点所保存的值出现的次数,或用节点维护一个表来保存更多的值。

1
2
3
4
5
6
public static void contains (TreeNode T, Object o) {
if (null == T) return null;
if (T.equals(o)) return T;
if (less(o, T.getElement()) return contains(T.getLeftChild, o);
else return contains(T.getRightChild, o);
}

Time Complexity

Complexity of searching a BST: O(h)O(h) where h is the heigh of the tree.
在二叉树中,平衡很重要。如果数据全往一边倒那么就会变成一棵超高的树,搜索时间会变很长,时间复杂度和节点个数成正比;但是如果是一棵平衡的二叉树的话,时间复杂度就会降低很多。

Operations:

  • Print Tree: Θ(N)\Theta (N)
  • Intert, Remove, Search, Find Maximum Value and Find Minimum Value: Θ(h)\Theta (h) where hh stands for height of the tree
  • Worst case: h=Θ(N)h = \Theta (N)
  • Best case: h=Θ(lgN)h = \Theta (lgN)
  • Average case: h=Θ(lgN)h = \Theta (lgN)

即使一棵二叉树本身是完全平衡的,在其生命周期拉长后,其平均深度会慢慢变成 ΘN1/2)\Theta (N^{1/2}),与我们的预期相差甚远。为了解决这样的问题,AVL Trees 和 Red-Black BSTs 出现了。
前面的问题不断地揭示了我们需要完全平衡的二叉树的事实,但是要维护一棵完全平衡二叉树对于数据结构的性能消耗也不小,当我们插入一个比整棵树所有值都大或都小的值时,时间复杂度为 O(N)O(N)。所以我们可以选择优化数的高度来解决这个问题。

AVL (Adelson, Velskii and Landis)

AVL 树的主要理念为:

  • 一个节点的左右子树的高度差最大为 1
  • 在每次树被更新后强制维护整棵树
  • 树的深度永远为 O(log2n)O(log_2n)

Insert

Insertions can violate AVL’s balance, and this can be fixed by “rotation”.

当我们将一个新的节点插入到 AVL 中时,树的平衡可能会被打破,我们以自下向上的叫做 rotation 的方式来修正这种错误。

假设在我们插入了新节点后,错误发生节点 k 上,那么我们可能会遇到四种情况:

  • 新节点插入到了节点 k 的子节点的子树上
  • 新节点插入到了节点 k 的子节点的子树上
  • 新节点插入到了节点 k 的子节点的子树上
  • 新节点插入到了节点 k 的子节点的子树上

其中,第一种和最后一种情况都可以用 Single Rotation 来修正,而第二种和第三种则需要 Double Rotation 来修正了。

Solution for Violation Case 1 (LL)

Case and Solution

Before Rotation

After Rotation

Solution for Violation Case 4 (RR)

Case and Solution

Before Rotation

After Rotation

Solution for Violation Case 2 (RL)

Case and Solution

Before Rotation

After Rotation

Solution for Violation Case 3 (LR)

Case and Solution

In this case, the operation is the same as in case 2, but the order and direction are opposite.

至此,Kiyoshi 已经大概理解了 Rotation 的方式。以后有空可以再填填坑,文字解释一下以上每一个 Case 的解决方案。

To - Be - Done

文章作者: Kiyoshi
文章链接: https://blog.k1yoshi.com/article/binary-trees-study-notes/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Kiyoshi's Blog