Java Map 与 Set 数据结构及实现原理

Map 和 Set

1. Map 和 Set 用于搜索
2. 搜索树：二叉搜索树 -> AVL 树 -> 红黑树
3. AVL 树：高度平衡的二叉搜索树
4. TreeMap 和 TreeSet 底层是红黑树，每次存储元素都得进行大小比较

二叉搜索树

1. 二叉搜索树：如果左子树不为空，那么左子树所有节点都小于根节点；如果右子树不为空，那么右子树所有节点都大于根节点；它的左右子树都是二叉搜索树。
2. 二叉搜索树的中序遍历是有序的

查找

比 key 大往右找，比 key 小往左找。

// 查找
public boolean search(int key) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val > key) {
            cur = cur.left;
        } else if (cur.val < key) {
            cur = cur.right;
        } else {
            return true;
        }
    }
    return false;
}

分析

1. 时间复杂度：
   • 最好情况：O(logN)，完全二叉树
   • 最坏情况：O(N)，单分支的二叉树

插入

// 插入
public boolean insert(int key) {
    TreeNode node = new TreeNode(key);
    TreeNode parent = null;
    if (root == null) {
        root = node;
         ;
    }
       root;
     (cur != ) {
         (cur.val < key) {
            parent = cur;
            cur = cur.right;
        }   (cur.val > key) {
            parent = cur;
            cur = cur.left;
        }  {
            
             ;
        }
    }
     (parent.val < key) {
        parent.right = node;
    }  {
        parent.left = node;
    }
     ;
}