树01

相关链接:

https://juejin.im/entry/58f4268f61ff4b0058fcb190
https://juejin.im/entry/583fbe5461ff4b006b82c771
https://juejin.im/entry/57dfa545128fe10064d60a94
https://juejin.im/entry/586876771b69e6006b42b94f
https://juejin.im/entry/58462c61a22b9d007aa4aa6b
https://juejin.im/entry/58371f13a22b9d006882902d
https://juejin.im/entry/56eecbb6128fe100513d1a20

1、二叉搜索树:

顺序性: 某节点的所有左子树都不大于该节点, 所有右子树都不小于该节点;

Paste_Image.png

2、出度:

节点r的孩子的个数称为节点r的出度;

3、二叉树:

节点度数不超过2的树称作二叉树;

4、遍历:

树遍历的三种方式.png 先序遍历.png

5、树的类型:

1、二叉查找树(二叉排序树);
2、平衡二叉树(AVL树);
3、红黑树;
4、B-树;
5、B+树;
6、字典树;
7、后缀树;
8、广义后缀树;

1、二叉查找树(二叉排序树)

二叉查找树
性质:

1、若它的左子树不为空, 则左子树上的所有节点的值都小于它的根节点的值;
2、若它的右子树不为空, 则右子树上所有节点的值都大于它的根节点的值;
3、其他的左右子树也分别为二叉查找树;
4、二叉查找树是动态查找树, 在查找过程中可见添加和删除相应的元素, 在这些操作中需要保持二叉查找树的以上性质;
在Java的实现中, 每个节点(Node)由四个域组成: Key、value、left、right. 即:键, 值, 左子树, 右子树;

private class Node {
    private Key key;
    private Value val;
    private Node left, right;
    public Node(Key key, Value val) {
        this.key = key;
        this.val = val;
    }
}

二叉查找树

查找:

public Value get(Key key) {
    Node x = root;
    while (x != null) {
         int cmp = key.compareTo(x.key);
         if (cmp < 0) {
             x = x.left;
         } else if (cmp > 0) {
             x = x.right;
         }  else {
             return x.val;
         } 
    }
    return null;
}

插入：如果小，往左；如果大，往右；如果null，插入；如果存在，覆盖。

public void put(Key key, Value val) {
    root = put(root, key, val);
}
private Node put(Node x, Key key, Value val) {
    if (x == null) return new Node(key, val);
    int cmp = key.compareTo(x.key);
    if (cmp < 0) {
        x.left = put(x.left, key, val);
    } else if (cmp > 0) {
        x.right = put(x.right, key, val);
    } else { // if (cmp == 0)
        x.val = val;
    }
    return x;
}

public void rotateLeft(Node h) {
    Node x = h.right;
    h.right = x.right;
    x.left = h;
}

AVL树(平衡二叉树)

平衡二叉树是一种二叉排序树, 其中每一个结点的左子树和右子树的高度差不超过1.
二叉树的平衡因子等于该结点的左子树深度减去右子树深度的值. 平衡因子只有三种值: -1, 0, 1;
距离插入结点最近的, 且平衡因子的绝对值大于1的结点为根的自述

1、二叉树的好处:

二叉排序树是一种比较有用的折中方案,
数组的搜索比较方便, 可以直接用下标, 但删除或者插入某些元素就比较麻烦.
链表增删快, 查找慢.
二叉排序树就既有链表的好处，也有数组的好处。
在处理大批量的动态的数据是比较有用。
文件系统和数据库系统一般都采用树（特别是B树）的数据结构数据，主要为排序和检索的效率。二叉树是一种最基本最典型的排序树，用于教学和研究树的特性，本身很少在实际中进行应用，因为缺点太明显了（看看教科书怎么说的）。就像冒泡排序一样，虽然因为效率问题并不实用，单不失一种教学例子的好手段。