c 语言双指针的问题

[Or2]

https://www.cs.yale.edu/homes/aspnes/pinewiki/C(2f)AvlTree.html

   3 typedef struct avlNode *AvlTree;
   5 /* empty avl tree is just a null pointer */
   6 
   7 #define AVL_EMPTY (0)
   8 

   9 struct avlNode {
  10     struct avlNode *child[2];    /* left and right */
  11     int key;
  12     int height;
  13 };
  14 
  87 static void
  88 avlRotate(AvlTree *root, int d)
  89 {
  90     AvlTree oldRoot;
  91     AvlTree newRoot;
  92     AvlTree oldMiddle;
  93 
  94     oldRoot = *root;
  95     newRoot = oldRoot->child[d];
  96     oldMiddle = newRoot->child[!d];
  97 
  98     oldRoot->child[d] = oldMiddle;
  99     newRoot->child[!d] = oldRoot;
 100     *root = newRoot;
 101 
 102     /* update heights */
 103     avlFixHeight((*root)->child[!d]);   /* old root */
 104     avlFixHeight(*root);                /* new root */
 105 }
 106 
 107 
 108 /* rebalance at node if necessary */
 109 /* also fixes height */
 110 static void
 111 avlRebalance(AvlTree *t)
 112 {
 113     int d;
 114 
 115     if(*t != AVL_EMPTY) {
 116         for(d = 0; d < 2; d++) {
 117             /* maybe child[d] is now too tall */
 118             if(avlGetHeight((*t)->child[d]) > avlGetHeight((*t)->child[!d]) + 1) {
 119                 /* imbalanced! */
 120                 /* how to fix it? */
 121                 /* need to look for taller grandchild of child[d] */
 122                 if(avlGetHeight((*t)->child[d]->child[d]) > avlGetHeight((*t)->child[d]->child[!d])) {
 123                     /* same direction grandchild wins, do single rotation */
 124                     avlRotate(t, d);
 125                 } else {
 126                     /* opposite direction grandchild moves up, do double rotation */
 127                     avlRotate(&(*t)->child[d], !d);
 128                     avlRotate(t, d);
 129                 }
 130 
 131                 return;   /* avlRotate called avlFixHeight */
 132             }
 133         }
 134                   
 135         /* update height */
 136         avlFixHeight(*t);
 137     }
 138 }
 139 
 140 /* insert into tree */
 141 /* this may replace root, which is why we pass
 142  * in a AvlTree * */
 143 void
 144 avlInsert(AvlTree *t, int key)
 145 {
 146     /* insertion procedure */
 147     if(*t == AVL_EMPTY) {
 148         /* new t */
 149         *t = malloc(sizeof(struct avlNode));
 150         assert(*t);
 151 
 152         (*t)->child[0] = AVL_EMPTY;
 153         (*t)->child[1] = AVL_EMPTY;
 154 
 155         (*t)->key = key;
 156 
 157         (*t)->height = 1;
 158 
 159         /* done */
 160         return;
 161     } else if(key == (*t)->key) {
 162         /* nothing to do */
 163         return;
 164     } else {
 165         /* do the insert in subtree */
 166         avlInsert(&(*t)->child[key > (*t)->key], key);
 167 
 168         avlRebalance(t);
 169 
 170         return;
 171     }
 172 }

1. 这个实现中，avlRotate, avlRebalance, avlInsert 都用了双指针，我的理解是作者特意用了双指针。 双指针相比于直接用指针有什么特别的优势么？
2. avl tree ，red black tree 还有什么写的很好的可以多学习下的实现么？

大家有没有什么高性能，牛皮的实现，让我学习学习

[stein42]

这个通常叫二级指针吧。

AvlTree 定义为指向根结点的指针。
对 AvlTree 进行修改，它的根结点可能改变，所以定义 AvlTree 为 AvlNode* 是必要的。

传参都是传 AvlTree*，相当于 AvlNode**，这是一个二级指针。

另一种定义方法是结构体：
struct AvlTree { AvlNode* root; }
结构体的好处是还可以包含其它字段，例如树的结点数量。
没有其它字段的话用指针也是可以的。

[Or2]

哈哈，豁然开朗啊！