Rick

树（进阶篇）

发布于 2020-03-25 | 标签: 树 、 算法 | 22分钟 | 4764字数

上一篇介绍了树和二叉树的一些基本知识，存储结构，遍历，常见算法应用等，这一篇主要对树的另外一些高级数据结构进行梳理

二叉搜索树


什么是二叉搜索树？

一颗二叉树，可以为空；如果不为空，满足以下性质：

  • 非空左子树的所有键值小于其根节点的键值
  • 非空右子树的所有键值大于其根节点的键值
  • 左、右子树都是二叉搜素树

二叉搜索树常见算法

查找元素

  • Position Find(ElementType X, BinTree BST)：从二叉搜索树BST中查找元素X，返回其结点所在地址
TreeNode* Find(int x, TreeNode* root) {
    if (root == NULL) {
        return NULL;		// 查找失败
    }
    if (root->val > x) {
        return Find(x, root->left);		// 左子树递归查找
    }
    if (root->val < x) {
        return Find(x, root->right);	// 右子树递归查找
    }else
    {
        return root;		// 查找到结点
    }
}

TreeNode* Find(int x, TreeNode* root) {
    while (root != NULL) {
        if (root->val > x) {
            root = root->left;
        }else if (root->val < x)
        {
            root = root->right;
        }else
        {
            return root;
        }       
        return NULL;
    }   
}

查找的效率决定于树的高度

查找最值元素

  • Position FindMin(BinTree BST)：从二叉搜索树BST中查找并返回最小元素所在节点的地址
TreeNode* FindMin(TreeNode* root) {
    if (root == NULL) {
        return NULL;
    }
    if (root->left == NULL) {
        return root;
    }else
    {
        return FindMin(root->left);
    }
}
  • Position FindMax(BinTree BST)：从二叉搜索树BST中查找并返回最大元素所在节点的地址
TreeNode* FindMax(TreeNode* root) {
    if (root != NULL) {
        while (root->right != NULL) {
            root = root->right;
        }
    } 
    return root;
}

插入元素

  • BinTree Insert(ElementType X, BinTree BST)：插入元素X到二叉搜索树BST中

    TreeNode* insertIntoBST(TreeNode* root, int val) {
    // 若原树为空，生成并返回一个结点的二叉搜索树
  	if (root == NULL) {
      root = new TreeNode(val);
    }
  	// 开始查找要插入元素的位置
    if (root->val > val) {
      root->left = insertIntoBST(root->left, val);		// 递归处理左子树
    }else if (root->val < val)
    {
      root->right = insertIntoBST(root->right, val);	// 递归处理右子树
    }
    return root; 
}

删除元素

  • BinTree Delete(ElementType X, BinTree BST)：从二叉搜索树BST中删除元素X

    • 要删除叶结点：直接删除，并修改其父节点指针--置为NULL

      image-20200318231109608

    • 要删除的结点只有一个孩子结点：将其父节点的指针指向要删除节点的孩子结点

      image-20200318231314737

    • 要删除的结点有左、右两颗子树：

      用另一结点替代被删除结点：右子树的最小元素或者左子树的最大元素，这样就转换成了前两种情况

      image-20200318232206833 image-20200318232306027 image-20200318232247420 image-20200318232104915 
    TreeNode* deleteNode(TreeNode* root, int key) {
    TreeNode* temp = NULL;
    // 先查找到结点的位置
    if (root == NULL) {
      return root;
    }
    if (root->val > key) {
      root->left = deleteNode(root->left, key);
    }else if (root->val < key)
    {
      root->right = deleteNode(root->right, key);
    }else
    // 找到了要删除的结点，然后对三种情况进行判断
    {
        // 左右子树都有结点的情况
        if (root->left != NULL && root->right != NULL) {
            // 在右子树上找一个最小的结点对要删除的结点进行替代
            temp = FindMin(root->right);
            root->val = temp->val;
            // 转换成要删除的是叶子结点或者只有一个孩子结点的情况
            root->right = deleteNode(root->right, root->val);
        }else
            // 针对要删除的是叶子结点或者是只有一个孩子结点的情况
        {
            if (root->left == NULL) {
                root = root->right;
            }else if (root->right == NULL)
            {
                root = root->left;
            }
        }
    }
    return root; 
}

TreeNode* FindMin(TreeNode* root) {
  if (root == NULL) {
    return NULL;
  }
  if (root->left == NULL) {
    return root;
  }else
  {
    return FindMin(root->left);
  }
}

    TreeNode* deleteNode(TreeNode* root, int key) {
  if (!root) {
    return nullptr;
  }
  // 找到要删除的结点
  if (root->val == key) {
    // 如果右子树没有结点，直接删掉该结点并返回左子树
    if (!root->right) {
      TreeNode* left = root->left;
      delete root;
      return left;
    }else
    {
      // 如果右子树有结点，找到右子树的最小结点
      // 进行交换，这样下次删除的就是叶子结点，比较容易
      TreeNode* right = root->right;
      while (right->left) {
        right = right->left;
      }
      swap(root->val, right->val);
    }
  }
  root->left = deleteNode(root->left, key);
  root->right = deleteNode(root->right, key);
  return root;
}

判断一棵树是否为二叉搜索树

递归

乍一看：这是一个平凡的问题，只需要遍历整棵树，检查结点值node->right->val > node->val和node->left->val < node->val对每个结点都成立

image-20200320161835995

问题是，这种方法并不总是正确。不仅右子结点要大于该节点，整个右子树的元素都应该大于该节点。例如:

image-20200320161938824

这意味着我们需要在遍历树的同时保留结点的上界与下界，在比较时不仅比较子结点的值，也要与上下界比较。

bool isValidBST(TreeNode* root) {
  // 为了测试通过LeetCode测试用例，上边界和下边界使用了long的边界值
  return helper(root, LONG_MAX, LONG_MIN);
}
bool helper(TreeNode* root, long upper, long lower) {
    if (!root) {
      	return true;
    }
    int val = root->val;
    if (val >= upper) {
      	return false;
    }
    if (val <= lower) {
      	return false;
    }
    if (!helper(root->left, val, lower)) {
      	return false;
    }
    if (!helper(root->right, upper, val)) {
      	return false;
    }
    return true;
}

更为优雅的递归：

class Solution {
public:
    private:
    TreeNode* prev = NULL;
public:
    bool isValidBST(TreeNode* root) {
        if(!root)   return true;
        return isValidBST(root->left)  && help(root) && isValidBST(root->right);
    }
    
    bool help(TreeNode* root){
        if(!prev){
            prev = root;
            return true;
        }
        if(prev->val >= root->val)   return false;
        prev = root;
        return true;
    }
};

中序遍历为升序

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* node = root;
        vector<int> inorder;
        stack<TreeNode*> s;
        while (node || !s.empty()) {
            while (node) {
                s.push(node);
                node = node->left;
            }
            if (!s.empty()) {
                node = s.top();
                inorder.push_back(node->val);
                s.pop();
                node = node->right;
            }
        }
        // 验证中序序列是否为升序
        for (int i = 1; i < inorder.size(); i++) {
            if (inorder[i] <= inorder[i - 1]) {
                return false;
            }
        }
        return true;
    }
};


平衡二叉树(AVL树)


平衡二叉树概念

搜索树结点不同插入次序，将导致不同的深度和平均查找长度ASL

  • 平衡因子（Balance Factor）：BF(T) = hL - hR，其中hL 、hR分别表示T的左、右子树的高度。

平衡二叉树（Balanced Binary Tree）（AVL树）空树，或者任一结点左、右子树高度差的绝对值不超过1，即|BF(T)| ≤ 1

image-20200319175418894

注意：是对任意一个结点而言，不仅仅是根节点


平衡二叉树的高度

完全二叉树 高度log2n，设nh高度为h的平衡二叉树的最少结点数。结点数最少时：

有 nh = nh-1 + nh-2 + 1 ==> 斐波那契数列加1

image-20200319180157073

平衡二叉树的调整

在平衡二叉树进行插入结点后，可能会导致该二叉树不再是平衡二叉树，需要对结点位置进行调整：调整的原则一定要注意：调整完一定还要是二叉搜索树

####RR旋转

image-20200319183618370

不平衡的**“发现者”是Mar，“麻烦结点”**Nov在发现右子树的右边，因而叫RR插入，需要RR旋转（右单旋）

image-20200319183737281

注意：插入的结点不一定就是最右边的结点才算RR旋转，一定要明确的是：插入结点后，被破坏平衡的那个结点的右子树的右边（可以是左叶子结点也可以是右叶子结点，只要是在右子树的右边即可）就可

image-20200319184322231 image-20200319184440426

LL旋转

image-20200319191132018

Mar的平衡性和May的平衡性都被破坏，我们只需要解决第一个被破坏的结点Mar

“发现者”是Mar，“麻烦结点”Apr在发现者左子树的左边，因而交LL插入，需要LL旋转（左单旋）

image-20200319191437310

LR旋转

image-20200319192517997

“发现者”是May，“麻烦结点”Jan在左子树的右边，因而交LR插入，需要LR旋转

image-20200319192729272

RL旋转

image-20200319195734013 image-20200319202119089

堆


相关概念

优先队列（Priority Queue）：特殊的“队列”，取出元素的顺序是按照元素的优先权（关键字）大小，呃呃不是元素进入队列的先后顺序；我们发现当我们实现优先队列的时候，无论是数组、有序数组还是链表，我们都不能很好地去实现按优先权大小这个功能

堆

  • 结构性：用数组表示的完全二叉树

    image-20200322194055046

  • 有序性：任一结点的关键字是其子树所有节点的最大值（或最小值）

    • 最大堆：也称“大顶堆”：根节点是最大值
    • 最小堆：也称“小顶堆”：根节点是最小值
    image-20200322174322022

最大堆操作

创建最大堆

typedef int ElementType;
typedef struct HNode* Heap; /* 堆的类型定义 */
struct HNode {
    ElementType* Data; /* 存储元素的数组 */
    int Size;          /* 堆中当前元素个数 */
    int Capacity;      /* 堆的最大容量 */
};
typedef Heap MaxHeap; /* 最大堆 */

#define MAXDATA 1000  /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */

/**
 * @description: 创建容量为MaxSize的空的最大堆
 * @param int
 * @return: MaxHeap
 */ 
MaxHeap CreateMaxHeap (int MaxSize) {
    MaxHeap H = (MaxHeap) malloc (sizeof(struct HNode));
    H->Data = (ElementType*) malloc ((MaxSize + 1) * sizeof(ElementType));
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Data[0] = MAXDATA;   /* 定义"哨兵"为大于堆中所有可能元素的值*/
    return H;
}

最大堆插入结点

/**
 * @description: 将元素X插入最大堆H，其中H->Data[0]已经定义为哨兵
 * @param MaxHeap 
 * @param ElementType
 * @return: bool
 */
bool Insert (MaxHeap H, ElementType X) {
    int i;
    if (IsFull(H)) { 
        printf("最大堆已满\n");
        return false;
    }
    i = ++H->Size; /* i指向插入后堆中的最后一个元素的位置 */
    for (; H->Data[i / 2] < X; i /= 2)
        H->Data[i] = H->Data[i / 2]; /* 上滤X */
    H->Data[i] = X; /* 将X插入 */
    return true;
}

/**
 * @description: 判断堆是否达到最大容量
 * @param Heap
 * @return: bool
 */
bool IsFull(Heap H){
    return (H->Size == H->Capacity);
}

最大堆结点的删除

#define ERROR -1 /* 错误标识应根据具体情况定义为堆中不可能出现的元素值 */
/**
 * @description: 从最大堆H中取出键值为最大的元素，并删除一个结点
 * @param MaxHeap 
 * @return: ElementType
 */
ElementType DeleteMax (MaxHeap H) {
    int Parent, Child;
    ElementType MaxItem, X;
    if (IsEmpty(H)) {
        printf("最大堆已为空");
        return ERROR;
    }
    MaxItem = H->Data[1]; /* 取出根结点存放的最大值 */
    /* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */
    X = H->Data[H->Size--]; /* 注意当前堆的规模要减小 */
    for(Parent = 1; Parent * 2 <= H->Size; Parent = Child ) {
        Child = Parent * 2;
        if((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1]))
            Child++;  /* Child指向左右子结点的较大者 */
        if(X >= H->Data[Child]) break; /* 找到了合适位置 */
        else  /* 下滤X */
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;
    return MaxItem;
} 

/**
 * @description: 判断堆是否为空
 * @param Heap 
 * @return: bool
 */
bool IsEmpty(Heap H) {
    return (H->Size == 0);
}

最大堆的建立

建立最大堆：将已经存在的N个元素按最大堆的要求存放在一个一维数组中

  • 方法1：通过插入操作，将N个元素一个个相继插入到一个初始化为空的堆中去，时间代价为O(NlogN)
  • 方法2：在线性时间复杂度下建立最大堆
    • 将N个元素按输入顺序存入，先满足完全二叉树的结构特性
    • 调整各结点位置，以满足最大堆的有序特性
/**
 * @description: 调整H->Data[]中的元素，使满足最大堆的有序性
 * @param MaxHeap 
 */
void BuildMaxHeap(MaxHeap H) {
    /* 这里假设所有H->Size个元素已经存在H->Data[]中 */
    int i;
    /* 从最后一个结点的父节点开始，到根结点1 */
    for(i = H->Size / 2; i > 0; i--)
        PercDown(H, i);
}

/**
 * @description: 下滤：将H中以H->Data[p]为根的子堆调整为最大堆
 * @param MaxHeap
 * @param int 
 */
void PercDown(MaxHeap H, int p) {
    int Parent, Child;
    ElementType X;
    X = H->Data[p]; /* 取出根结点存放的值 */
    for(Parent = p; Parent * 2 <= H->Size; Parent = Child ) {
        Child = Parent * 2;
        if((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1]) )
            Child++;  /* Child指向左右子结点的较大者 */
        if(X >= H->Data[Child]) break; /* 找到了合适位置 */
        else  /* 下滤X */
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;
}

堆排序

算法1

void HeapSort1 (ElementType A[], int N) {
  BuildHeap(A);
  for (i = 0; i < N; i++) {
    tempA[i] = DeleteMin(A);
  }
  for (i = 0; i < N; i++) {
    A[i] = tempA[i];
  }
}

时间复杂度为O(NlogN)；

需要额外O(N)空间，并且复制元素需要时间

算法2

typedef int ElementType;

/**
 * @brief 交换元素
 * @param a 
 * @param b 
 */
void Swap(ElementType *a, ElementType *b) {
    ElementType t = *a;
    *a = *b;
    *b = t;
}

/**
 * @brief 向下过滤，将N个元素的数组中以A[p]为根的子堆调整为最大堆
 * @param A 
 * @param p 
 * @param N 
 */
void PercDown(ElementType A[], int p, int N) {
    int Parent, Child;
    ElementType X;

    X = A[p]; /* 取出根结点存放的值 */
    for (Parent = p; (Parent * 2 + 1) < N; Parent = Child) {
        Child = Parent * 2 + 1; // 从0开始，不同之前堆是从1开始
        if ((Child != N - 1) && (A[Child] < A[Child + 1]))
            Child++; /* Child指向左右子结点的较大者 */
        if (X >= A[Child])
            break; /* 找到了合适位置 */
        else       /* 下滤X */
            A[Parent] = A[Child];
    }
    A[Parent] = X;
}

/**
 * @brief 堆排序
 * @param A 
 * @param N 
 */
void HeapSort(ElementType A[], int N) {
    int i;
    for (i = N / 2; i >= 0; i--) /* 建立最大堆 */
        PercDown(A, i, N);
    for (i = N - 1; i > 0; i--) {
        /* 删除最大堆顶 */
        Swap(&A[0], &A[i]);
        PercDown(A, 0, i);
    }
}


哈夫曼树与编码


基础概念

带权路径长度（WPL）：设二叉树有n个叶子结点，每个叶子结点带有权值wk，从根节点到每个叶子结点的长度为Ik，则每个叶子结点的带权路径长度之和就是 WPL = ∑wkIk

最优二叉树获哈夫曼树：WPL最小的二叉树


哈夫曼树的构造

每次把权值最小的两颗二叉树合并，如何每次找到最小的权值 ==> 最小堆

#include <iostream>
using namespace std;
#define MINDATA -1     /* 该值应根据具体情况定义为小于堆中所有可能元素的值 */

typedef struct HuffmanTreeNode* HuffmanTree;
struct HuffmanTreeNode {    /* 哈弗曼树结点定义 */
    int weight;             /* 权值 */
    HuffmanTree left, right;
};

typedef HuffmanTreeNode* ElementType;   /* 哈弗曼树结点的指针为ElementType */
typedef struct HNode* Heap; /* 堆的类型定义 */
typedef Heap MinHeap;       /* 最小堆 */
struct HNode {
    ElementType* Data;      /* 存储元素的数组 */
    int Size;               /* 堆中当前元素个数 */
    int Capacity;           /* 堆的最大容量 */
};

/**
 * @description: 创建容量为MaxSize的最小堆
 * @param int 
 * @return: MinHeap
 */
MinHeap CreateMinHeap (int MaxSize) {
    MinHeap H = (MinHeap)malloc(sizeof(struct HNode));
    H->Data = (ElementType*)malloc((MaxSize + 1) * sizeof (ElementType));
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Data[0]->weight = MINDATA;  /* 定义"哨兵"为小于堆中所有可能元素的值*/
    return H;
}

/**
 * @description: 判断堆是否达到最大容量
 * @param MinHeap
 * @return: bool
 */
bool IsFull(MinHeap H){
    return (H->Size == H->Capacity);
}

/**
 * @description: 将元素X插入最小堆H，其中H->Data[0]已经定义为哨兵
 * @param MinHeap
 * @param ElementType 
 * @return: bool
 */
bool Insert (MinHeap H, ElementType X) {
    int i;
    if (IsFull(H)) {
        printf("最小堆已满\n");
        return false;
    }
    i = ++H->Size;  /* i指向插入后堆中的最后一个元素的位置 */
    for (; H->Data[i / 2]->weight > X->weight; i /= 2) {
        H->Data[i] = H->Data[i / 2];    /* 上滤X */
    }
    H->Data[i] = X; /* 将X插入 */
}

/**
 * @description: 判断堆是否为空
 * @param MinHeap 
 * @return: bool
 */
bool IsEmpty(MinHeap H) {
    return (H->Size == 0);
}

/**
 * @description: 从最小堆H中取出键值为最小的元素，并删除一个结点
 * @param MinHeap 
 * @return: ElementType
 */
ElementType DeleteMin (MinHeap H) {
    int Parent, Child;
    ElementType MinItem, X;
    if (IsEmpty(H)) {
        printf("最小堆已为空\n");
        return;
    }
    MinItem = H->Data[1];   /* 取出根结点存放的最小值 */
    X = H->Data[H->Size--];
    for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {
        Child = Parent * 2;
        if ((Child != H->Size) && (H->Data[Child]->weight > H->Data[Child + 1]->weight))
            Child++;    /* Child指向左右子结点的较小者 */
        if (X->weight <= H->Data[Child]->weight) break; /* 找到了合适的位置 */
        else  /* 下滤X */
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;
    return MinItem;
}

/**
 * @description: 下滤：将H中以H->Data[p]为根的子堆调整为最小堆
 * @param MaxHeap
 * @param int 
 */
void PercDown(MinHeap H, int p) {
    int Parent, Child;
    ElementType X;
    X = H->Data[p]; /* 取出根结点存放的值 */
    for(Parent = p; Parent * 2 <= H->Size; Parent = Child) {
        Child = Parent * 2;
        if((Child != H->Size) && (H->Data[Child]->weight > H->Data[Child + 1]->weight))
            Child++;  /* Child指向左右子结点的较大者 */
        if(X->weight <= H->Data[Child]->weight) break; /* 找到了合适位置 */
        else  /* 下滤X */
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;
}

/**
 * @description: 调整H->Data[]中的元素，使满足最大堆的有序性
 * @param MaxHeap 
 */
void BuildMinHeap(MinHeap H) {
    /* 这里假设所有H->Size个元素已经存在H->Data[]中 */
    int i;
    /* 从最后一个结点的父节点开始，到根结点1 */
    for(i = H->Size / 2; i > 0; i--)
        PercDown(H, i);
}

/**
 * @description: 利用最小堆构建哈弗曼树
 * @param MinHeap 
 * @return: HuffmanTree
 */
HuffmanTree Huffman (MinHeap H) {
    /* 假设H->Size个权值赢存在H->Elements[]->weight里 */
    int i;
    HuffmanTree T;
    BuildMinHeap(H);    /* 将H->Elements[]按权值调整为最小堆 */
    for (i = 1; i < H->Size; i++) {     /* 合并 */
        T = (HuffmanTree)malloc(sizeof(struct HuffmanTreeNode));
        T->left = DeleteMin(H);     /* 从最小堆删除一个结点，作为左结点 */
        T->right = DeleteMin(H);    /* 从最小堆删除一个结点，作为右结点 */
        T->weight = T->left->weight + T->right->weight; /* 计算新权值 */
        Insert(H, T);               /* 将新T插入最小堆 */
    }
    T = DeleteMin(H);
    return T;
}

哈弗曼编码

  • 根据字符出现的频次，进行不等长编码，提高编码的效率，频率高的字符编码尽量短。但是不等长编码会带来二义性的问题

  • 避免二义性：前缀码 （prefix code）：任何字符的编码都不是领字符编码的前缀，这样就可以无二义性地解码

  • 规定在哈弗曼树中左分支为0，右分支为1，则从根节点到每个叶子结点所经过的分支对应的0和1组成的序列便是该结点对应的哈弗曼编码

    image-20200324171431840


并查集


基础概念

并查集是一种维护集合的数据结构。

  • 并：Union（合并）合并两个集合
  • 查：Find（查找）判断两个元素是否在同一个集合里面
  • 集：Set（集合）

并查集实现一般使用数组来实现，数组中每个元素类型定义为SetType

typedef int ElementType;
typedef struct {
    ElementType data;
    int parent;		// 指向parent数组下标
}SetType;
image-20200324181835578 image-20200324181930573

集合运算

查找

/**
 * @brief 查找某个元素所在集合
 * @param S 
 * @param X 
 * @return int 
 */
int Find(SetType S[], ElementType X) {
    int i;
    for (i = 0; i < MaxSize && S[i].data != X; i++);
    if (i >= MaxSize)
        return -1;  // 未找到返回-1
    for (; S[i].parent > 0; i = S[i].parent);
    return i;       // 找到 X 所在集合，返回树根结点在数组 X 中的下标
}

并

  • 分别找到X1和X2两个元素所在集合树的根节点
  • 如果他们不同根，将其中一个根节点的父结点指针设置成另一个根节点的数组下标
  • 为了提高合并后查找的性能，我们可以采用小的集合合并到大的集合里面
  • 如何知道两个集合谁大谁小？ ==> 我们可以看到当一个元素为根节点的时候，他的parent为-1，那么我们可以对其进行修改变为 -集合元素个数
image-20200324190115919 
/**
 * @brief 合并两个元素所在集合树根节点
 * @param S 
 * @param X1 
 * @param X2 
 */
void Union (SetType S[], ElementType X1, ElementType X2) {
    int root1, root2;
    root1 = Find(S, X1);
    root2 = Find(S, X2);
    // 集合1比较大，将集合2并入集合1
    if (S[root1].parent < S[root2].parent) { 
        S[root1].parent += S[root2].parent;
        S[root2].parent = root1;
    } else {
        S[root2].parent += S[root1].parent;
        S[root1].parent = root2;
    }
}
赞赏
# 树 # 算法
已运行:
浏览数: 次 | 访客数: 人
Powered by Gridea
0%