精华内容
下载资源
问答
  • 平衡搜索树-AVLTree

    千次阅读 2018-03-27 00:07:33
    又称为高度平衡的二叉搜索树。它能保持二叉树的高度平衡,尽量降低二叉树的高度,减少树的平均搜索长度。 AVL树的性质 左子树和右子树的高度之差的绝对值不超过1 树中的每一个左子树和右子树都是AVL树 每个...

    AVL树

    又称为高度平衡的二叉搜索树。它能保持二叉树的高度平衡,尽量降低二叉树的高度,减少树的平均搜索长度。


    AVL树的性质

    1. 左子树和右子树的高度之差的绝对值不超过1
    2. 树中的每一个左子树和右子树都是AVL树
    3. 每个节点都有一个平衡因子,任一节点的平衡因子是-1或0或1.(每个节点的平衡因子等于右子树的高度减去左子树的高度,即:bf = rightHeigh - leftHeight)

    AVL树的效率

    一颗AVL树有N个节点,其高度可以保持在log2N(表示log以2为底N的对数),插入/删除/查找的时间复杂度也是log2N.


    更新平衡因子

    这里写图片描述

    1. cur在parent左,p bf - -
    2. cur在parent 右,p bf++
      • p == 0;p树高度不变
      • |p| == 1;高度变了,继续更新
      • |p| == 2;不再更新,旋转平衡起来

    插入

    1. 右单旋转—— RotateR
    2. 左单旋转—— RotateL
    3. 右左双旋转— RotateRL
    4. 左右双旋转— RotateLR
    右单旋转

    这里写图片描述

    void RotateR(Node* parent)
        {
            Node* subL = parent->_left;
            Node* subLR = subL->_right;
            parent->_left = subLR;
            if(subLR)
                subLR->_parent = parent;
            subL->_right = parent;
            Node* ppNode = parent->_parent ;
            parent->_parent = subL;
            if(parent == _root)
            {
                _root = subL;
                _root->_parent = NULL;
            }
            else
            {
                if(ppNode->_left == parent)
                {
                    ppNode->_left = subL;
                }
                else
                {
                    ppNode->_right = subL;
                }
                subL->_parent = ppNode;
            }
            parent->_bf = subL->_bf = 0;
        }
    左单旋转

    这里写图片描述

    void RotateL(Node* parent)
        {
            Node* subR = parent->_right;
            Node* subRL = subR->_left;
            parent->_right = subRL;
            if(subRL)
                subRL->_parent = parent;
            subR->_left = parent;
            Node* ppNode = parent->_parent ;
            parent->_parent = subR;
            if(parent == _root)
            {
                _root = subR;
                _root->_parent = NULL;
            }
            else
            {
                if(ppNode->_right == parent) 
                {
                    ppNode->_right = subR;
                }
                else
                {
                    ppNode->_left = subR;
                }
                subR->_parent = ppNode;
            }
            parent->_bf = subR->_bf = 0;
        }
    右左双旋转

    这里写图片描述

    void RotateRL(Node* parent)
        {
            Node* subR = parent->_right;
            Node* subRL = subR->_left;
            int bf = subRL->_bf;
            RotateR(parent->_right);
            RotateL(parent);
            if(bf == 0)
            {
                subR->_bf = parent->_bf = subRL->_bf = 0;
            }
            else if(bf == 1)
            {
                parent->_bf = -1;
                subR->_bf = 0;
                subRL->_bf = 0;
            }
            else
            {
                parent->_bf = 0;
                subR->_bf = 1;
                subRL->_bf = 0;
            }
        }
    左右双旋转

    左右的图和右左图类似

     void RotateLR(Node* parent)   //左右双旋  
        {  
            Node* subL = parent->_left;  
            Node* subLR = subL->_right;  
            int bf = subLR->_bf;  
            RotateL(subL);  
            RotateR(parent);  
    
            if (bf == 0)  
                parent->_bf =subLR->_bf= subL->_bf = 0;  
            else if (bf == 1)  
            {  
                parent->_bf = subLR->_bf = 0;  
                subL->_bf = -1;  
            }  
            else if (bf == -1)  
            {  
                parent->_bf = 1;  
                subL->_bf = subLR->_bf = 0;  
            }  
        }  

    判断是不是平衡二叉树:


    具体代码实现看这篇文章:
    https://blog.csdn.net/qq_37941471/article/details/79748878

    代码实现:


    • AVLTree.h
    • test.cpp

    AVLTree.h

    //#pragma once
    #include <iostream>
    using namespace std;
    
    template<class K,class V>
    struct AVLTreeNode
    {
        K _key;
        V _value;
        int _bf;
        AVLTreeNode<K,V>* _left;
        AVLTreeNode<K,V>* _right;
        AVLTreeNode<K,V>* _parent;
    
        AVLTreeNode(const K& key,const V& value)
            :_key(key)
            ,_value(value)
            ,_bf(0)
            ,_left(NULL)
            ,_right(NULL)
            ,_parent(NULL)
        {}
    };
    
    template<class K,class V>
    class AVLTree
    {
        typedef AVLTreeNode<K,V> Node;
    public:
        AVLTree()
            :_root(NULL)
        {}
    
        //插入
    
        bool Insert(const K& key,const V& value)
        {
            if(_root == NULL)
            {
                _root = new Node(key,value);
                return true;
            }
            Node* cur = _root;
            Node* parent = NULL;
            while(cur)
            {
                if( cur->_key < key)//根 < 插入的节点
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if( cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left ;
                }
                else
                {
                    return false;
                }
            }
    
            cur = new Node(key,value);
            if(parent->_key < key)
            {
                parent->_right = cur;
                cur->_parent = parent;
            }
            else if(parent->_key > key)
            {
                parent->_left = cur;
                cur->_parent = parent;
            }
    
        //更新平衡因子 
        //1.cur在parent左,p bf-- 
        //2.cur在parent 右,p bf++
        //p == 0;p树高度不变
        //|p| == 1;高度变了,继续更新
        //|p| == 2;不再更新,旋转平衡起来
    
            while(parent)
            {
                if(cur == parent->_left)
                {
                    parent->_bf--;
                }
                else
                {
                    parent->_bf++;
                }
                if(parent->_bf == 0)
                {
                    break;
                }
                else if(parent->_bf == 1 || parent->_bf == -1)
                {
                    //从树下往上更新
                    cur = parent;
                    parent = cur->_parent;
                }
                else if(parent->_bf == -2 || parent->_bf == 2)
                {
                    if(parent->_bf == 2)
                    {
                        if(cur->_bf == 1)
                        {
                            RotateL(parent);
                        }
                        else //-1
                        {
                            RotateRL(parent);
                        }
                    }
                    else // -2
                    {
                        if(cur->_bf == -1)
                        {
                            RotateR(parent);
                        }
                        else // 1
                        {
                            RotateLR(parent);
                        }
                    }
                }
                break;
            }
        }
    
        void InOrder()
        {
            _InOrder(_root);
            cout<<endl;
        }
        void _InOrder(Node* root)//中序遍历 左中右
        {
            if(root == NULL)
                return;
            _InOrder(root->_left);
            cout<<root->_key<<" ";
            _InOrder(root->_right);
        }
    //右单旋转
        void RotateR(Node* parent)
        {
            Node* subL = parent->_left;
            Node* subLR = subL->_right;
            parent->_left = subLR;
            if(subLR)
                subLR->_parent = parent;
            subL->_right = parent;
            Node* ppNode = parent->_parent ;
            parent->_parent = subL;
            if(parent == _root)
            {
                _root = subL;
                _root->_parent = NULL;
            }
            else
            {
                if(ppNode->_left == parent)
                {
                    ppNode->_left = subL;
                }
                else
                {
                    ppNode->_right = subL;
                }
                subL->_parent = ppNode;
            }
            parent->_bf = subL->_bf = 0;
        }
    
     //左单旋转
    
        void RotateL(Node* parent)
        {
            Node* subR = parent->_right;
            Node* subRL = subR->_left;
            parent->_right = subRL;
            if(subRL)
                subRL->_parent = parent;
            subR->_left = parent;
            Node* ppNode = parent->_parent ;
            parent->_parent = subR;
            if(parent == _root)
            {
                _root = subR;
                _root->_parent = NULL;
            }
            else
            {
                if(ppNode->_right == parent) 
                {
                    ppNode->_right = subR;
                }
                else
                {
                    ppNode->_left = subR;
                }
                subR->_parent = ppNode;
            }
            parent->_bf = subR->_bf = 0;
        }
    
    //右左双旋转
    
        void RotateRL(Node* parent)
        {
            Node* subR = parent->_right;
            Node* subRL = subR->_left;
            int bf = subRL->_bf;
            RotateR(parent->_right);
            RotateL(parent);
            if(bf == 0)
            {
                subR->_bf = parent->_bf = subRL->_bf = 0;
            }
            else if(bf == 1)
            {
                parent->_bf = -1;
                subR->_bf = 0;
                subRL->_bf = 0;
            }
            else
            {
                parent->_bf = 0;
                subR->_bf = 1;
                subRL->_bf = 0;
            }
        }
    
    //左右双旋转
         void RotateLR(Node* parent)   //左右双旋  
        {  
            Node* subL = parent->_left;  
            Node* subLR = subL->_right;  
            int bf = subLR->_bf;  
            RotateL(subL);  
            RotateR(parent);  
    
            if (bf == 0)  
                parent->_bf =subLR->_bf= subL->_bf = 0;  
            else if (bf == 1)  
            {  
                parent->_bf = subLR->_bf = 0;  
                subL->_bf = -1;  
            }  
            else if (bf == -1)  
            {  
                parent->_bf = 1;  
                subL->_bf = subLR->_bf = 0;  
            }  
        }  
    
         //判断是不是平衡搜索树
         //1. 递归——时间复杂度n^2
         //      (递归的次数*每次递归的次数)
         //        每个节点的遍历*高度(也是遍历整个树)
         //bool IsBalance()  
         //{  
            // int depth = 0;
      //       return _IsBalance(_root);  
         //} 
         //int MaxDepth(Node* root)  
         //{  
            //if (NULL == root)  
            //  return 0;  
            //int left = MaxDepth(root->_left)+1;  
            //int right = MaxDepth(root->_right) + 1;  
            //return left > right ? left : right;  
         //}  
         //bool _IsBalance(Node* root)
         //{
            // //递归的终止条件
            // if(root == NULL)
            // {
            //   return true;
            // }
            // int leftHeight = MaxDepth(root->_left);
            // int rightHeight = MaxDepth(root->_right);
            // return abs(rightHeight-leftHeight) < 2
            //   && _IsBalance(root->_left)
            //   && _IsBalance(root->_right);
         //}
         //2. 优化——时间复杂度O(n)——高度只遍历一次
          bool IsBalance() 
          {  
             int depth = 0;
             return _IsBalance(_root,depth);  
          } 
        bool _IsBalance(Node* root,int& depth)
        {
            if(root == NULL)
            {
                return true;
            }
            int left = 0;
            int right = 0;
            if(_IsBalance(root->_left,left)&&_IsBalance(root->_right,right))
            {
                if( abs(left-right) > 1 )
                    return false;
                depth = (left > right ? left : right)+1;
                return true;
            }
            return false;
        }
        /*  bool _IsBalance(Node* root,int& depth)  
          {  
              if(root == NULL)
              {
                  depth = 0;
                  return true;
              }
              int leftdepth = 0;
              int rightdepth = 0;
              if(_IsBalance(root->_left,leftdepth) == false)
                  return false;
              if(_IsBalance(root->_right,rightdepth) == false)
                  return false;
              if(rightdepth - leftdepth != root->_bf)
              {
                   cout << root->_key << "平衡因子异常" << endl;  
                   return false;  
              }
              depth = leftdepth > rightdepth ? leftdepth+1 : rightdepth+1;
          }  */
    private:
        Node* _root;
    };
    
    

    test.cpp

    #include "AVLTree.h"
    
    void testAVLTree()
    {
        AVLTree<int, int> t;  
        int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
        int depth = 0;
        for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); i++)  
        {  
            t.Insert(a[i], i);  
            cout << "isbalance?"<<t.IsBalance() <<"插入"<< a[i] << endl;  
        }  
        t.InOrder();  
        t.IsBalance();  
        AVLTree<int, int> t1;  
        int a1[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };  
        for (size_t i = 0; i < sizeof(a1) / sizeof(a1[0]); i++)  
        {  
            t1.Insert(a1[i], i);  
            cout << "isbalance?" << t1.IsBalance() << "插入" << a1[i] << endl;  
        }  
        t1.InOrder();  
    }
    
    int main()
    {
        testAVLTree();
        return 0;
    }
    展开全文
  • 平衡二叉搜索树是一种特殊的二叉搜索树。为什么会有平衡二叉搜索树呢? 考虑一下二叉搜索树的特殊情况,如果一个二叉搜索树所有的节点都是右节点,那么这个二叉搜索树将会退化成为链表。从而导致搜索的时间复杂度...

    简介

    平衡二叉搜索树是一种特殊的二叉搜索树。为什么会有平衡二叉搜索树呢?

    考虑一下二叉搜索树的特殊情况,如果一个二叉搜索树所有的节点都是右节点,那么这个二叉搜索树将会退化成为链表。从而导致搜索的时间复杂度变为O(n),其中n是二叉搜索树的节点个数。

    而平衡二叉搜索树正是为了解决这个问题而产生的,它通过限制树的高度,从而将时间复杂度降低为O(logn)。

    AVL的特性

    在讨论AVL的特性之前,我们先介绍一个概念叫做平衡因子,平衡因子表示的是左子树和右子树的高度差。

    如果平衡因子=0,表示这是一个完全平衡二叉树。

    如果平衡因子=1,那么这棵树就是平衡二叉树AVL。

    也就是是说AVL的平衡因子不能够大于1。

    先看一个AVL的例子:

    总结一下,AVL首先是一个二叉搜索树,然后又是一个二叉平衡树。

    AVL的构建

    有了AVL的特性之后,我们看下AVL是怎么构建的。

    public class AVLTree {
    
        //根节点
        Node root;
    
        class Node {
            int data; //节点的数据
            int height; //节点的高度
            Node left;
            Node right;
    
            public Node(int data) {
                this.data = data;
                left = right = null;
            }
        }
    

    同样的,AVL也是由各个节点构成的,每个节点拥有data,left和right几个属性。

    因为是二叉平衡树,节点是否平衡还跟节点的高度有关,所以我们还需要定义一个height作为节点的高度。

    在来两个辅助的方法,一个是获取给定的节点高度:

    //获取给定节点的高度
        int height(Node node) {
            if (node == null)
                return 0;
            return node.height;
        }
    

    和获取平衡因子:

    //获取平衡因子
        int getBalance(Node node) {
            if (node == null)
                return 0;
            return height(node.left) - height(node.right);
        }
    

    AVL的搜索

    AVL的搜索和二叉搜索树的搜索方式是一致的。

    先看一个直观的例子,怎么在AVL中搜索到7这个节点:

    搜索的基本步骤是:

    1. 从根节点15出发,比较根节点和搜索值的大小
    2. 如果搜索值小于节点值,那么递归搜索左侧树
    3. 如果搜索值大于节点值,那么递归搜索右侧树
    4. 如果节点匹配,则直接返回即可。

    相应的java代码如下:

    //搜索方法,默认从根节点搜索
        public Node search(int data){
            return search(root,data);
        }
    
        //递归搜索节点
        private Node search(Node node, int data)
        {
            // 如果节点匹配,则返回节点
            if (node==null || node.data==data)
                return node;
    
            // 节点数据大于要搜索的数据,则继续搜索左边节点
            if (node.data > data)
                return search(node.left, data);
    
            // 如果节点数据小于要搜素的数据,则继续搜索右边节点
            return search(node.right, data);
        }
    

    AVL的插入

    AVL的插入和BST的插入是一样的,不过插入之后有可能会导致树不再平衡,所以我们需要做一个再平衡的步骤。

    看一个直观的动画:

    插入的逻辑是这样的:

    1. 从根节点出发,比较节点数据和要插入的数据
    2. 如果要插入的数据小于节点数据,则递归左子树插入
    3. 如果要插入的数据大于节点数据,则递归右子树插入
    4. 如果根节点为空,则插入当前数据作为根节点

    插入数据之后,我们需要做再平衡。

    再平衡的逻辑是这样的:

    1. 从插入的节点向上找出第一个未平衡的节点,这个节点我们记为z
    2. 对z为根节点的子树进行旋转,得到一个平衡树。

    根据以z为根节点的树的不同,我们有四种旋转方式:

    • left-left:

    如果是left left的树,那么进行一次右旋就够了。

    右旋的步骤是怎么样的呢?

    1. 找到z节点的左节点y
    2. 将y作为旋转后的根节点
    3. z作为y的右节点
    4. y的右节点作为z的左节点
    5. 更新z的高度

    相应的代码如下:

    Node rightRotate(Node node) {
            Node x = node.left;
            Node y = x.right;
    
            // 右旋
            x.right = node;
            node.left = y;
    
            // 更新node和x的高度
            node.height = max(height(node.left), height(node.right)) + 1;
            x.height = max(height(x.left), height(x.right)) + 1;
    
            // 返回新的x节点
            return x;
        }
    
    • right-right:

    如果是right-right形式的树,需要经过一次左旋:

    左旋的步骤正好和右旋的步骤相反:

    1. 找到z节点的右节点y
    2. 将y作为旋转后的根节点
    3. z作为y的左节点
    4. y的左节点作为z的右节点
    5. 更新z的高度

    相应的代码如下:

    //左旋
        Node leftRotate(Node node) {
            Node x = node.right;
            Node y = x.left;
    
            //左旋操作
            x.left = node;
            node.right = y;
    
            // 更新node和x的高度
            node.height = max(height(node.left), height(node.right)) + 1;
            x.height = max(height(x.left), height(x.right)) + 1;
    
            // 返回新的x节点
            return x;
        }
    
    • left-right:

    如果是left right的情况,需要先进行一次左旋将树转变成left left格式,然后再进行一次右旋,得到最终结果。

    • right-left:

    如果是right left格式,需要先进行一次右旋,转换成为right right格式,然后再进行一次左旋即可。

    现在问题来了,怎么判断一个树到底是哪种格式呢?我们可以通过获取平衡因子和新插入的数据比较来判断:

    1. 如果balance>1,那么我们在Left Left或者left Right的情况,这时候我们需要比较新插入的data和node.left.data的大小

      如果data < node.left.data,表示是left left的情况,只需要一次右旋即可

      如果data > node.left.data,表示是left right的情况,则需要将node.left进行一次左旋,然后将node进行一次右旋

    2. 如果balance<-1,那么我们在Right Right或者Right Left的情况,这时候我们需要比较新插入的data和node.right.data的大小
      如果data > node.right.data,表示是Right Right的情况,只需要一次左旋即可

      如果data < node.left.data,表示是Right left的情况,则需要将node.right进行一次右旋,然后将node进行一次左旋

    插入节点的最终代码如下:

    //插入新节点,从root开始
        public void insert(int data){
            root=insert(root, data);
        }
    
        //遍历插入新节点
        Node insert(Node node, int data) {
    
            //先按照普通的BST方法插入节点
            if (node == null)
                return (new Node(data));
    
            if (data < node.data)
                node.left = insert(node.left, data);
            else if (data > node.data)
                node.right = insert(node.right, data);
            else
                return node;
    
            //更新节点的高度
            node.height = max(height(node.left), height(node.right)) + 1;
    
            //判断节点是否平衡
            int balance = getBalance(node);
    
            //节点不平衡有四种情况
            //1.如果balance>1,那么我们在Left Left或者left Right的情况,这时候我们需要比较新插入的data和node.left.data的大小
            //如果data < node.left.data,表示是left left的情况,只需要一次右旋即可
            //如果data > node.left.data,表示是left right的情况,则需要将node.left进行一次左旋,然后将node进行一次右旋
            //2.如果balance<-1,那么我们在Right Right或者Right Left的情况,这时候我们需要比较新插入的data和node.right.data的大小
            //如果data > node.right.data,表示是Right Right的情况,只需要一次左旋即可
            //如果data < node.left.data,表示是Right left的情况,则需要将node.right进行一次右旋,然后将node进行一次左旋
    
            //left left
            if (balance > 1 && data < node.left.data)
                return rightRotate(node);
    
            // Right Right
            if (balance < -1 && data > node.right.data)
                return leftRotate(node);
    
            // Left Right
            if (balance > 1 && data > node.left.data) {
                node.left = leftRotate(node.left);
                return rightRotate(node);
            }
    
            // Right Left
            if (balance < -1 && data < node.right.data) {
                node.right = rightRotate(node.right);
                return leftRotate(node);
            }
    
            //返回插入后的节点
            return node;
        }
    

    AVL的删除

    AVL的删除和插入类似。

    首先按照普通的BST删除,然后也需要做再平衡。

    看一个直观的动画:

    删除之后,节点再平衡也有4种情况:

    1. 如果balance>1,那么我们在Left Left或者left Right的情况,这时候我们需要比较左节点的平衡因子

      如果左节点的平衡因子>=0,表示是left left的情况,只需要一次右旋即可

      如果左节点的平衡因<0,表示是left right的情况,则需要将node.left进行一次左旋,然后将node进行一次右旋

    2. 如果balance<-1,那么我们在Right Right或者Right Left的情况,这时候我们需要比较右节点的平衡因子

      如果右节点的平衡因子<=0,表示是Right Right的情况,只需要一次左旋即可

      如果右节点的平衡因子>0,表示是Right left的情况,则需要将node.right进行一次右旋,然后将node进行一次左旋

    相应的代码如下:

    Node delete(Node node, int data)
        {
            //Step 1. 普通BST节点删除
            // 如果节点为空,直接返回
            if (node == null)
                return node;
    
            // 如果值小于当前节点,那么继续左节点删除
            if (data < node.data)
                node.left = delete(node.left, data);
    
            //如果值大于当前节点,那么继续右节点删除
            else if (data > node.data)
                node.right = delete(node.right, data);
    
           //如果值相同,那么就是要删除的节点
            else
            {
                // 如果是单边节点的情况
                if ((node.left == null) || (node.right == null))
                {
                    Node temp = null;
                    if (temp == node.left)
                        temp = node.right;
                    else
                        temp = node.left;
    
                    //没有子节点的情况
                    if (temp == null)
                    {
                        node = null;
                    }
                    else // 单边节点的情况
                        node = temp;
                }
                else
                {  //非单边节点的情况
                    //拿到右侧节点的最小值
                    Node temp = minValueNode(node.right);
                    //将最小值作为当前的节点值
                    node.data = temp.data;
                    // 将该值从右侧节点删除
                    node.right = delete(node.right, temp.data);
                }
            }
    
            // 如果节点为空,直接返回
            if (node == null)
                return node;
    
            // step 2: 更新当前节点的高度
            node.height = max(height(node.left), height(node.right)) + 1;
    
            // step 3: 获取当前节点的平衡因子
            int balance = getBalance(node);
    
            // 如果节点不再平衡,那么有4种情况
            //1.如果balance>1,那么我们在Left Left或者left Right的情况,这时候我们需要比较左节点的平衡因子
            //如果左节点的平衡因子>=0,表示是left left的情况,只需要一次右旋即可
            //如果左节点的平衡因<0,表示是left right的情况,则需要将node.left进行一次左旋,然后将node进行一次右旋
            //2.如果balance<-1,那么我们在Right Right或者Right Left的情况,这时候我们需要比较右节点的平衡因子
            //如果右节点的平衡因子<=0,表示是Right Right的情况,只需要一次左旋即可
            //如果右节点的平衡因子>0,表示是Right left的情况,则需要将node.right进行一次右旋,然后将node进行一次左旋
            // Left Left Case
            if (balance > 1 && getBalance(node.left) >= 0)
                return rightRotate(node);
    
            // Left Right Case
            if (balance > 1 && getBalance(node.left) < 0)
            {
                node.left = leftRotate(node.left);
                return rightRotate(node);
            }
    
            // Right Right Case
            if (balance < -1 && getBalance(node.right) <= 0)
                return leftRotate(node);
    
            // Right Left Case
            if (balance < -1 && getBalance(node.right) > 0)
            {
                node.right = rightRotate(node.right);
                return leftRotate(node);
            }
            return node;
        }
    

    本文的代码地址:

    learn-algorithm

    本文收录于 www.flydean.com

    最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧等你来发现!

    欢迎关注我的公众号:「程序那些事」,懂技术,更懂你!

    展开全文
  • Python之平衡二叉搜索树(AVL树)

    千次阅读 2019-04-15 11:01:26
    它能在O(log n)内完成插入、查找和删除操作,最早被发明的平衡二叉搜索树为AVL树。 常见的平衡二叉搜索树有:AVL树、红黑树、Treap、节点大小平衡树。 注意:移动树的节点时,被移动节点及其原新两个位置的父、子...

    平衡二叉搜索树(Balanced Binary Tree):
    是一种结构平衡的二叉搜索树,即叶节点高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。它能在O(log n)内完成插入、查找和删除操作,最早被发明的平衡二叉搜索树为AVL树。

    常见的平衡二叉搜索树有:AVL树、红黑树、Treap、节点大小平衡树。

    注意:移动树的节点时,被移动节点及其原新两个位置的父、子节点的指向均需重新指向,保证各节点指向正确。

    平衡二叉搜索树(AVL树),可以自动进行调整,以确保树时时保持平衡。

    平衡因子(balance factor):为实现AVL树,需要在树的每个节点加入一个平衡因子(balance factor)以跟踪其变化情况。

    一个节点的平衡因子为其左子树的高度和右子树的高度之差,即balanceFactor=height(leftSubTree)−height(rightSubTree)。
    如果平衡因子大于零,则子树左重(left-heavy)。如果平衡因子小于零,则子树右重(right-heavy)。如果平衡因子是零,那么树完美平衡。

    为实现AVL树,定义平衡因子为-1、0或1时这个树是平衡的,一旦树的节点的平衡因子超出了这个范围,则需要将树恢复平衡。

    此例与BST二叉查找树的代码区别:
    1、TreeNode类中,__init__多了balanceFactor属性;
    2、BinarySearchTree类中,_put()中多了2行更新平衡因子的代码;
    3、BinarySearchTree类中,多了updateBalance()、rotateLeft()、rotateRight()、rebalance()四个函数;
    4、此例中删除节点时的平衡未实现。

    示例:

    # 创建树的节点类
    class TreeNode(object):
    	# 初始化树的节点
    	def __init__(self, key, val, left=None, right=None, parent=None, balanceFactor=0):
    		self.key = key 									#节点值,节点位置,索引
    		self.payload = val 								#有效载荷,节点显示的值
    		self.leftChild = left 							#左子节点
    		self.rightChild = right 						#右子节点
    		self.parent = parent 							#父节点
    		self.balanceFactor = balanceFactor				#节点的平衡因子
    
    	# 判断是否有左子节点,若有则返回左子节点
    	def hasLeftChild(self):
    		return self.leftChild
    
    	# 判断是否有右子节点,若有则返回右子节点
    	def hasRightChild(self):
    		return self.rightChild
    
    	# 判断是否是左子节点(父节点存在,并且self与self父节点的左子节点相同)
    	def isLeftChild(self):
    		# 下面的含义是(self.parent is not None) and (self.parent.leftChild == self)
    		return self.parent and self.parent.leftChild == self
    
    	# 判断是否是右子节点
    	def isRightChild(self):
    		return self.parent and self.parent.rightChild == self
    
    	# 判断是否是根节点
    	def isRoot(self):
    		return not self.parent	 						#没有父节点
    
    	# 判断是否是叶节点
    	def isLeaf(self):
    		return not (self.rightChild or self.leftChild)	#没有左右子节点
    
    	# 判断是否有子节点
    	def hasAnyChildren(self):
    		return self.rightChild or self.leftChild 		#有左或右子节点
    
    	# 判断是否有2个子节点
    	def hasBothChildren(self):
    		return self.rightChild and self.leftChild 		#有左右2个子节点
    
    	# 替换节点数据
    	def replaceNodeData(self, key, value, lc, rc):
    		self.key = key 									#更新节点值
    		self.payload = value 							#更新有效载荷
    		self.leftChild = lc 							#更新左子节点
    		self.rightChild = rc 							#更新右子节点
    		if self.hasLeftChild():							#若有左子节点
    			self.leftChild.parent = self 				#将该节点的左子节点的父节点指向self
    		if self.hasRightChild():						#若有右子节点
    			self.rightChild.parent = self 				#将该节点的右子节点的父节点指向self
    
    	# 中序遍历
    	# 只要用了yield语句,普通函数就是生成器,也是迭代器,在定义过程中不需要像迭代器那样写__iter__()和__next__()方法。yield语句的作用就是在调用的时候返回相应的值和作为生成器的标志。
    	def __iter__(self):
    		if self:										#若当前节点存在,则
    			if self.hasLeftChild():						#若当前节点有左子节点,则
    				for elem in self.leftChild:				#循环输出当前节点的左子树的节点值
    					yield elem 							#在for循环中,每次执行到yield时,就返回一个迭代值,且不会终止循环;下个循环时,代码从yield返回值的下一行继续返回
    			yield self.key 								#返回当前节点值
    			if self.hasRightChild():					#若当前节点有右子节点,则
    				for elem in self.rightChild:			#循环输出当前节点的右子树的节点值
    					yield elem 				
    
    	# 将被删除节点的继任者拼接到被删除的节点位置
    	def spliceOut(self):
    		if self.isLeaf():								#若被删除节点是叶节点,则无需再拼接
    			if self.isLeftChild():						#若被删除节点是父节点的左子节点,则
    				self.parent.leftChild = None 			#被删除节点为None,无需再拼接
    			else:										#若被删除节点是父节点的右子节点,则
    				self.parent.rightChild = None 			#被删除节点为None,无需再拼接
    		elif self.hasAnyChildren():						#若被删除节点有子节点,则
    			if self.hasLeftChild():						#若被删除节点有左子节点,则
    				if self.isLeftChild():					#若被删除节点是左子节点,则
    					# 将被删除节点的父节点的左子节点指向被删除节点的左子节点
    					self.parent.leftChild = self.leftChild  
    				else:									#若被删除节点是右子节点,则
    					# 将被删除节点的父节点的右子节点指向被删除节点的左子节点
    					self.parent.rightChild = self.leftChild 
    				# 将被删除节点的左子节点的父节点指向被删除节点的父节点
    				self.leftChild.parent = self.parent 		
    			else:										#若被删除节点没有左子节点,则被删除节点有右子节点
    				if self.isLeftChild():					#若被删除节点是左子节点,则
    					# 将被删除节点的父节点的左子节点指向被删除节点的右子节点
    					self.parent.leftChild = self.rightChild 
    				else:									#若被删除节点是右子节点,则
    					# 将被删除节点的父节点的右子节点指向被删除节点的右子节点
    					self.parent.rightChild = self.rightChild
    				# 将被删除节点的右子节点的父节点指向被删除节点的父节点
    				self.rightChild.parent = self.parent 		
    
    	# 查找被删除节点的继任者,继任者节点最多只能有一个子节点
    	def findSuccessor(self):
    		succ = None 									#初始化被删除节点的继任者为None
    		if self.hasRightChild():						#若被删除节点有右子节点,则
    			succ = self.rightChild.findMin()			#获取被删除节点的右子树中的最小节点作为继任者
    		else:											#若被删除节点没有右子节点,则
    			if self.parent:								#若被删除节点有父节点,则
    				if self.isLeftChild():					#若被删除节点是父节点的左子节点,则
    					succ = self.parent 					#被删除节点的父节点是继任者
    				else:									#若被删除节点是父节点的右子节点,则被删除节点的继任者是其父节点的继任者,不会是被删除节点
    					self.parent.rightChild = None 		#暂时将None赋值给被删除节点,则继任者不会是被删除节点,方便下一行递归查找
    					succ = self.parent.findSuccessor()	#将被删除节点的父节点的继任者作为继任者
    					self.parent.rightChild = self 		#获得继任者后,重新将被删除节点赋值给自己,以免被删除节点为None扰乱树结构
    		return succ
    
    	# 查找当前树的最小子节点,因此例是BST搜索树,左子节点的值是最小的,所以只找左子节点
    	def findMin(self):
    		current = self 									#将自身设置为当前节点
    		while current.hasLeftChild():					#若当前节点有左子节点,则循环
    			current = current.leftChild 				#将当前节点的左子节点作为下一个当前节点
    		return current 									#返回最终左子节点,即此树中的最小节点			
    
    # 二叉查找树类(此例为BST搜索树类)
    class BinarySearchTree(object):
    	# 初始化空二叉树
    	def __init__(self):
    		self.root = None
    		self.size = 0
    
    	# 获取树的大小
    	def length(self):
    		return self.size
    
    	# 通过__len__方法使用len()
    	def __len__(self):
    		return self.size
    
    	# 实现了__iter__方法的对象就是可迭代对象,__iter__覆盖for x in操作,因此它是递归的!因它是在TreeNode实例上递归的,所以__iter__方法在TreeNode类中定义
    	def __iter__(self):
    		return self.root.__iter__()			#返回二叉查找树根节点的迭代,即遍历二叉查找树
    
    	# 创建二叉搜索树
    	def put(self, key, val):
    		if self.root:						#若树已经有根节点,则
    			self._put(key, val, self.root)	#从树的根开始,搜索二叉树
    		else:								#若树没有根节点,则
    			self.root = TreeNode(key, val)	#创建一个新的TreeNode并把它作为树的根节点
    		self.size = self.size + 1 			#增加树的大小
    
    	# 搜索树,put()的辅助函数
    	def _put(self, key, val, currentNode):
    		if key < currentNode.key:			#若新的键值小于当前节点键值,则搜索左子树
    			if currentNode.hasLeftChild():	#若当前节点有左子树要搜索,则
    				self._put(key, val, currentNode.leftChild)	#递归搜索左子树
    			else:							#若当前节点无左子树要搜索,则
    				currentNode.leftChild = TreeNode(key, val, parent = currentNode)	#创建一个新的TreeNode并把它作为当前节点的左子节点
    				self.updateBalance(currentNode.leftChild)	#更新当前节点的左子节点的平衡因子
    		elif key == currentNode.key:		#若新的键值=当前节点键值,则
    			currentNode.payload = val 		#更新当前节点的有效载荷
    			self.size = self.size - 1 		#由于只修改,未增加,又因put()中+1,所以此处-1
    		else:								#若新的键值>=当前节点键值,则搜索右子树
    			if currentNode.hasRightChild():	#若当前节点有右子树要搜索,则
    				self._put(key, val, currentNode.rightChild)	#递归搜索右子树
    			else:							#若当前节点无右子树要搜索,则
    				currentNode.rightChild = TreeNode(key, val, parent = currentNode)	#创建一个新的TreeNode并把它作为当前节点的右子节点
    				self.updateBalance(currentNode.rightChild)	#更新当前节点的右子节点的平衡因子
    
    	# 更新平衡因子
    	def updateBalance(self, node):
    		if node.balanceFactor > 1 or node.balanceFactor < -1:	#若节点的平衡因子不是-1、0、1,则
    			self.rebalance(node)						#该节点再平衡
    			return
    		if node.parent != None:							#若该节点有父节点,即该节点不是根节点,则
    			if node.isLeftChild():						#若该节点是左子节点,则
    				node.parent.balanceFactor += 1 			#该节点的父节点的平衡因子+1
    			elif node.isRightChild():					#若该节点是右子节点,则
    				node.parent.balanceFactor -= 1 			#该节点的父节点的平衡因子-1
    			if node.parent.balanceFactor != 0:			#若该节点的父节点的平衡因子不为0,则
    				self.updateBalance(node.parent)			#更新该节点的父节点的平衡因子
    
    	# 左旋转(右重的树要左旋转才平衡)
    	"""
    	示例:B为原根,D为新根,节点的高度为子孙节点的最大层级+1,下面为树的图
    			B 										D
    		A 		D  								B 		E
    			C 		E 						A 		C
    	newBal(B) = hA - hC					#新B节点的平衡因子为A与C节点的高度差
    	oldBal(B) = hA - hD 				#原B节点的平衡因子为A与D节点的高度差
    	oldBal(B) = hA - (1 + max(hC, hE))	#原D节点的高度为两子树高度中较大者加1,hC和hE没有改变
    	newBal(B) - oldBal(B) = hA - hC - (hA - (1 + max(hC, hE))) = 1 + max(hC, hE) - hC
    	newBal(B) = oldBal(B) + 1 + max(hC, hE) - hC = oldBal(B) + 1 + max(hC - hC, hE - hC)
    			  = oldBal(B) + 1 + max(hE - hC, 0) = oldBal(B) + 1 + max(-oldBal(D), 0)
    			  = oldBal(B) + 1 - min(oldBal(D), 0)		#根据平衡因子计算公式:oldBal(D)=hC-hE,得出hE-hC=−oldBal(D)
    	newBal(D) = hB - hE
    	oldBal(D) = hC - hE
    	newBal(D) - oldBal(D) = hB - hC = 1 + max(hA, hC) - hC = 1 + max(hA - hC, hC - hC)
    	newBal(D) = oldBal(D) + 1 + max(hA - hC, 0) = oldBal(D) + 1 + max(newBal(B), 0)
    	"""
    	def rotateLeft(self, rotRoot):
    		newRoot = rotRoot.rightChild 					#待旋转节点的右子节点设为新的根节点
    		rotRoot.rightChild = newRoot.leftChild 			#新根的原左子节点作为原根的新右子节点
    		if newRoot.leftChild != None:					#若新根原来有左子节点,则
    			newRoot.leftChild.parent = rotRoot 			#将新根的原左子节点的父节点指向原根
    		newRoot.parent = rotRoot.parent 				#新根的父节点指向原根的父节点
    		if rotRoot.isRoot():							#若原根是树的根节点,则
    			self.root = newRoot 						#将新根设为树的根节点
    		else:											#若原根不是树的根节点,则
    			if rotRoot.isLeftChild():					#若原根是左子树,则
    				rotRoot.parent.leftChild = newRoot 		#将原根的父节点的左子节点指向新根
    			else:										#若原根是右子树,则
    				rotRoot.parent.rightChild = newRoot 	#将原根的父节点的右子节点指向新根
    		newRoot.leftChild = rotRoot 					#将新根的左子节点指向原根
    		rotRoot.parent = newRoot 						#将原根的父节点指向新根
    		rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor, 0)	#更新原根节点的平衡因子,被移动的子树内的节点的平衡因子不受旋转影响,计算方法见上方注释
    		newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(rotRoot.balanceFactor, 0)	#更新新根节点的平衡因子,被移动的子树内的节点的平衡因子不受旋转影响,计算方法见上方注释
    
    	# 右旋转(左重的树要右旋转才平衡)
    	"""
    	示例:E为原根,C为新根,节点的高度为子孙节点的最大层级
    					 E 								 C
    				C 		  F 					B 		   E
    			B 		D 						A 		   D 	   F
    		A
    	newBal(E) = hD - hF
    	oldBal(E) = hC - hF
    	newBal(E) - oldBal(E) = hD - hC = hD - (1 + max(hB, hD)) = -1 + min(hD - hB, hD - hD)
    						  = -1 + min(hD - hB, 0) = -1 - max(hB - hD, 0) 
    						  = - max(oldBal(C), 0) - 1
    	newBal(E) = oldBal(E) - 1 - max(oldBal(C), 0)
    	newBal(C) = hB - hE
    	oldBal(C) = hB - hD
    	newBal(C) - oldBal(C) = hD - hE = hD - (1 + max(hD, hF)) = -1 + min(hD - hD, hD - hF)
    						  = -1 + min(0, hD - hF) = -1 + min(0, newBal(E))
    	newBal(C) = oldBal(C) - 1 + min(0, newBal(E))
    	"""
    	def rotateRight(self, rotRoot):
    		newRoot = rotRoot.leftChild 					#待旋转节点的左子节点设为新的根节点
    		rotRoot.leftChild = newRoot.rightChild 			#新根的原右子节点作为原根的新左子节点
    		if newRoot.rightChild != None:					#若新根原来有右子节点,则
    			newRoot.rightChild.parent = rotRoot 		#将新根的原右子节点的父节点指向原根
    		newRoot.parent = rotRoot.parent 				#新根的父节点指向原根的父节点
    		if rotRoot.isRoot():							#若原根是树的根节点,则
    			self.root = newRoot 						#将新根设为树的根节点
    		else:											#若原根不是树的根节点,则
    			if rotRoot.isLeftChild():					#若原根是左子树,则
    				rotRoot.parent.leftChild = newRoot 		#将原根的父节点的左子节点指向新根
    			else:										#若原根是右子树,则
    				rotRoot.parent.rightChild = newRoot 	#将原根的父节点的右子节点指向新根
    		newRoot.rightChild = rotRoot 					#将新根的右子节点指向原根
    		rotRoot.parent = newRoot 						#将原根的父节点指向新根
    		rotRoot.balanceFactor = rotRoot.balanceFactor - 1 - max(newRoot.balanceFactor, 0)	#更新原根节点的平衡因子,被移动的子树内的节点的平衡因子不受旋转影响,计算方法见上方注释
    		newRoot.balanceFactor = newRoot.balanceFactor - 1 + min(0, rotRoot.balanceFactor)	#更新新根节点的平衡因子,被移动的子树内的节点的平衡因子不受旋转影响,计算方法见上方注释
    
    	# 再平衡
    	def rebalance(self, node):
    		if node.balanceFactor < 0:						#若该节点的平衡因子<0,则
    			if node.rightChild.balanceFactor > 0:		#若该节点的右子节点的平衡因子>0,则
    				self.rotateRight(node.rightChild)		#右旋转该节点的右子节点
    			self.rotateLeft(node)						#左旋转该节点
    		elif node.balanceFactor > 0:					#若该节点的平衡因子>0,则
    			if node.leftChild.balanceFactor < 0:		#若该节点的左子节点的平衡因子<0,则
    				self.rotateLeft(node.leftChild)			#左旋转该节点的左子节点
    			self.rotateRight(node)						#右旋转该节点
    
    	# 通过__setitem__方法使用mytree[3]="red"方式,否则只能用put()方法
    	def __setitem__(self, k, v):
    		self.put(k, v)
    
    	# 根据索引key获取其对应的节点值
    	def get(self, key):
    		if self.root:						#若树已经有根节点,则
    			res = self._get(key, self.root)	#从树的根开始,搜索二叉树
    			if res:							#若搜索到了,则
    				return res.payload 			#返回存储在节点的有效载荷中的值,即节点显示的值
    			else:							#若没搜索到,则没有该索引对应的节点
    				return None
    		else:								#若树没有根节点,则说明是空二叉树
    			return None
    
    	# 搜索树,get()的辅助函数
    	def _get(self, key, currentNode):
    		if not currentNode:					#若没有当前节点,则返回None
    			return None
    		elif currentNode.key == key:		#若当前节点的位置和待查找的位置相同,则
    			return currentNode 				#返回当前节点的值
    		elif key < currentNode.key:			#若当前节点的位置>待查找的位置,则
    			return self._get(key, currentNode.leftChild)	#递归查找当前节点的左子树
    		else:								#若当前节点的位置<=待查找的位置,则
    			return self._get(key, currentNode.rightChild)	#递归查找当前节点的右子树
    
    	# 通过__getitem__方法使用mytree[3]获取值的方式,否则只能用get()方法
    	def __getitem__(self, key):
    		return self.get(key)
    
    	# 通过__contains__方法使用in方法
    	def __contains__(self, key):
    		if self._get(key, self.root):
    			return True
    		else:
    			return False
    
    	# 根据索引key删除其对应的节点
    	def delete(self, key):
    		if self.size > 1:									#若树的大小>1,则
    			nodeToRemove = self._get(key, self.root)		#获取要删除的节点
    			if nodeToRemove:								#若该节点存在,则
    				self.remove(nodeToRemove)					#删除该节点
    				self.size = self.size - 1 					#树的大小减1
    			else:											#若该节点不存在,则
    				raise KeyError('错误,键值不在树中')		#报错
    		elif self.size == 1 and self.root.key == key:		#若树的大小为1,且要删除的是根,则
    			self.root = None 								#根节点为None
    			self.size = self.size - 1 						#树的大小减1
    		else:												#若树的大小为0,则为空树
    			raise KeyError('错误,键值不在树中')			#报错
    
    	# 通过__delitem__方法使用del方法
    	def __delitem__(self, key):
    		self.delete(key)
    
    	# 删除节点
    	def remove(self, currentNode):
    		if currentNode.isLeaf(): 						#若被删除节点是叶节点,则没有子节点
    			if currentNode == currentNode.parent.leftChild:	#若被删除节点是其父节点的左子节点,则
    				currentNode.parent.leftChild = None 	#被删除节点为None
    			else:										#若被删除节点是其父节点的右子节点,则
    				currentNode.parent.rightChild = None 	#被删除节点为None
    		elif currentNode.hasBothChildren(): 			#若被删除节点有2个子节点,则
    			succ = currentNode.findSuccessor()			#获取被删除节点的继任者(防止树结构混乱)
    			succ.spliceOut()							#将被删除节点的继任者拼接到被删除节点位置
    			currentNode.key = succ.key 					#将被删除节点位置的值设置为继任者的值
    			currentNode.payload = succ.payload 			#将被删除节点的有效载荷设置为继任者的有效载荷
    		else: 											#若被删除节点只有1个子节点,则
    			if currentNode.hasLeftChild():				#若被删除节点只有左子节点,则
    				if currentNode.isLeftChild():			#若被删除节点是左子节点,则
    					# 将被删除节点的左子节点的父节点指向被删除节点的父节点
    					currentNode.leftChild.parent = currentNode.parent 	
    					# 将被删除节点的父节点的左子节点指向被删除节点的左子节点
    					currentNode.parent.leftChild = currentNode.leftChild 	
    				elif currentNode.isRightChild():		#若被删除节点是右子节点,则
    					# 将被删除节点的左子节点的父节点指向被删除节点的父节点
    					currentNode.leftChild.parent = currentNode.parent
    					# 将被删除节点的父节点的右子节点指向被删除节点的左子节点
    					currentNode.parent.rightChild = currentNode.leftChild
    				else:								#若被删除节点无父节点,则被删除节点为根节点
    					# 替换被删除节点的左子节点的键、有效载荷、左子节点和右子节点数据
    					currentNode.replaceNodeData(currentNode.leftChild.key, currentNode.leftChild.payload, currentNode.leftChild.leftChild, currentNode.leftChild.rightChild)
    			else:										#若被删除节点只有右子节点,则
    				if currentNode.isLeftChild():			#若被删除节点是左子节点,则
    					# 将被删除节点的右子节点的父节点指向被删除节点的父节点
    					currentNode.rightChild.parent = currentNode.parent
    					# 将被删除节点的父节点的左子节点指向被删除节点的右子节点
    					currentNode.parent.leftChild = currentNode.rightChild
    				elif currentNode.isRightChild():		#若被删除节点是右子节点,则
    					# 将被删除节点的右子节点的父节点指向被删除节点的父节点
    					currentNode.rightChild.parent = currentNode.parent
    					# 将被删除节点的父节点的右子节点指向被删除节点的右子节点
    					currentNode.parent.rightChild = currentNode.rightChild
    				else:								#若被删除节点无父节点,则被删除节点为根节点
    					# 替换被删除节点的右子节点的键、有效载荷、左子节点和右子节点数据
    					currentNode.replaceNodeData(currentNode.rightChild.key, currentNode.rightChild.payload, currentNode.rightChild.leftChild, currentNode.rightChild.rightChild)
    
    mytree = BinarySearchTree()	#实例化二叉搜索树
    mytree[2]="yellow" 			#此例中第一个添加到mytree的索引值为2
    mytree[0]="red"				#通过__setitem__方法添加节点
    mytree[1]="blue"
    mytree[3]="at"
    print(mytree[3])
    mytree[3]="at2"				#修改mytree[3]的值
    print(mytree[3])
    mytree.put(4, 'val')		#通过put()方法在索引为4的位置添加'val'
    if 4 in mytree:				#in使用__contains__()判断索引是否在树中
    	print('in')
    print(len(mytree))			#通过__len__方法获取mytree树的大小
    print(mytree.length())		#通过length()方法获取mytree树的大小
    print(mytree[4])			#通过__getitem__方法获取索引为4的节点
    print(mytree.get(4))		#通过get()方法获取索引为4的节点
    print(mytree.root.key)		#树的根节点的key
    mytree.delete(2)			#通过delete()方法删除索引为2的节点
    # del mytree[2]				#通过__delitem__方法删除索引为2的节点
    print(mytree[2])
    for i in mytree:			#通过两个类中的__iter__方法进行迭代
    	print(i)
    

    结果为:

    at
    at2
    in
    5
    5
    val
    val
    1
    None
    0
    1
    3
    4
    
    展开全文
  • 二叉搜索树的树高与性能前面笔者介绍了二叉搜索树的实现和性能分析,查询,插入和删除等操作均线性正比于二叉树的高度。在最坏的情况下,线性表退化为列表,二叉搜索树的性能会降低至O(n)。因此,如果能控制树高,则...

    二叉搜索树的树高与性能

    前面笔者介绍了二叉搜索树的实现和性能分析,查询,插入和删除等操作均线性正比于二叉树的高度。在最坏的情况下,线性表退化为列表,二叉搜索树的性能会降低至O(n)。因此,如果能控制树高,则二叉搜索树的性能会明显提升

    理想平衡与适度平衡

    理想平衡

    既然二叉搜索树的性能主要影响与树高,则应该在节点数目固定的前提下,尽可能降低树高。也意味着,应尽可能地使兄弟子树的高度彼此接近,即全树尽可能的平衡。当然根据二叉树的特性,规模为n的二叉树,高度不可能小于log以2为底n的对数。如果高度为log以2为底n的对数的平衡二叉树,则称为理想平衡树。完全二叉树,满二叉树均属于理想平衡树。

    适度平衡

    理想平衡的条件过于严格,在实际中意义不大,因为出现的概率实现太小了。因此有必要定制一种规则,限制两个兄弟子树的高度差在一定的范围内。满足这个限制条件则为平衡二叉树。例如:AVL树,伸展树,红黑树,kd-树都属于适度平衡树。因此均属于平衡二叉搜索树

    二叉搜索树到平衡二叉搜索树的等价变化

    如果两个二叉搜索树的中序遍历是一致的,则他们彼此等价。如下图所示:
    这里写图片描述

    可以看出,虽然二叉搜索树中各节点的垂直高度有所不同,但水平次序完全一致。这一特点可概括为“上下可变,左右不乱“。

    平衡二叉搜索树的规则:

    平衡二叉搜索树的适度平衡如前文所述,都是通过对树添加了某一限制来保证的。比如,在红黑树,从树根到叶子节点的通路中,总是包含一样多的黑节点。而在AVL树中,兄弟节点的高度差不能超过1。这些限制条件除了保证了适度平衡外,还有如下局限性:

    • 经过单次动态修改之后,最多只有O(logn)处局部不再满足限制条件
    • 可在O(logn)时间内,O(logn)处局部重新满足平衡二叉搜索树的条件
      这意味这,因为添加节点或者删除节点而失衡的节点,可经过等价交换重新恢复平衡。

    这里的树的局部非常重要。比如:任何二叉搜索树,都可以转换为指定规则的二叉搜索树,但是你不得不花费O(n)的时间。而对于上图的二叉搜索树,仅仅需要转换阴影部分即可。

    旋转调整

    最基本的修复手段,就是通过围绕特定节点的旋转,实现等价前提下的局部拓扑调整。

    zig

    这里写图片描述

    如图所示,如果X,Y是C的孩子,C和Z是V的孩子,则经过以V为轴进行顺时针zig的一次旋转。结果会使节点C和C的左子树升一级,V和V的右子树降一级。并且V的左子树为原C的右子树

    zag

    这里写图片描述

    如图所示,如果X,Y是C的孩子,C和Z是V的孩子,则经过以V为轴进行逆时针zag的一次旋转。结果会使节点C和C的右子树升一级,V和V的左子树降一级。并且V的右子树为原C的左子树

    效率与效果

    zig和zag旋转均属局部操作,仅涉及常数个节点及其之间的联接关系,故均可在常数时间内完成。正因如此,在后面实现各种二叉搜索树平衡化算法时,它们都是支撑性的基本操作。

    就与树相关的指标而言,经一次zig或zag旋转之后,节点v的深度加一,节点c的深度减一; 这一局部子树(乃至全树)的高度可能发生变化,但上、下幅度均不超过一层。

    展开全文
  • 平衡搜索树之AVLTree

    千次阅读 2016-07-23 21:21:13
    AVL树又称为高度平衡的二叉搜索树,是1962年有俄罗斯的数学家G.M.Adel'son-Vel'skii和E.M.Landis提出来的。它能保持二叉树的高度 平衡,尽量降低二叉树的高度,减少树的平均搜索长度。所以严格点来说,对于一棵搜索...
  • AVL树(二叉平衡搜索树

    千次阅读 2020-09-01 21:18:03
    AVL是为了维护节点平衡引入的四种节点旋转操作: 节点失衡的原因是由于: 左孩子左子树太高了。(右旋转) node和child节点的高度值都需要更新。 child=node->left; node->left=child->right; child-&...
  • AVL Tree Implementation 自平衡二叉搜索树的实现   学习资料: CSDN:【数据结构】AVL树详解 百度词条:AVL树 在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别...
  • 如果搜索树的高度总是O(logn),就能保证查找、插入、删除的时间为O(logn)。最坏情况下的高度为O(logn)的树称为平衡树 比较流行的一种平衡树是AVL树,它是Adelson-Velskii和Landis在1962年提出的 AVL树的定义 一棵...
  • 文章目录前言自平衡的二叉搜索树(AVL树)AVL树的结构定义AVL树的旋转AVL树失衡的4种情况 :失衡的处理方法左旋操作右旋操作左平衡操作右平衡操作AVL树插入操作AVL树的删除操作判断一颗二叉搜索树是不是平衡树判断一颗...
  • 一、平衡树概述 接下来几篇文章将会介绍平衡树结构: 的高度为O() 其中有两种平衡二叉树结构:AVL和红黑。它们适合内部存储的引用 一个结构:B-,它的度大于2。其适合外部存储的引用(例如,存储在...
  • 在前一篇博客中,谈到二叉搜索树。随机二叉搜索树的平均高度为o(logn),但是会出现极端的情况。如下图所示,则二叉树的高度O(n),在这种已经退化的二叉树下,无论是搜索,还是删除等等操作时间复杂度都为O(n),这我...
  • 平衡二叉搜索树 既然二叉搜索树的性能主要取决于高度,故在节点数目固定的前提下,应尽可能地降低高度。 相应地,应尽可能地使兄弟子树的高度彼此接近,即全树尽可能地平衡。   等价变换 等价二叉搜索树:若两棵...
  • 前面我们写了AVL的创建AVL插入节点,即节点的插入,下面我们介绍AVL节点的删除,与前面调整的 方法相同,在平衡时,对进行调整,具体步骤如下:1. - 判断是否为NULL,若为NULL,直接返回false; - ...
  • 二叉搜索树平衡二叉树

    千次阅读 2016-11-08 21:57:09
    二叉树也是一种树,适用与以上的全部操作,但二叉搜索树能 够实现数据的快速查找 性质: 非空左子树的所有键值小于其根节点的键值 非空右子树的所有键值大于其根节点的键值 左右子树都是二叉搜索树 以下代码...
  • 文章目录前言平衡二叉搜索树(AVL树)AVL树的节点数据结构在原始数据上创建AVL树调整树的节点使平衡的操作:旋转LL (右旋):在左叶的左侧插入数据代码实现:RR(左旋):在右子叶的右侧插入数据代码实现LR(左右旋...
  • 1 什么是二叉搜索树? 二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它...
  • 的结构,如果不能保持平衡,那么其搜索性能会大大打折扣,而本节课介绍了几种经典的平衡树,如AVL,2-3-4tree,红黑等等,然后着重讲了红黑,接下来就红黑的基本性质,作一些简短的总结。   首先,红黑...
  • AVL平衡二叉搜索树

    千次阅读 2014-02-03 11:21:05
    原文: 维基百科AVL C++版  AVL的实现  C语言版 平衡二叉树的 插入 删除 查找 等功能c语言实现 数据结构
  • 初入数据结构中的平衡二叉搜索树(AVL树)
  • AVL 树是晶早发明的自平衡二叉搜索树之— 平衡因子(Balance Factor):某结点的左右子树的高度差 AVL树的特点 每个节点的平衡因子只可能是1、0、-1 (绝对值≤1,如果超过1,称之为“失衡") 每个节点的左右子树高度...
  • 数据结构_平衡二叉搜索树(AVL树)

    千次阅读 2018-06-21 21:22:36
    平衡二叉搜索树 在二叉搜索树中,已经知道search、insert和remove等主要接口的运行时间均正比于树的高度。但是在最坏的情况下,二叉搜索树可能退化成列表,此时查找的效率会降至O(n)。因此,通常通过控制树高,来...
  • 平衡二叉搜索树(AVL)详解

    万次阅读 多人点赞 2018-07-09 17:53:13
    1.二叉搜索树(Binary Sort Tree) 二叉搜索树,又称之为二叉排序树(二叉查找树),它或许是一棵空树,或许是具有以下性质的二叉树: 若他的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树...
  • 二叉搜索树及判断一棵树是否平衡

    千次阅读 2016-07-08 20:34:42
    二叉搜索树的特点: 1. 每个节点都有一个作为搜索依据的关键码(key),所有节点的关键码互不相同。 2. 左子树上所有节点的关键码(key)都小于根节点的关键码(key)。 3. 右子树上所有节点的关键码(key)都...
  • 红黑(RBT)AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑要多; 红黑是弱平衡的,用非严格的平衡来换取增删节点时候旋转次数的降低;红黑上每个结点内含五个域,color...
  • 本篇博客内容略多,涵盖面比较广...一、二叉搜索树 二叉搜索树是一种特殊的二叉树,它的特点是: 对于任意一个节点p,存储在p的左子树的中的所有节点中的值都小于p中的值 对于任意一个节点p,存储在p的右子树的...
  • 平衡二叉查找删除删除调整

    千次阅读 2018-03-14 11:34:39
    AVL删除 avl删除,我们需要从某一个角度或者视角去想问题,比如我们根据删除的结点的继承关系来看: 1.删除的结点 左右子树都为空 (1)可能是根节点,那么我们直接删掉他 (2)可能是叶子结点,在删除时我们...
  • 基本数据结构-平衡二叉搜索树AVL10.1 AVL的定义定义:平衡二叉树或为空树,或为如下性质的二叉排序树: (1)左右子树深度之差的绝对值不超过1; (2)左右子树仍然为平衡二叉树. 平衡因子BF=左子树深度-右子树...
  • 1.叶节点,直接删除 2.只有左枝或只有右枝,可以直接用左子树或右子代替节点 二. 要删除的节点同时有左右子树 化繁为简 1.先找出该节点的直接后继,因为该节点同时有左右两枝,所以直接后继一定是它的右子的...
  • 平衡树

    万次阅读 2018-08-08 22:13:11
     平衡树是二叉搜索树和堆合并构成的数据结构,它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 二.优势  对一棵查找树(search tree)进行查询/新增/删除 等动作,...
  • 1 二叉搜索树(BST)一颗二叉搜索树 (BST)是以一颗二叉树来组织的,可以使用一个链表数据结构来表示,其中,每个结点就是一个对象,包含数据内容key以及left、right和p分别指向结点的左孩子、右孩子和双亲。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 39,740
精华内容 15,896
关键字:

平衡搜索树删除