数据结构 | 二叉搜索树即其平衡 | UntitledPenguin Factory—

[最后更新于 2024-05-15]

今天（2024-05-12）更新二叉搜索树（Binary Search Tree）和平衡树的相关内容

属性

二叉搜索树是一种二叉树的树形数据结构，其满足如下特性：

若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
二叉搜索树的左右子树均为二叉搜索树。

二叉搜索树能够维护一个有序的动态队列，平衡的二叉搜索树能够将插入、删除等基本操作的时间复杂度控制在O（ $\log_2 n$ ），这与普通的队列相比高效许多。

基本操作

查询最大值/最小值 一直回溯查询左节点直至某节点左子树为空（反之亦然）

查询前驱值/后继值

若左子树不为空返回左子树中最大值（最靠右的节点）
若左子树为空则不断向上查找根节点在第一个向左的根节点处停下来否则没有前驱节点

顺序遍历 若左子树不为空递归调用遍历左子树打印根结点值若右子树不为空递归调用遍历右子树

查询/删除值为k的节点 查询：比较k与当前根结点值，若大于k则向左查找（若此时左子树为空则查无此k），若小于k则向右查找（同理，若无右子树则查无此k）。删除：若k所在节点为叶子节点直接删除若k只有一个子树，则该子树直接继承k所在位置若k有两个节点，则查找k的前驱节点（左子树中的最大值），交换k和该前驱的位置，再将k删除。

查找在第i位的节点值

用size（root）记录subtree 的节点数量：

	->a=size（left subtree）
	if a=i-1 return x
	if a>=i 那么查询回溯左子树
	if a<i-1 以 i-a-1回溯查询右子树

平衡树

刚刚提到，平衡的二叉搜索树的时间复杂度在 $\log_2 n$ ，但是若树不平衡（左右子树高度相差很多），甚至退化为链（某一边子树为空），那么其作为二叉搜索树的优势则无法实现。

所以，为了保证树的高度维持在 $\log_2 n$ 上下以保证一系列搜索查询操作的高效，那么就要对树的平衡性进行不断考察和维护。

实现方法举例：

红黑树：

属性：

每个节点都标记红或黑两种颜色中的一种根结点永远是黑红色不可在父子中相邻保证所有根到叶的路径中经过的黑色节点数目相同

证明：n个节点的红黑树高度不超过2 $\log_2 n+1$

设每条root-null（根到叶）路径经过不少于k个节点，那么n>=2^k-1 有 k不大于

\log_2 n

- 即每条路径至多有

\log_2 n+1

个黑色节点又因为每条路径中红色节点数目不超过黑色，所以每条路径的总结点数不超过2

\log_2 n+1

图解：

AVL树：

引入一个balance factor来记录左子树和右子树高度的差值若树平衡，则该值一直得处在-1 0 1之间；否则树失衡，需要对树进行旋转操作来重新平衡。

图解：

替罪羊树：

替罪羊树引入了一个平衡系数alpha（一般采用0.7左右）来检查k处的某个子树大小在k中的占比，若超过一定比例，那么在k处重构。比如取alpha为2/3，若某个发现k处左子树的大小以及占比超过其2/3，那么就在k处对树进行重构：一般将树中节点存入数组后再重新建树即可。在插入新节点时，若发现此处树高过高（例如超过了1/alpha（log2 n）），那么我们向上不断查询直至找到一个平衡系数不合格替罪羊节点然后在替罪羊处重构。

图解：

堆树（treap）：

对每个节点随机生成一个优先值priority（需要是随机的，range要足够大，可以容纳树上的所有节点），然后对于每个节点的关键字key维护其搜索树的性质，但同时对 priority维护堆的属性（通过旋转来实现）

注意由于算法不同，其对于树平衡与否的判定也有所不同（比如上图中某些树在AVL中已经不平衡，但在替罪羊树中却仍然算作平衡），使用时需要综合考虑效率来应用。

重新平衡：

旋转（操作时间复杂度在O(1)）

x - y左旋： y变为x的父节点，且继承x的父节点p，维持其原来的右子树c x变为y的左子树，维持其原有的左子树a 再将y的左子树b（大于x且小于y的部分），变为x的右子树

x - y右旋同理 y变为x的父节点，且继承x的父节点p，维持其原来的左子树a x变为y的右子树，维持其原来的右子树c 再将y的右子树b（大于y且小于x的部分），变为x的左子树

演示：

代码：用AVL实现BST：

虽然AVL的操作有点繁琐，但是其实其记录两边树高的方法很符合本人直觉，所以就试着写写。由于懒惰（……），只写了insert没有写delete。耶( •̀ ω •́ )y。

class TreeNode:

    def __init__(self,key):

       self.key=key
       self.left=None
       self.right=None
       self.height=1

  
class AVLBST:

    def __init__(self):
        self.root=None

    def search(self, key):
        return self.searching(self.root, key)

    def searching(self, currentroot, key):
        if not currentroot:return False
        if currentroot.key == key:
            return True
        if key < currentroot.key:
            return self.searching(currentroot.left, key)
        return self.searching(currentroot.right, key)

    def getheight(self,root):

        if root is None:
            return 0
        return root.height

    def avlfactor(self, root):
    
        if root is None:
            return 0
        return self.getheight(root.left) - self.getheight(root.right)

    def insert(self,key):
        self.root=self.inserting(self.root,key)

    def inserting(self,currentroot,key):
        if currentroot is None:
            return TreeNode(key)
        if key<currentroot.key:
            currentroot.left=self.inserting(currentroot.left,key)
        else:
            currentroot.right=self.inserting(currentroot.right,key)
	               currentroot.height=1+max(self.getheight(currentroot.left),self.getheight(currentroot.right))

        balance=self.avlfactor(currentroot)
        if balance>1 and key<currentroot.left.key:
            return self.rightrotate(currentroot)
        if balance< -1 and key>currentroot.right.key:
            return self.leftrotate(currentroot)
        if balance>1 and key>currentroot.left.key:
            currentroot.left=self.rightrotate(currentroot.left)
            return self.rightrotate(currentroot)
        if balance< -1 and key<currentroot.right.key:
            currentroot.right=self.leftrotate(currentroot.right)
            return self.leftrotate(currentroot)

        return currentroot      
  

    def leftrotate(self,x):

        y = x.right
        T2 = y.left
        y.left = x
        x.right = T2

        x.height = 1 + max(self.getheight(x.left), self.getheight(x.right))
        y.height = 1 + max(self.getheight(y.left), self.getheight(y.right))

        return y

  
    def rightrotate(self,x):

        y = x.left
        T2 = y.right
        y.right = x
        x.left = T2

        x.height = 1 + max(self.getheight(x.left), self.getheight(x.right))
        y.height = 1 + max(self.getheight(y.left), self.getheight(y.right))

        return y

    def treeprint(self):
        self.subtreeprint(self.root)
        
    def subtreeprint(self,currentroot):
        if currentroot:
          print("(",end="")
          self.subtreeprint(currentroot.left)
          print(currentroot.key,end="")
          self.subtreeprint(currentroot.right)
          print(")",end="")

MyTree=AVLBST()
MyTree.insert(10)
MyTree.insert(20)
MyTree.insert(30)
MyTree.insert(40)
MyTree.insert(50)
MyTree.insert(60)
MyTree.insert(70)
MyTree.treeprint()
x=int(input())
if MyTree.search(x): print(str(x)+" is in the Tree")
else: print(str(x)+" is in the Tree")

这周的学习就到这里啦。下周想要再给堆和BST进行插图的工作以便巩固和加深自己的理解，同时也是试用一下博客的图片嵌入功能。所以这一篇和上一篇都可看做 ~~未完待续~~

-鹅仔 2024/5/12 19：29

伟大而忙碌的星期三，我竟然下班在完善博客。今天把堆和树的插图都搞定了。最近已经来到了哈希表的部分，预计周末就会更新了。昨天上班隔壁组的德国老哥感叹我十分勤奋，怀疑我是否下了班还偷偷学习新技术我的内心：嗯…怎么不算呢

-鹅仔 2024/5/15 21：41